Java使用什么哈希函数来实现Hashtable类？

Java使用什么哈希函数来实现Hashtable类？

将密钥添加到OpenJDK中的HashMap或从中请求时，执行流程如下：

1. 使用开发人员定义的

   hashCode()

   方法将密钥转换为32位值。
2. 然后， 第二个哈希函数 （Andrew的答案包含源代码）将32位值转换为哈希表中的偏移量。第二个哈希函数由HashMap的实现提供，并且不能被开发人员覆盖。
3. 哈希表的相应条目包含对链表的引用，如果哈希表中不存在键，则为null。如果存在冲突（多个具有相同偏移量的键），则将键及其值仅收集在一个单链表中。

如果将哈希表大小选择为适当高，则冲突次数将受到限制。因此，单次查找平均只需要恒定的时间。这称为 预期恒定时间
。但是，如果攻击者可以控制插入到哈希表中的密钥并了解所使用的哈希算法，则他可能会引发很多哈希冲突，因此会强制执行线性查找时间。这就是为什么最近对某些哈希表实现进行了更改，以包括一个随机元素的原因，这使得攻击者更难预测哪些键将导致冲突。

一些ASCII艺术

key.hashCode()     |     | 32-bit value     |        hash table     V      +------------+    +----------------------+HashMap.hash() --+     | reference  | -> | key1 | value1 | null |      |     |------------|    +----------------------+      | modulo size    | null       |      | = offset       |------------|    +---------------------+      +--------------> | reference  | -> | key2 | value2 | ref | |------------|    +---------------------+ |    ....    | |          +----------------+          V        +----------------------+        | key3 | value3 | null |        +----------------------+