java - Java 使用什么散列函数来实现 Hashtable 类？

Question

从书CLRS(《算法导论》)中，有几个散列函数，如mod、multiply等。

Java 使用什么散列函数将键映射到槽？

我看到这里有一个问题Hashing function used in Java Language .但它没有回答问题，我认为该问题的标记答案是错误的。它说 hashCode() 可以让你为 Hashtable 做你自己的散列函数，但我认为它是错误的。

hashCode()返回的整数是Hashtble的真正key，然后Hashtable使用散列函数对hashCode()进行散列。这个答案意味着Java给了你一个机会给Hashtable一个散列函数，但是不，这是错误的。 hashCode() 给出真正的键，而不是散列函数。

那么 Java 到底使用什么哈希函数呢？

Answer 1

在 OpenJDK 中，当向 HashMap 添加或请求键时，执行流程如下:

1. 使用开发人员定义的 hashCode() 方法将 key 转换为 32 位值。
2. 然后通过第二个散列函数(其中 Andrew 的答案包含源代码)将 32 位值转换为散列表内的偏移量。第二个哈希函数由 HashMap 的实现提供，开发人员无法覆盖。
3. 如果哈希表中尚不存在该键，则哈希表的相应条目包含对链表的引用或 null。如果存在冲突(具有相同偏移量的多个键)，则将键及其值简单地收集在一个单链表中。

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

一些 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 |
                                                    +----------------------+