Ric*_*ell 60
维基百科关于哈希表的文章提供了一个明显更好的解释和概述人们使用的不同哈希表方案,而不是我能够摆脱困境.事实上,阅读那篇文章可能比在这里提出问题更好.:)
那说......
链式哈希表索引到指向链表头部的指针数组.每个链接列表单元格都具有为其分配的密钥以及为该密钥插入的值.当您想要从其键中查找特定元素时,键的散列用于计算要遵循的链接列表,然后遍历该特定列表以查找您所追求的元素.如果哈希表中的多个键具有相同的哈希值,那么您将拥有包含多个元素的链接列表.
链式散列的缺点是必须遵循指针才能搜索链表.好处是,链式哈希表只会随着负载因子(哈希表中的元素与桶阵列长度的比率)的增加而线性变慢,即使它高于1.
开放寻址哈希表索引到指向(键,值)对的指针数组.您可以使用密钥的哈希值来确定数组中的哪个插槽首先查看.如果哈希表中的多个键具有相同的哈希值,那么您可以使用某种方案来决定另一个要查找的槽.例如,线性探测是指您选择一个之后的下一个插槽,然后是之后的下一个插槽,依此类推,直到找到与您正在寻找的键匹配的插槽,或者您打空插槽(在这种情况下,密钥不能在那里).
当负载因子较低时,开放寻址通常比链式散列更快,因为您不必遵循列表节点之间的指针.如果负载因子接近1,它会变得非常非常慢,因为在找到您要查找的密钥或空插槽之前,您最终通常必须搜索存储区阵列中的许多插槽.此外,哈希表中的元素永远不会超过桶阵列中的条目.
为了解决所有哈希表在其加载因子接近1时至少变得更慢(并且在某些情况下实际上完全中断)的事实,实际的哈希表实现使得桶阵列更大(通过分配新的桶阵列,并从中复制元素)当负载系数超过某个值(通常约为0.7)时,旧的那个进入新的,然后释放旧的.
上述所有内容都有很多变化.再次,请参阅维基百科文章,它确实非常好.
对于一个供其他人使用的图书馆,我强烈建议您进行试验.由于它们通常对性能至关重要,因此通常最好使用其他人已经仔细调整的哈希表的实现.有许多开源BSD,LGPL和GPL许可的哈希表实现.
例如,如果你正在使用GTK,那么你会发现GLib中有一个很好的哈希表.