瞭解散列表

我知道一些散列表使用「存儲桶」，它是「條目」的鏈接列表。瞭解散列表

HashTable 
    -size //total possible buckets to use 
    -count // total buckets in use 
    -buckets //linked list of entries 

Entry 
    -key //key identifier 
    -value // the object you are storing for reference 
    -next //the next entry

爲了通過指數來獲得鬥，你必須調用：

myBucket = someHashTable[hashIntValue]

然後，直到你找到你正在尋找或空的一個，你可以重複條目的鏈接列表。

散列函數是否總是返回NUMBER % HashTable.size？這樣，你保持在極限內？那哈希函數應該如何工作？

來源

2011-01-12 joels

從數學上講，散列函數通常定義爲從希望存儲在散列表中的元素的Universe到範圍{0,1,2，...，numBuckets-1}的映射。這意味着從理論上講，使用mod運算符將某些整數散列碼映射到有效桶索引的範圍中並不需要任何條件。

但是，在實踐中，幾乎所有的程序員都會使用一個通用的哈希碼來產生均勻分佈的整數值，然後對其進行修改，使其適合於桶的範圍。這允許獨立於哈希表中使用的桶的數量來開發哈希代碼。

編輯：你的哈希表的描述被稱爲鏈哈希表並使用一種稱爲技術封閉處理。除了你所描述的哈希表之外，還有許多其他的哈希表實現。如果你很好奇 - 我希望你是！ :-) - 你可能想看看the Wikipedia page on the subject。

來源

2011-01-12 01:22:43 templatetypedef

沒有關於散列函數應該如何表現的預定義規則。您可以將所有值映射到索引0 - 一個完美有效的散列函數（表現不佳，但有效）。

當然，如果你的哈希函數返回一個超出相關數組索引範圍的值，它將無法正常工作。但是，這並不是說，你需要使用公式(number % TABLE_SIZE)

來源

2011-01-12 01:24:53

投下了這個答案的人可以提供解釋嗎？我會猜測他們不會。 – 2011-01-12 01:56:16

不，該表通常是一個條目數組。您不會迭代它直到找到相同的散列值，而是使用散列結果（或通常是哈希模數numBuckets）來直接索引到條目數組中。這給你O（1）的行爲（迭代將是O（n））。

當您試圖存儲具有相同散列結果的兩個不同對象（稱爲「散列衝突」）時，您必須找到某種方法來騰出空間。不同的實現方式在處理碰撞方面有所不同。您可以創建具有相同散列的所有對象的鏈接列表，或者使用一些重新散列來存儲在表格的不同條目中。

來源

2011-01-12 01:30:29 Javier

什麼是散列表？

它也被稱爲散列映射是用於實現關聯數組。它一個數據結構是能夠鍵映射到的值的結構。

它是如何工作的？

散列表使用散列函數來計算可以找到正確值的桶或槽陣列的索引。

請參閱下圖清楚說明。

enter image description here

優點：

在一個良好的尺寸哈希表，每個查找的平均成本爲獨立元件存儲在表中的數量。

許多哈希表設計還允許任意插入和刪除鍵值對。

在許多情況下，哈希表練得更有效超過搜索樹或任何其他查表結構。

缺點：當條目的數量非常少

哈希表是不能奏效的。（然而，在某些情況下，計算散列函數的高成本可以通過與鑰匙一起保存的散列值減輕）

用途：

它們被廣泛應用於各種電腦軟件特別是關聯數組，數據庫索引，緩存和集合。

來源

2013-08-24 10:26:03

回答

相關問題