Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the trick in the hash() method in Java HashMap implementation? [duplicate]

Tags:

java

hashmap

hash

Possible Duplicate:
Understanding strange Java hash function

static int hash(int h) {   
    // This function ensures that hashCodes that differ only by   
    // constant multiples at each bit position have a bounded   
    // number of collisions (approximately 8 at default load factor).   
    h ^= (h >>> 20) ^ (h >>> 12);   
    return h ^ (h >>> 7) ^ (h >>> 4);   
} 

I don't quite understand the algorithm principle of this implementation. Any explanation or any resouce I could refer to ? Thanks !

UPDATE

Thanks all for the answers and resouces. Actually I understand how hash works, yet but not konw why this code will ensure a bounded number of collisions, as the comment says. Is there any theoretical verification?

like image 841
larmbr Avatar asked Nov 19 '12 10:11

larmbr


1 Answers

The main goal is to generate very different values for similar input parameters and minimize number of collisions. http://en.wikipedia.org/wiki/Hash_function

This implementation is just one satisfactory option of many possible functions.

like image 115
Nikolay Kuznetsov Avatar answered Nov 16 '22 02:11

Nikolay Kuznetsov