What hashing function does Java use to implement Hashtable class?

Question

From the book CLRS ("Introduction to Algorithms"), there are several hashing functions, such as mod, multiply, etc.

What hashing function does Java use to map the keys to slots?

I have seen there is a question here Hashing function used in Java Language. But it doesn't answer the question, and I think the marked answer for that question is wrong. It says that hashCode() let you do your own hashing function for Hashtable, but I think it is wrong.

The integer returned by hashCode() is the real key for Hashtble, then Hashtable uses a hashing function to hash the hashCode(). What this answer implies is that Java give you a chance to give Hashtable a hashing function, but no, it is wrong. hashCode() gives the real key, not the hashing function.

So what exactly the hashing function does Java use?

Answer 1

When a key is added to or requested from a HashMap in OpenJDK, the flow of execution is the following:

1. The key is transformed into a 32-bit value using the developer-defined hashCode() method.
2. The 32-bit value is then transformed by a second hash function (of which Andrew's answer contains the source code) into an offset inside the hash table. This second hash function is provided by the implementation of HashMap and cannot be overridden by the developer.
3. The corresponding entry of the hash table contains a reference to a linked list or null, if the key does not yet exist in the hash table. If there are collisions (several keys with the same offset), the keys together with their values are simply collected in a singly linked list.

If the hash table size was chosen appropriately high, the number of collisions will be limited. Thus, a single lookup takes only constant time on average. This is called expected constant time. However, if an attacker has control over the keys inserted into a hash table and knowledge of the hash algorithm in use, he can provoke a lot of hash collisions and therefore force linear lookup time. This is why some hash table implementations have been changed recently to include a random element that makes it harder for an attacker to predict which keys will cause collisions.

Some ASCII art

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