使用链接列表的队列与使用数组进行哈希表桶的队列的好处？

Question

我知道两种实现队列的方法，使用链接列表或使用数组。在哈希表中，当桶超过条目限制时，需要重新散列哈希表时，我应该使用哪一种方法来生成桶。我是否有可能使用其他数据结构获得O(1) -队列和去队列以及索引？

使用数组，我可以让桶大小提高到更高的值，因为数组中的索引允许我对键使用二进制搜索(按排序顺序插入)。考虑一下，如果桶大小变成1000，搜索变成ln( 1000 ) vs 1000。insert操作变成O(n)，但是查找比Insert更常见。

使用链表，我得到O(1)插入，删除，但我也得到O(n)。

我的问题是，我是否能从使用其他数据结构中获得好处，或者使用这些数据结构的好处明显大于其他数据结构？

Answer 1

我觉得你问错问题了。与其担心如何处理水桶中的大量物品，还不如关注为什么水桶已经装满了。

哈希表假定有两件事：

1. 您已经选择了一个散列函数，它在桶中提供了一个很好的项分布。
2. 你不会让负载系数太高的。一个好的哈希表实现将提供相当不错的性能，负载系数高达0.8，但除此之外，性能急剧下降。我认为大多数实现都喜欢将负载因子保持在0.7以下。因此，如果哈希表中的项数超过表容量的70%，则应考虑增加容量。当负载因子超过某个阈值时，大多数哈希表实现会自动增加容量。

当您选择使用哈希表时，您将承担确保这两种情况都成立的责任。如果您选择了一个糟糕的散列函数，或者如果您超过了设计的负载因子，那么性能将受到影响，再多的优化桶结构也不会对您有所帮助。

存储桶列表结构的实现不应该重要，因为您的存储桶不应该大到足以产生性能差异。一个简单的链表提供了O(1)插入和O(k)查找(其中k是桶中的项目数)。但是k不应该超过2或3，所以使用渐近更有效的数据结构是没有意义的。

无论如何实现存储桶，当您超过哈希表的容量时(如果哈希表实现自动调整大小，则需要支付调整O(n)大小的代价)。

Answer 2

在为哈希表实现桶时，应该使用链接列表，因为它们是可调整大小的。您需要在散列映射中的桶中执行的唯一操作是遍历和追加新项，这两个操作都可以在每个元素的O(1)中完成。当使用数组时，会不必要地或太少地分配内存，因为不能调整它的大小。此外，您不应该使用队列，您最好只使用一个普通的链接列表。