Why hash function has done XOR on hascode?

Question

I read the explanation but I could not understand what we are achieving by doing XOR on the hashCode. Can anyone give some example.

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

This code was taken from HashMap source code. I just wanted to know why they have used XOR, Marko has replied that properly that HashMap implementation uses lower-end bits. I think not only HashMap, other collections will also be doing same that is why I did not mentioned any collection name. I don't understand why people "rate down" this question.

possible duplicate of http://stackoverflow.com/questions/2334218/why-are-xor-often-used-in-java-hashcode-but-another-bitwise-operators-are-used — Jason C, Feb 27 '15 at 07:22
What is this code and who wrote it? It's anybody's guess what the author was trying to achieve, unless you can give us some context for what you're trying to do. — Dawood ibn Kareem, Feb 27 '15 at 07:33

score 3 · Accepted Answer · answered Feb 27 '15 at 08:50

3

This is a typical maneuver to protect from "bad" hashcodes: such whose lower-end bits are not variable enough. Java's HashMap implementation relies only on lower-end bits of the hashcode to select the bucket.

However, this code's motivation has expired long ago because HashMap already does its own bit spreading. It would make sense if used on Hashtable, but of course no code written since year 2000 should ever use it.

answered Feb 27 '15 at 08:50

Marko Topolnik

195,646
29
319
436

"this code's motivation has expired long ago because HashMap already does its own bit spreading" - the code in the OP is *from the HashMap class*, not from the OP's own code. – user253751 Mar 16 '15 at 09:04
@immibis That was not mentioned in the original question; instead it just said "I don't understand what *we* are achieving...". I assumed OP implied his own codebase. – Marko Topolnik Mar 16 '15 at 09:50
I see it was added 1.5 hours after your answer. – user253751 Mar 16 '15 at 10:02

score 0 · Answer 2 · answered Nov 18 '19 at 01:54

the code is openjdk java HashMap source code:HashMap.java

     /**
     * 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.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

xor is to let hash result be more distributed

Why hash function has done XOR on hascode?

2 Answers2