鏈接在哈希表

Question

當我們有鏈接哈希表：

我只是想知道，如果保持的列表中每個鍵，以便將影響搜索，插入和哈希表中刪除的運行時間？

Answer 1

是的，當然。通常引用的散列表的O（1）假設完美的散列 - 其中沒有兩個不相同的條目解析爲相同的散列。

在實踐中，這將不會是這樣。你會一直有（爲了一個足夠大的數據集）碰撞。無論您是使用鏈接還是其他碰撞解決方法，碰撞都意味着查找時會有更多工作。

這就是爲什麼要選擇具有良好的設計/寫一個好的哈希函數這是非常非常重要的，有良好的匹配數據，你會使用爲您的哈希表的關鍵。在實踐中，不同類型的數據會使用不同的散列函數更好地散列。

Answer 2

可以想像，你選擇你的哈希算法和地圖的大小，以減輕碰撞，你會在第一時間得到的數字。此時，您應該在任何位置都有一個非常小的列表（理想情況下是一個或兩個元素），因此在鏈中維護排序結構的額外工作肯定不僅僅是迭代該存儲桶中的少量項目。

Answer 3

從理論上講：是的，因爲在一般情況下，你只需要步行半鏈找到，如果一個項目在連鎖與否。

在實踐中，有可能是沒有太大的區別，因爲鏈通常很短，而增加了代碼的複雜性也將花費一定的週期，主要表現在「插入」情況。

順便說一句：在大多數情況下的時隙數大於所述散列值的「密鑰空間」小得多。如果您能夠承擔該空間，則將散列值存儲在鏈節點中將節省重新計算每一跳上的散列值，並且將避免大部分最終比較。這當然是一個空間< - >時間折衷。如：

struct hashnode **this; 
for (this=& table[slot] ; *this; this = &(*this)->link) { 
    if ((*this)->hash != the_hash) continue; 
    if (compare ((*this)->payload , the_value)) continue; 
    break; 
} 
/* at this point "this" points to the pointer that points to the wanted element, 
    or to the NULL-pointer where it should be inserted. 

    For the sorted-list example, you should instead break out of the loop 
    if the compare function returns > 0, and handle that special case here. 

*/