为什么我们要使用链表来解决哈希表中的冲突？

Question

我想知道为什么许多语言(Java、C++、Python、Perl等)使用链表而不是数组来实现哈希表以避免冲突？

我的意思是，我们应该使用数组，而不是链表桶。

如果关注的是数组的大小，那么这意味着我们有太多的冲突，所以我们已经有了哈希函数的问题，而不是我们解决冲突的方式。我是不是误解了什么？

Answer 1

我的意思是，我们应该使用数组而不是链表的桶。

每件事的利弊都取决于许多因素。

数组最大的两个问题是：

1. changing容量涉及将所有 content复制到您必须从中选择的另一个内存区域
2. ：

a) Element*数组，在表操作期间添加一个额外的间接，以及每个具有相关堆管理开销的非空桶的一个额外内存分配

b) Element数组，使得预先存在的Element的iterators/pointers/references被其他节点上的一些操作(例如insert)无效(链表方法-或上面的2a -不需要使这些无效)

...will忽略了几个较小的关于数组间接性的设计选择……

从1开始减少拷贝的实用方法包括保留多余的容量(即，当前未使用的内存用于预期的或已经擦除的元素)，如果sizeof(Element)比sizeof(Element*)大得多，您将被推向Element*s数组(具有"2a“问题)，而不是Element[]s/2b。

还有一些其他的答案声称在数组中擦除比链表更昂贵，但事实往往相反:搜索连续的Element比扫描链表更快(代码中的步骤更少，对缓存更友好)，一旦找到，您可以将最后一个数组Element或Element*复制到要擦除的数组上，然后减小大小。

如果关注的是数组的大小，那么这意味着我们有太多的冲突，所以我们已经有了哈希函数的问题，而不是我们解决冲突的方式。我是不是误解了什么？

为了回答这个问题，让我们看看一个很棒的哈希函数会发生什么。使用加密强度散列将一百万个元素打包到一百万个存储桶中，我的程序运行了几次，计算0，1，2等元素散列到的存储桶的数量...

0=367790 1=367843 2=184192 3=61200 4=15370 5=3035 6=486 7=71 8=11 9=2
0=367664 1=367788 2=184377 3=61424 4=15231 5=2933 6=497 7=75 8=10 10=1
0=367717 1=368151 2=183837 3=61328 4=15300 5=3104 6=486 7=64 8=10 9=3

如果我们将其增加到1亿个元素-仍然使用负载率1.0：

0=36787653 1=36788486 2=18394273 3=6130573 4=1532728 5=306937 6=51005 7=7264 8=968 9=101 10=11 11=1

我们可以看到比率是相当稳定的。即使使用加载因子1.0 (C++的unordered_set和-map的默认最大值)，也可以预期36.8%的存储桶为空，另外36.8%处理一个Element，18.4%2个元素，依此类推。对于任何给定的数组调整大小逻辑，您可以很容易地了解它需要调整大小(以及可能复制元素)的频率。您是对的，它看起来并不糟糕，如果您正在进行大量查找或迭代，对于这种理想化的加密散列情况，它可能比链表更好。

但是，高质量的散列在CPU时间上相对昂贵，因此支持散列函数的通用散列表通常非常弱:例如，对于std::hash<int>的C++标准库实现来说，返回它们的参数是非常常见的，而MS Visual C++的std::hash<std::string>选择沿string均匀间隔的10个字符来并入散列值，而不管string有多长。

显然，实现的经验是，这种弱但快速的哈希函数和链表(或树)的组合来处理更大的冲突倾向，对于日常的键和要求，平均来说工作得更快，并且不会出现令人讨厌的糟糕性能的用户对抗表现。

Answer 2

策略1

使用(小)数组，一旦发生冲突，这些数组将被实例化并随后填充。1个堆操作用于数组的分配，然后为N-1更多的空间。如果该存储桶再也没有发生冲突，则N-1个条目的容量将被浪费。列表获胜，如果冲突很少，则不会分配多余的内存，只是为了在存储桶上有更多溢出的可能性。删除项目的成本也更高。要么在阵列中标记删除的点，要么将其后面的内容移到前面。如果数组已满怎么办？数组的链表还是调整数组的大小？

使用数组的一个潜在好处是执行排序插入，然后在检索时进行二进制搜索。链表方法无法与之竞争。但这是否有回报取决于写入/检索比率。写作的频率越低，回报就越大。

策略2

使用列表。你要为你得到的东西付出代价。1个冲突=1个堆操作。没有急切的假设(以及在内存方面付出的代价)，即“还会有更多”。在冲突列表中进行线性搜索。更便宜的删除。(这里不包括free() )。考虑数组而不是列表的一个主要动机是减少堆操作的数量。有趣的是，一般的假设似乎是它们很便宜。但实际上没有多少人会知道与遍历列表寻找匹配相比，分配需要多少时间。

策略3

既不使用数组，也不使用列表，而是将溢出条目存储在哈希表中的另一个位置。上一次我在这里提到这一点时，我有点不以为然。优点:0内存分配。如果表格的填充度确实很低，并且只有很少的碰撞，则可能效果最好。

摘要

确实有很多选择和权衡可供选择。诸如标准库中的那些通用哈希表实现不能做出关于写/读比率、哈希键的质量、用例等的任何假设。另一方面，如果哈希表应用程序的所有这些特征都是已知的(并且如果这是值得的)，则很有可能创建针对应用程序所需的一组折衷而定制的哈希表的优化实现。

Answer 3

原因是，这些列表的预期长度很小，在绝大多数情况下只有零个、一个或两个条目。然而，在非常糟糕的散列函数的最坏情况下，这些列表也可能变得任意长。即使这种最坏的情况不是针对哈希表进行优化的情况，它们仍然需要能够优雅地处理它。

现在，对于基于数组的方法，您需要设置最小数组大小。而且，如果初始数组大小不是零，那么由于所有的空列表，您已经有了很大的空间开销。2的最小数组大小意味着您浪费了一半的空间。当数组变满时，你需要实现逻辑来重新分配它们，因为你不能对列表长度设置上限，你需要能够处理最坏的情况。

在这些约束下，基于列表的方法要高效得多:它只有节点对象的分配开销，大多数访问与基于数组的方法具有相同的间接量，并且更容易编写。

我并不是说不可能写一个基于数组的实现，但它比基于列表的方法复杂得多，效率也低得多。