哈希表是如何在流行语言中内部实现的?

您提到的经典“散列桶数组”在我看到的每个实现中都使用。

最具教育意义的版本之一是Tcl语言的哈希实现,在文件中 tcl/generic/tclHash.c . 文件中超过一半的行是注释 每件事 详细说明:分配、搜索、不同的哈希表类型、策略等。旁注:实现Tcl语言的代码是 真正地 可读的。

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

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

你可能还想看看 how Parrot implements basic hashes 与Perl 5实现相比,它的可怕程度要小得多。

至于“最有效、最实用”,请使用其他人的哈希库。看在上帝的份上,不要自己写一本供生产使用。现在已经有无数健壮高效的机器人了。

Lua 表使用 utterly ingenious implemenation 对于任意键,其行为类似于“bucket数组”,但如果使用连续整数作为键,则其表示形式和空间开销与数组相同。在实现中,每个表都有一个 散列部分 阵列部件 .

我觉得这太酷了:-)

Attractive Chaos 有一个 comparison of Hash Table Libraries update .

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

你也可以使用 open addressing 使用二次或多项式探测, as Python does .

Java HashMap , TreeMap 和 ConcurrentSkipListMap . 后两者保持钥匙的有序。

哈希图 使用您提到的在每个铲斗位置链接的标准技术。它使用相当弱的32位哈希代码,并将键存储在表中。数字配方作者还给出了一个散列表的示例(C),该散列表的结构基本上与Java的类似,但其中(a)从数组中分配存储桶列表的节点,以及(b)使用更强的64位散列代码,无需在表中存储键。

哈希表的用途是定时查找、添加和删除。就算法而言,所有操作的操作均为O(1)摊销。 然而,在使用树的情况下……对于平衡树,最坏情况下的操作时间将是O(logn)。N是节点数。但是,我们真的把散列实现为树吗?