标准库如何在实践中实现哈希表？

Question

一些编程语言(如python、Java和C++11 )将哈希表(虽然有时以不同的名称表示扩展功能)作为其标准库的一部分。我想从一个高层次的算法的角度来理解已经实施了什么。具体地说：

• 键的哪个函数用来给出放置数据的位置(即使用的哈希函数是什么)？
• 它们用来解决碰撞的算法是什么？例如，它们中的任何一个都使用简单链吗？
• 有没有利用随机性来选择散列函数？

Answer 1

对于爪哇来说

如何计算哈希函数本身？

它们由类本身用int hashCode()实现。

它们用来解决碰撞的算法是什么？例如，它们中的任何一个都使用简单的链接吗？

典型的简单链接。Java 8将支持字符串冲突的树。

有没有利用随机性来选择散列函数？

否，除了字符串元素/键以避免DOS攻击。