如何在流行语言内部实现哈希表？
有人可以说一下流行语言如Python，Ruby如何在内部实现哈希表进行符号查找？ 他们使用经典的“带链接列表的数组”方法，还是使用平衡树？
我需要一个简单的（更少的LOC）和快速的方法来索引用C编写的DSL中的符号。想知道其他人发现的最有效和实用的东西。
您提到的经典“哈希桶arrays”用于我见过的每个实现中。
最具教育意义的版本之一是Tcl语言中的哈希实现，文件为tcl / generic / tclHash.c 。 文件中超过一半的行是详细解释所有内容的注释：分配，搜索，不同的哈希表类型，策略等。旁注：实现Tcl语言的代码实际上是可读的。
Perl使用带有链表的数组来保存冲突。 它有一个简单的启发式，可以根据需要自动加倍数组的大小。 还有代码在哈希之间共享密钥以节省一点内存。 您可以在“HV”下的过时但相关的Perl Illustrated Guts中阅读它。 如果你真的喜欢冒险，你可以深入了解hv.c。
哈希算法过去非常简单，但现在使用Unicode可能要复杂得多。 由于该算法是可预测的，因此存在DoS攻击，攻击者生成的数据会导致哈希冲突。 例如，作为POST数据发送到网站的大量密钥列表。 Perl程序可能会将其拆分并将其转储为哈希值，然后将其全部推入一个桶中。 得到的散列是O（n）而不是O（1）。 在服务器上抛出大量POST请求，可能会阻塞CPU。 因此，Perl现在用一些随机数据扰乱哈希函数。
您还可能想看看Parrot如何实现基本哈希 ，它比Perl 5实现明显不那么可怕。
至于“最有效和最实用”，请使用别人的哈希库。 为了上帝的缘故，不要自己写一个用于生产用途。 那里已经有很多强大而高效的产品。
Lua表使用完全巧妙的实现 ，任意键的行为类似于“数组桶”，但如果使用连续的整数作为键，则它具有与数组相同的表示和空间开销。 在实现中，每个表都有一个散列部分和一个数组部分 。
我认为这很酷:-)
有吸引力的混沌有哈希表库和更新的比较 。 源代码可用，它使用C和C ++
平衡树排除了哈希表的目的，因为哈希表可以提供（摊销）常量时间的查找，而平衡树上的平均查找是O（log（n））。
如果你有足够的存储桶，那么单独的链接（带有链表的数组）确实非常有效，并且你的链表实现使用池分配器而不是malloc（）来自堆中的每个节点。 我发现它在适当调整时与其他任何技术一样高效，并且编写起来非常简单快捷。 尝试从源数据的1/8开始。
您也可以像Python那样使用二次或多项式探测的开放寻址 。
如果您可以阅读Java ，您可能需要查看其各种地图实现的源代码，特别是HashMap ， TreeMap和ConcurrentSkipListMap 。 后两者保持按键排序。
Java的HashMap使用您在每个桶位置链接的标准技术。 它使用相当弱的32位哈希码并将密钥存储在表中。 Numerical Recipes的作者还提供了一个示例（在C中）的哈希表基本上像Java一样，但其中（a）你从一个数组中分配桶列表的节点，（b）你使用更强大的64位哈希代码并省去在表中存储密钥。
Crashworks的意思是……
哈希表的目的是持续时间查找，添加和删除。 在算法方面，所有操作的操作都是O（1）摊销。 而如果你使用树…最坏的情况下操作时间将是平衡树的O（log n）。 N是节点数。 但是，我们真的有哈希实现为树吗？