哈希表和桶陣列

Question

我讀到一個哈希表中，我們有一個桶陣列，但我不明白什麼桶數組包含。

它是否包含哈希指數？條目（鍵/值對）？都？

該圖像，對我來說，不是很清楚：

^{（reference）}

所以，這是一個鬥陣？

Answer 1

在實際中，已經計算（通過散列密鑰）計算的條目的鏈接列表以進入該存儲桶。

Answer 2

在HashTable中有大部分時間衝突。那就是當不同的元素具有相同的散列值時。具有相同散列值的元素存儲在一個存儲桶中。因此，對於每個散列值，您都有一個存儲桶，其中包含具有該散列值的所有元素。

Answer 3

桶數組中涉及的內容很大程度上取決於散列表中存儲的內容以及衝突解決策略。

當您使用linear probing或其他open addressing technique，你的水桶表存儲鍵或鍵值對，這取決於您使用哈希表^*的。

當您使用separate chaining technique時，您的存儲區數組存儲密鑰對和鏈接結構的標題（例如鏈接列表）。

要記住關於桶數組的重要事項是它建立了一個哈希碼和一組零個或多個鍵之間的映射。換句話說，給定一個散列碼和一個桶數組，你可以在常量時間內找出與這個散列碼相關聯的可能鍵（枚舉候選鍵可能是線性的，但找到第一個鍵需要是常數以便滿足散列表的平均等待時間插入和恆定時間搜索的性能保證）。

^*如果您的哈希表我們用於檢查成員資格（即它代表一組密鑰），那麼存儲區數組存儲密鑰;否則，它存儲鍵值對。

Answer 4

數組索引大多等同於散列值（好吧，散列值mod是數組大小），所以根本不需要將數組存儲在數組中。

至於什麼實際的數組包含有幾個選項：

• 如果我們使用separate chaining：

  • 到所有具有元素的鏈接列表的引用那個散列值。因此：

    LinkedList<E>[] 
    

  • 鏈接列表節點（即，鏈接列表的頭部） - 類似於第一個選項，但是我們只需從鏈接列表中直接開始，而不必通過單獨引用它來浪費空間。所以：

    LinkedListNode<E>[] 
    

• 如果我們使用open addressing，我們只是存儲實際元素。如果有另一個具有相同散列值的元素，我們使用一些可重現的技術爲它找到一個位置（例如，我們只是嘗試下一個位置）。所以：

  E[] 
  

• 可能有一些其他的選擇，但以上是最知名的，具有獨立，鏈接是最流行的（據我所知）

* I」假設熟悉泛型和Java/C＃/ C++語法 - E這裏只是我們存儲的元素的類型，LinkedList<E>表示存儲E類型的元素的LinkedList。 X[]是一個包含X類型元素的數組。

Answer 5

存儲桶是鍵值對的鏈接列表。散列索引是告訴「哪個桶」的一個 ，並且鍵值對中的「鍵」是告訴「該桶中的哪個條目」的那個。 也退房 hashing in Java -- structure & access time，我有蜜蜂在那裏告訴更多的細節。