流行编程语言中哈希表的内部实现方式是怎样的？

Question

流行编程语言中哈希表的内部实现方式是怎样的？

chashtable

26

请问有人能够解释一下像Python、Ruby这样的流行编程语言是如何实现哈希表进行符号查找的吗？它们使用经典的“数组和链表”方法，还是使用平衡树？

我需要一种简单（少量代码行）且快速的方法，用于索引用C语言编写的DSL中的符号。想知道其他人发现什么最有效和实用。

- CDR

4

也许你想问“地图是如何实现的…”，因为哈希表并不是实现地图的唯一方式！ - Artelius

好的评论。但问题是我已经基于符号的计算哈希值构建了基础工作。顺便问一下，除了哈希表，还有哪些其他方式实现映射呢？我以为每个人都在使用哈希表。 - CDR

1

有时地图也是由二叉树构建的。当键类型不可哈希化或者您想要保留映射中数据的某种顺序（以便可以从A到Z迭代）时，通常会使用它。 - Crashworks

7个回答

12

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

哈希算法曾经非常简单，但现在可能更加复杂了，因为涉及Unicode。由于算法是可预测的，因此存在DoS攻击，攻击者生成会导致哈希冲突的数据。例如，将大量密钥作为POST数据发送到网站。Perl程序可能会将其拆分并转储到哈希表中，然后将其全部推入一个桶中。结果哈希的复杂度为O(n)，而不是O(1)。向服务器发送大量POST请求，可能会使CPU堵塞。因此，Perl现在使用一些随机数据扰动哈希函数。

您也可以查看如何实现基本哈希表，这比Perl 5的实现要简单得多。

关于“最有效和实用”的问题，使用其他人的哈希库。千万不要为了生产使用而自己编写。已经有成千上万个健壮且高效的哈希库存在。

- Schwern

8

Lua表使用一个极其巧妙的实现，对于任意键值都表现为“桶数组”，但如果您使用连续的整数作为键，则具有与数组相同的表示和空间开销。在实现中，每个表都有一个哈希部分和一个数组部分。

我认为这非常酷 :-)

- Norman Ramsey

4

平衡树有点违背哈希表的初衷，因为哈希表可以在（摊还）常数时间内提供查找，而平衡树的平均查找时间是O(log(n))。

如果您有足够的桶，并且您的链表实现使用池分配器而不是从堆中单独malloc()每个节点，那么分离链接（数组与链表）确实非常有效。我发现当正确调整时，它几乎和任何其他技术一样高效，并且编写起来非常容易快捷。尝试从源数据开始使用1/8作为桶的数量。

您还可以使用二次或多项式探测的开放寻址，就像Python一样。

- Crashworks

对数时间复杂度常数？ - Nick Dandoulakis

1

@tydok - "打破初衷"意味着未能达到其他解决方案所达到的任何目标，因此它意味着“不如”，而不是“比...更好”。 - Daniel Earwicker

4

Attractive Chaos 进行了一次哈希表库比较并发布了一篇更新文章。源代码以C和C++编写。

- Lear

2

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

Java的HashMap在每个桶位置使用链式技术。它使用相当弱的32位哈希码并将键存储在表中。Numerical Recipes的作者还给出了一个例子（用C编写）：一个哈希表本质上结构类似于Java的哈希表，但在这个哈希表中，（a）您从数组中分配桶列表的节点，（b）使用更强的64位哈希码，并且不需要在表中存储键。

- Neil Coffey

在Java中，TreeMap是基于红黑树实现的，而ConcurrentSkipListMap则是基于跳表实现的。 - coderz

1

Crashworks 的意思是……

哈希表的目的是实现常数时间的查找、添加和删除。在算法方面，所有操作的时间复杂度都是 O(1) 摊销的。而如果使用树，则平衡树的最坏情况操作时间为 O(log n)，其中 n 是节点数。但是，我们真的将哈希实现为树吗？

- Kapil D

谢谢指出我的不清晰--我已经修正了我的回答。 - Crashworks

3

以树形结构实现的哈希表是一种具有哈希表API的树形结构。 - user82238

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- zvr · Accepted Answer

我见过的每一个实现都使用了你提到的经典的“哈希桶数组”。

其中最有教育意义的版本是Tcl语言中的哈希实现，在文件tcl/generic/tclHash.c中。该文件中超过一半的行都是解释详细说明的注释：分配、搜索、不同的哈希表类型、策略等等。另外，Tcl语言的代码实现真的很易读。