8

According to this blog entry, HashMap reinvokes its own implementation of hashCode() (called hash()) on a hashcode it already retrieved.

If key is not null then , it will call hashfunction on the key object , see line 4 in above method i.e. key.hashCode() ,so after key.hashCode() returns hashValue , line 4 looks like

int hash = hash(hashValue)

and now ,it applies returned hashValue into its own hashing function .

We might wonder why we are calculating the hashvalue again using hash(hashValue). Answer is ,It defends against poor quality hash >functions.

Can HashMap accurately reassign hashcodes? HashMap can store objects, but it doesn't have access to the logic that assigns a hashCode its objects. For example, hash() couldn't possibly integrate the logic behind the following hashCode() implementation:

public class Employee {
protected long employeeId;
protected String firstName;
protected String lastName;

public int hashCode(){
    return (int) employeeId;
}

}
Community
  • 1
  • 1
Muno
  • 575
  • 2
  • 5
  • 20
  • 3
    Possible duplicate of [Understanding strange Java hash function](http://stackoverflow.com/questions/9335169/understanding-strange-java-hash-function) – Nayuki Oct 16 '15 at 18:29
  • 1
    @NayukiMinase Guess the implementation of `hash()` has changed over time, since the 1.8.0_51 version is different/simpler (see my answer). – Andreas Oct 16 '15 at 18:32

1 Answers1

14

The hash() derives the "improved" hash code from the actual hash code, so equal input will always be equal output (from jdk1.8.0_51):

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

As to why the hash code needs improvement, read the javadoc of the method:

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don't benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

Andreas
  • 154,647
  • 11
  • 152
  • 247
  • 2
    To say it another way, the `HashMap` class takes raw `hashCode()` values from its objects and applies a one-to-one "whitening" transformation to try to make the distribution more even. – Nayuki Oct 16 '15 at 18:28
  • @Andreas I accepted the solution! Thanks. Could you link me, or perhaps explain, what power-of-two masking is? A google search for the term produced nil. – Muno Oct 18 '15 at 05:10
  • 1
    @Muno Power-of-two masking refers to the fact that the hashtable size is always a power of two (2,4,8,16,32,...), so to calculate hashtable bucket, a simple bitmask operation can be performed (e.g. `h & 0x1F` for hashtable size 32), which is faster than a modulus operation (`%`). – Andreas Apr 05 '17 at 23:23