Jim*_*Jim 5 algorithm performance hashtable data-structures
我想知道为什么许多语言（Java、C++、Python、Perl 等）使用链表而不是数组来实现哈希表以避免冲突？
我的意思是，我们应该使用数组，而不是链表桶。
如果担心的是数组的大小，那么这意味着我们有太多冲突，因此我们已经在哈希函数上遇到了问题，而不是我们解决冲突的方式。我误解了什么吗？
策略1
使用（小）数组，一旦发生冲突，这些数组就会被实例化并随后填充。1.堆操作用于分配数组，那么空间多了N-1。如果该存储桶不再发生冲突，则条目的 N-1 容量将被浪费。列表获胜，如果冲突很少，则不会仅仅为了桶上出现更多溢出的可能性而分配多余的内存。移除物品的成本也更高。要么在数组中标记已删除的点，要么将其后面的内容移到前面。如果数组已满怎么办？数组的链接列表或调整数组的大小？
使用数组的一个潜在好处是进行排序插入，然后在检索时进行二分搜索。链表方法无法与之竞争。但这是否有效取决于写入/检索比率。书写频率越低，回报就越大。
策略2
使用列表。你为你所得到的付出代价。1 次碰撞 = 1 次堆操作。没有急切地假设（以及在记忆方面付出的代价）“还会有更多”。碰撞列表内的线性搜索。删除更便宜。（这里不算free()）。使用数组而不是列表的一个主要动机是减少堆操作的数量。有趣的是，普遍的假设似乎是它们很便宜。但实际上没有多少人知道分配需要多少时间，例如遍历列表寻找匹配项。
策略3
既不使用数组也不使用列表，而是将哈希表中的溢出条目存储在另一个位置。上次我在这里提到这一点时，我有点皱眉。优点：0 内存分配。如果桌子的填充等级确实较低且碰撞很少，则可能效果最好。
概括
确实有很多选择和权衡可供选择。通用哈希表实现（例如标准库中的实现）不能对写入/读取比率、哈希键质量、用例等做出任何假设。另一方面，如果哈希表应用程序的所有这些特征都是已知的（并且如果它值得付出努力），很可能创建一个哈希表的优化实现，该实现是针对应用程序所需的权衡集而定制的。