C：在散列表中存儲多達一百萬個條目

我正在研究效率至關重要的項目。哈希表將非常有用，因爲我需要根據一個密鑰輕鬆查找節點的內存地址。我預見到的唯一問題是這個散列表需要處理多達100萬個條目。據我所知，通常哈希表桶是一個鏈表，以便他們可以處理同一個桶中的多個條目。在我看來，有一百萬條這些列表會太慢。執行這樣的事情的常見方式是什麼？也許換一個標準的鏈表作爲跳過列表？C：在散列表中存儲多達一百萬個條目

來源

2011-07-25 blcArmadillo

如果你想用萬個條目一個哈希表，通常你至少有2個百萬桶。我不記得所有的統計數據（關鍵詞是「生日悖論」），但絕大多數的桶都會有零個或一個項目。原則上，您可以將非常不利，並將所有物品放在一個桶中 - 但您必須比那些每隔一天都會被閃電擊中的人更加不走運。

對於增長的哈希表，正常的技巧是增長一個不變的百分比 - 通常的教科書案例是通過加倍散列表大小來增長。只要散列表中的項數達到散列表大小的一定比例，就可以這樣做，而不管實際使用多少個散列。這給預計表現O（1）的插入，刪除和搜索。

散列表的每個桶中的鏈表只是一種處理衝突的方式 - 在每個操作意義上都不太可能，但是在重要散列表的使用期限內，它們會發生 - 特別是作爲哈希表獲得超過半滿。

鏈表不是處理碰撞的唯一方式 - 關於這個話題有大量的知識。 Walter Bright（D編程語言的開發人員）主張使用二叉樹而不是鏈表，聲稱他的Dscript從這個設計選擇中相對於Javascript獲得了顯着的性能提升。

當我問我的時候，他使用了簡單（不平衡）的二叉樹，所以最壞情況下的性能和鏈表一樣，但我猜想的關鍵點是二叉樹處理代碼很簡單，哈希表本身使得構建大型不平衡樹木的可能性非常小。

原則上，您可以輕鬆使用treaps，紅黑樹或AVL樹。一個有趣的選項可能是使用張角樹進行碰撞處理。但總的來說，這對少數圖書館設計師和一些真正的迷戀者來說是一個小問題。

來源

2011-07-25 18:53:05 Steve314

處理碰撞的另一種方法是布穀鳥哈希。 – caf

這個理論似乎消除了一對密鑰碰撞兩個哈希的可能性，或者兩個可能位置的一個密鑰由於碰撞而不可用。可能意味着我沒有充分研究它。之前我看過雙哈希方案，但在五分鐘前閱讀您的評論之前沒有聽到「杜鵑哈希」這個術語，所以我很容易錯過一兩個特定的技巧。 – Steve314

@ Steve314那麼這很容易遞歸處理（再次替換對象的位置和重複），我假設你知道;）我同意我沒有看到他們使用什麼魔術技巧來確保不斷查找（至少不是這些技巧如何不適用於鏈接的hashmap） – Voo

您可以在單個「桶」中使用Tree而不是List。（AVL或類似的）

編輯：好吧，跳過列表也可以。（而且似乎更快） - O（log n）就是你的目標。

來源

2011-07-25 18:40:43 sleeplessnerd

嚴格來說，哈希表已經給你O（1）的期望。如果你正在尋找一個漸進式的改進，你需要一個保證均衡的樹來進行衝突處理 - 一些最壞的情況O（log n），以便哈希表本身可以分攤最壞情況的O（log n）操作，而不是攤銷最差的 - case O（n）。因爲跳過列表是隨機的，所以它不會提供這種保證 - 儘管它在實踐中可能會提高性能。 – Steve314

O（log n）表示一個桶中的結構用於碰撞處理。 – sleeplessnerd

如果每個桶列表中有多個條目，那麼您將失去散列表的所有優點。將散列表縮放到數百萬個條目的常用方法是使主散列數組可調整大小，因此即使有數百萬個條目，存儲區列表仍然很短。

來源

2011-07-25 18:41:38 zwol

我不得不想象調整一個哈希表是一個相當昂貴的操作。有沒有比遍歷每個條目更好的方法？ – blcArmadillo

@blcArmadillo：你不必調整它的大小，它的大小應該在創建時決定。 – ruslik

@blcArmadillo - 如果您通過例如調整表格大小來調整表格的大小，加倍，這是非常便宜的。調整表的大小是O（n），但很少。基本上，對於每個插入，您「收取」一個額外的單位信用額度來支付調整大小 - 每個操作只收取固定金額，並且調整大小（發生時）從「保存時間」支付。 – Steve314

不知道這是否會幫助你或沒有，但也許：http://memcached.org/

來源

2011-07-25 18:42:27

關於那個形象的東西...它會給我做惡夢。 – Steve314

條目總數並不重要，只有每個存儲區的平均條目數（N /散列大小）。使用具有較大域的散列函數（例如，20位或甚至更大）來確保。

當然，這會佔用更多的內存，但就是這樣，這是一種常見的內存vs速度折衷。

來源

2011-07-25 18:53:35 ruslik

如果您的密鑰具有正常分佈（這是一個非常大的IF），那麼希望在哈希表中插入散列表中的所有桶的預期數量是M * logM（自然對數，到基數e），其中M是桶的數量。

很驚訝無法在網上輕鬆找到它！

我在my blog上發佈了相同的派生，並使用rand（）對其進行了驗證，它似乎是一個相當不錯的估計。

來源

2012-08-02 13:41:44 Arvind

C：在散列表中存儲多達一百萬個條目

回答

相關問題