我正在開發一款遊戲，並且爲了安全起見，任何用戶（程序員）只允許將ID存儲到對象而不是指針，並且必須使用此ID來獲取指向對象的指針，以便獨立於它一定的質量。快速64位整數ID查找/搜索
讓我們使用最糟糕的情況：每個ID都在使用中。它是64位，所以你去：18446744073709551616 ID來搜索。很多數據都存儲在數據庫中，我們的程序查找要麼返回一個指針，要麼返回一個空指針。空指針表示程序必須訪問數據庫才能加載對象，之後它將有一個指針。
想法： 所以我知道的唯一真正的技巧是二進制搜索。因此，在最糟糕的情況下，這意味着每次ID查找需要64次比較。
我的另一個想法是創建一個靜態空間分區，一棵樹，每個分支分裂成2個分支的權力，但只有一個合理的深度。在ID上使用一個按位運算符而不是模運算符來查找它在每個級別上屬於哪個分支。樹中的每個可能的分支總是存在，但是在某個深度它們停止並且仍然需要二分搜索，因爲確切數量的值仍然是未知的。
你有什麼想法？
這是散列圖的經典案例。首先，瞭解您實際上可以在任何時間激活多少個ID。 2^64是無稽之談，因爲即使只是保存這些ID和指向對象的指針的數據結構已經至少爲268'435'456 TB。現在，使用64位ID沒什麼問題，但是要弄清楚在任何時候你會有多少活動對象，選擇一個合理的數字，比如說5'000，並使用一個散列圖，例如10倍的對象數。如果你的負載因子足夠低，你的散列函數足夠好，你將得到一個分期的O（1）訪問時間。
即使活動對象的數量要大得多，例如100萬，仍然可以使用相對較小的哈希映射，例如大小爲10000的映射。映射的每個元素都指向ID的鏈接列表。這些列表使用簡單的線性搜索進行搜索。如果散列函數選擇得當，那麼ID將在散列映射中的10000個條目上均勻分佈（或接近）。因此散列表的每個條目將包含大約100個ID。線性搜索這樣的列表平均需要50比較。
在我的一個應用程序中，符號的數量大約是1000.我只用了簡單的線性搜索。性能分析表明90％的CPU時間用在表查找中。接下來我做了一個只有32個條目的哈希表 - >查表的CPU負載降到4％以下。問題解決了。擴大散列表對速度沒有明顯影響（小於4％），因此我將其保留爲32的大小。
結論：您可以使用小於元素數的散列表。這需要平均數量的比較（ID的總數/散列表的大小/ 2）選擇足夠大的散列表大小以將表查找的CPU時間減少到總CPU時間的很小部分。
+1指出了更高負載因素下的一個很好的解決方案。應該注意的是，鏈表需要額外增加一個間接級別，從而導致更多的緩存未命中。這是可用內存與性能要求之間的平衡。 – wich 2011-01-28 13:13:49
是的，現在我明白我的想法是多麼愚蠢是：或許ID空間允許2^64的可能性，但所有的對象永遠不會全部加載到內存中的所有方式。謝謝，現在我感到有些慚愧;（對不起， – Xilliah 2011-01-28 18:36:47