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

有人可以说一下流行语言如Python,Ruby如何在内部实现哈希表进行符号查找？他们使用经典的"带链接列表的数组"方法,还是使用平衡树？

我需要一个简单的(更少的LOC)和快速的方法来索引用C编写的DSL中的符号.想知道其他人发现的最有效和实用的东西.

您提到的经典"哈希桶阵列"用于我见过的每个实现中.

其中一个最具教育意义的版本是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表使用完全巧妙的实现,任意键的行为类似于"数组桶",但如果使用连续的整数作为键,它具有与数组相同的表示和空间开销.在实现中,每个表都有一个散列部分和一个数组部分.

我认为这很酷:-)