c - 流行语言内部如何实现哈希表？

Question

有人可以解释一下 Python、Ruby 等流行语言如何在内部实现哈希表以进行符号查找吗？他们是使用经典的“带有链表的数组”方法，还是使用平衡树？

我需要一种简单（更少的 LOC）和快速的方法来索引用 C 编写的 DSL 中的符号。想知道其他人发现什么最有效和实用。

Answer 1

您提到的经典“哈希桶数组”在我见过的每个实现中都使用过。

最具教育意义的版本之一是 Tcl 语言中的哈希实现，位于文件tcl/generic/tclHash.c中。文件中超过一半的行是详细解释所有内容的注释：分配、搜索、不同的哈希表类型、策略等。旁注：实现 Tcl 语言的代码确实可读。

Answer 2

Perl 使用带有链表的数组来保存冲突。它有一个简单的启发式方法，可以根据需要自动将数组的大小加倍。还有一些代码可以在哈希之间共享密钥以节省一点内存。您可以在“HV”下的过时但仍然相关的Perl Illustrated Guts中阅读有关它的内容。如果你真的很喜欢冒险，你可以深入研究 hv.c。

散列算法过去非常简单，但现在使用 Unicode 可能要复杂得多。因为算法是可预测的，所以存在 DoS 攻击，攻击者生成的数据会导致哈希冲突。例如，作为 POST 数据发送到网站的大量密钥列表。Perl 程序可能会将其拆分并将其转储到一个散列中，然后将其全部推入一个桶中。结果哈希是 O(​​n) 而不是 O(1)。向服务器抛出大量 POST 请求，您可能会阻塞 CPU。结果，Perl 现在用一些随机数据扰乱了散列函数。

您可能还想看看Parrot 如何实现基本哈希，这比 Perl 5 实现要可怕得多。

至于“最高效实用”，就用别人的hash库吧。看在上帝的份上，不要自己写一个用于生产用途。那里已经有一个强大而高效的工具。

Answer 3

Lua表使用了一种非常巧妙的实现，对于任意键，它的行为类似于“桶数组”，但是如果您使用连续整数作为键，它具有与数组相同的表示和空间开销。在实现中，每个表都有一个散列部分和一个数组部分。

我认为这很酷:-)

Answer 4

平衡树有点违背哈希表的目的，因为哈希表可以在（摊销的）恒定时间内提供查找，而平衡树上的平均查找是 O(log(n))。

如果您有足够的存储桶，单独的链接（带有链表的数组）确实可以很好地工作，并且您的链表实现使用池分配器而不是 malloc() 单独从堆中处理每个节点。我发现它在适当调整后与任何其他技术一样具有性能，并且编写起来非常容易和快速。尝试从源数据的 1/8 开始。

您还可以像 Python 那样使用具有二次或多项式探测的开放寻址。

Answer 5

Attractive Chaos有一个Hash Table Libraries 的比较和一个更新。源代码是可用的，它是 C 和 C++

Answer 6

如果您可以阅读Java，您可能想查看其各种地图实现的源代码，特别HashMap是TreeMap和ConcurrentSkipListMap。后两者保持键有序。

JavaHashMap使用您提到的在每个存储桶位置链接的标准技术。它使用相当弱的 32 位哈希码并将键存储在表中。Numerical Recipes 作者还给出了一个哈希表的示例（用 C 语言），其结构基本上类似于 Java，但其中 (a) 您从数组中分配桶列表的节点，并且 (b) 您使用更强大的 64 位哈希编码并省去在表中存储密钥。

Answer 7

Crashworks 的意思是……

哈希表的目的是恒定时间查找、添加和删除。就算法而言，所有操作的操作都是 O(1) 摊销的。而如果您使用树...对于平衡树，最坏情况下的操作时间将是 O(log n)。N 是节点数。但是，我们真的将哈希实现为树吗？