Explanation of HashMap#hash(int) method

by

>>> is the logical right shift (no sign-extension) (JLS 15.19 Shift Operators), and ^ is the bitwise exclusive-or (JLS 15.22.1 Integer Bitwise Operators).

As to why this is done, the documentation offers a hint: HashMap uses power-of-two length tables, and hashes keys by masking away the higher bits and taking only the lower bits of their hash code.

// HashMap.java -- edited for conciseness
static int indexFor(int h, int length) {
    return h & (length-1);
}

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int index = indexFor(hash, table.length);
    // ...
}

So hash() attempts to bring relevancy to the higher bits, which otherwise would get masked away (indexFor basically discards the higher bits of h and takes only the lower k bits where length == (1 << k)).

Contrast this with the way Hashtable (which should have NOT a power-of-two length table) uses a key’s hash code.

// Hashtable.java -- edited for conciseness
public synchronized V get(Object key) {
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % table.length;
    // ...
}

By doing the more expensive % operation (instead of simple bit masking), the performance of Hashtable is less sensitive to hash codes with poor distribution in the lower bits (especially if table.length is a prime number).

More Related Contents:

  1. Why does HashMap require that the initial capacity be a power of two?
  2. How to create a HashMap with two keys (Key-Pair, Value)?
  3. Count number of values of a list having same hash value in java?
  4. How to convert fuzzy hash string to a file? [closed]
  5. How to print all the values for a key in HashMap in java
  6. what is the method to delete hashmap entry
  7. How to check if an integer is in a set of given ranges? [closed]
  8. Java 8 Streams hashmap
  9. Is the order of values retrieved from a HashMap the insertion order
  10. Java Compare Two Lists
  11. How to preserve insertion order in HashMap? [duplicate]
  12. java.lang.OutOfMemoryError: GC overhead limit exceeded [duplicate]
  13. How to call a method stored in a HashMap? (Java) [duplicate]
  14. Performance ConcurrentHashmap vs HashMap
  15. Java HashMap performance optimization / alternative
  16. Reverse HashMap keys and values in Java
  17. What is a best practice of writing hash function in java?
  18. Copying a HashMap in Java
  19. Java HashMap nested generics with wildcards
  20. How to prove that HashMap in java is not thread-safe
  21. Is there a way to get the value of a HashMap randomly in Java?
  22. What exactly is bucket in hashmap?
  23. Changing HashMap keys during iteration
  24. Why Hashtable does not allow null keys or values?
  25. Hash : How does it work internally?
  26. Theoretical limit for number of keys (objects) that can be stored in a HashMap?
  27. Why are immutable objects in hashmaps so effective?
  28. what is the best way to get a sub HashMap based on a list of Keys?
  29. Explain the timing causing HashMap.put() to execute an infinite loop
  30. Generate Subject Hash of X509Certificate in Java

Leave a Comment