我正在嘗試確定要爲以下內容使用哪種數據結構。針對不同數據結構的速度/內存使用情況估計
假設我可能有1000萬個密鑰包含指向包含某些數據的唯一對象的指針。
鍵是UUID認爲它們是16字節的二進制數組。 UUID是使用高質量的隨機數生成器生成的。
我一直在考慮以下內容，但想知道速度和內存消耗方面的優缺點。一些公平的估計，在64位平臺上的最好/最差/平均情況會很好。
我需要能夠插入幾乎無限的項目。
二叉樹 哈希表 基數樹（位基或2位多路）
我需要這些操作是：插入，刪除，搜索
我喜歡基數樹的主意但它被證明是最難實施的，而且我還沒有找到適合我實施的商業產品。
簡短的回答
哈希表可能是最好的爲你的情況。
速度
哈希表（std::unordered_map）將ø（1）如果散列是恆定的。在你的情況下，O（1）成立，因爲你甚至不需要散列—只使用隨機UUID的低32位應該足夠好。查找的成本與一個或兩個指針間接相似。
二叉樹（std::map）將Ø（日誌 ñ），所以10萬個項目，你將有24間的比較和24個電位高速緩存未命中。即使對於n = 4,000它將使用12個比較，所以它很快變得比散列表差得多。
基數樹將Ø（ķ），那麼你將有一個最大的ķ比較和ķ潛在的高速緩存未命中。在極不可能的情況下，基數樹將像散列表一樣快。更糟糕的是（假設k =一個合理的16，對於一個256樹的樹），它的性能會比二叉樹好，但比散列表差得多。
所以如果速度是最重要的，使用哈希表。
架空
如果滿一個典型的哈希表將每個項目約1 – 3個指針開銷。如果沒有滿，你可能會浪費每個空插槽1個空間指針。你應該能夠保持它接近完整，同時仍然比二叉樹快，因爲你有一個非常隨機的密鑰，但爲了獲得最大的速度，你當然想要給它足夠的空間。對於32位機器上的1000萬個項目，預計整個表的開銷爲114MiB。對於半滿桌，預計爲153MiB。
紅黑樹，最常見的std::map實現，將有3個指針+ 1布爾每個項目。一些實現利用指針對齊來將bool與其中一個指針合併。根據實現以及散列表的完整程度，紅黑樹可能會略微降低開銷。預計114 – 153MiB。
一個基數樹將有每個項目1個指針和每個空白插槽1個指針。不幸的是，我認爲這樣大的隨機密鑰會導致你在樹的邊緣有很多空槽，所以它可能使用比上述任何一個更多的內存。減少k可以降低此開銷，但同樣會降低性能。
如果最小開銷很重要，請使用散列表或二叉樹。如果它是優先級，請使用完整的哈希表。
請注意，std::unordered_map不允許您控制何時調整大小，因此獲得滿滿將會很困難。 Boost Intrusive有一個非常不錯的unordered_map實現，可以讓你直接控制這個和其他許多事情。
我會先嚐試std::map或std::unordered_map。
他們已經有很多聰明的人在多年的發展和改進。
你有什麼理由不能使用std::map或std::unordered_map？
我目前使用std :: map。我認爲gcc版本在下面使用了紅黑樹。只是想看看它如何與其他記憶和速度相比。 – Matt
IMO基數樹不難實現。但是，一個簡單的哈希表就足夠了。只需分配2^16個對象列表的數組，並使用UUID的前2個字節來索引要在其中插入對象的列表。然後你可以搜索約160個項目的列表。或者，分配20M指針數組。要存儲一個對象，只需在0-20M範圍內對UUID進行散列，找到第一個空閒（NULL）指針並將其存儲在那裏。搜索意味着從散列值走到第一個NULL值。刪除也很簡單....嘗試閱讀http://en.wikipedia.org/wiki/Hash_function
不是我一直在尋找的答案，但你給了我一個想法，所以非常感謝。 – Matt
我只是做了一個快速計算，我認爲你可能會用標準樹很好。 1000萬個密鑰是一個合理的數字。使用一個平衡樹，將只有23個節點的深度進行檢查。有了基數樹，你實際上有一個128位密鑰的關鍵長度來檢查。
你的鑰匙也可以代表和比較非常便宜。使用兩個64位值的元組（boost或0x）來獲得相同的128位密鑰。元組排序足以在地圖中使用。如同比較，密鑰複製因此便宜。按原樣比較整數可能比爲基數深度搜索進行掩碼和基於比特的比較要便宜。
所以在這種情況下，地圖可能工作得很好。
*我會避免unordered_map這裏，因爲UUID往往是結構化數據。這意味着標準哈希程序（對於哈希映射）很容易在性能上很差。*
更新：
由於您使用隨機UUID的哈希可能就好了 - 雖然這樣的大哈希表有顯著的內存開銷保持效率。另外，給定完全隨機的UUIDs，基數可能最終與樹具有相同的平衡（因爲密鑰分配完全均勻）。因此，您甚至可能無法保存步驟，仍然會導致位操作的開銷。但是有很多方法可以專門化和優化基數樹，所以很難說明它是否會更快或者總是更慢。
UUID是普通UUID還是自定義算法？特別是，他們是否遵循基於前綴的模式，或者它們基本上是隨機的？這將決定基樹是否是一個好選擇。 –
他們是版本4 uuid的。除了幾位以外完全是隨機的。 – Matt