What hashing function does Java use to implement Hashtable class?

by

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

More Related Contents:

  1. Why does Java’s hashCode() in String use 31 as a multiplier?
  2. Good Hash Function for Strings
  3. Why does HashMap require that the initial capacity be a power of two?
  4. Hash : How does it work internally?
  5. O(3^n) exponential time complexity [closed]
  6. Good Java graph algorithm library? [closed]
  7. Sparse matrices / arrays in Java
  8. How to decrypt a SHA-256 encrypted string?
  9. Quickest way to find missing number in an array of numbers
  10. Java, find intersection of two arrays
  11. Calculating all of the subsets of a set of numbers
  12. How to convert a byte array to its numeric value (Java)?
  13. How does Java order items in a HashMap or a HashTable?
  14. Why does Java’s Arrays.sort method use two different sorting algorithms for different types?
  15. Iteration order of HashSet
  16. Find duplicate element in array in time O(n)
  17. Find top N elements in an Array
  18. Algorithm for finding all paths in a NxN grid
  19. ConcurrentHashMap and Hashtable in Java [duplicate]
  20. Convert a String to a byte array and then back to the original String
  21. Lossless JPEG Rotate (90/180/270 degrees) in Java?
  22. Java – Sort one array based on values of another array?
  23. In Java, how do I efficiently and elegantly stream a tree node’s descendants?
  24. How to generate the power-set of a given List?
  25. How to restore the PriorityQueue to its initial state before the method call?
  26. How to determine if binary tree is balanced?
  27. Fastest way of finding the middle value of a triple?
  28. Interview question – Search in sorted array X for index i such that X[i] = i
  29. How to hash a password with SHA-512 in Java?
  30. Example of O(n!)?

Leave a Comment