爲什麼哈希表在存儲桶的數組上使用鏈表？

Question

當一個值被散列爲相同的值時，它將被添加到由散列值引用的鏈表中。爲什麼hashtables的實現使用數組上的鏈表作爲存儲桶？

是否因爲數組在初始化時具有預定的大小，所以當需要將過多元素添加到存儲桶時需要調整大小？

Answer 1

是的：一般來說，這是因爲一個數組有一個預定的大小。沒有要求您使用鏈接列表或數組作爲存儲區;一些狡猾的實現使用另一個哈希表，其中，然後使用鏈接列表或數組作爲其桶！

如果使用數組，則哈希表對每個數組元素都有一個預定的大小。每個可能的桶都被分配，並且你的哈希表可能很大。如果你有很多的內存，或者你希望有一個非常完整的散列表，那可能是好的。您可以通過持有指向數組的指針並根據需要進行分配來緩解這種情況。

數組可以被索引，所以你可以保持數組排序。然後，如果它變大，你可以做一個二進制搜索來找到你想要的密鑰。

如果您使用鏈接列表，則必須遍歷鏈表以線性查找匹配。這樣做效率不高，但它最大限度地減少了內存使用量。與所有數據結構問題一樣，您必須考慮您將擁有哪些訪問模式以及如何使用和填充結構;你想贏得什麼樣的折衷，哪些是你不太關心的？

Answer 2

他們沒有。

聲稱「哈希表的實現」使用鏈接列表是一種過度概括。 Java的確如此。許多其他語言不會。例如，Python使用開放散列，請參閱此問題的答案，How are Python's Built In Dictionaries Implemented

通常，通用API的設計者面臨着一個非常艱難的選擇，因爲他們不知道用戶的用例。有不同的實現選擇和不同的權衡，例如，如果你只添加元素但從不刪除，不同的選擇適用於經常變異的散列映射。等等。