Using Integer as a key with HashMap in Java

Question

Recently I was looking for good implementation of hashCode() method in Java API and looked through Integer source code. Didn't expect that, but the hashCode() just returns the backed int value.

public final class Integer ... {
private final int value;
...
    public int hashCode() {
        return Integer.hashCode(value);
    }
    public static int hashCode(int value) {
        return value;
    }

It's really strange as there are a lot of papers and pages as well as packages dedicated to this question - how to design good hash function to distribute values.

Finally I ended up with this conclusion:

Integer is the worst data type candidate for a key when used with HashMap, as all consecutive keys will be places in one bin/bucked. Like in the sample above.

Map<Integer, String> map = HashMap<>();

for (int i = 1; i < 10; i++) {
    map.put(Integer.valueOf(i), "string" + i);
}

There are two questions, for which I didn't find answers while googled:

Am I right with my conclusion regarding Integer data type?
In case it's true, why Integer's hashCode() method don't implemented in some tricky way when power operation, prime numbers, binary shifting are used?

" all consecutive keys will be places in one bin" — no, not true at all. You seem to have some misunderstanding about how hash bucketing works. — khelwood
– khelwood, Commented May 10, 2018 at 12:37

Eran · Accepted Answer · 2018-05-10 13:00:22Z

14

Integer is the worst data type candidate for a key when used with HashMap, as all consecutive keys will be places in one bin

No, that statement is wrong.

In fact, the implementation of Integer's hashCode() is the best possible implementation. It maps each Integer value to a unique hashCode value, which reduces the chance of different keys being mapped into the same bucket.

Sometimes a simple implementation is the best.

From the Javadoc of hashCode() in the Object class:

It is not required that if two objects are unequal according to the java.lang.Object.equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

Integer is one of the few classes that actually guarantees that unequal objects will have different hashCode().

edited May 10, 2018 at 13:00

answered May 10, 2018 at 12:32

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

oreh Over a year ago

thx for the answer. I finally get this peace of code if ((p = tab[i = (n - 1) & hash]) == null) from putVal()

Cargeh · Accepted Answer · 2018-05-10 12:41:25Z

Adding to @Eran's answer, Java's HashMap also has a protection against "bad hash functions" (which Integer.hashCode() isn't, but still).

/**
 * 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);
}

So your "simple hash" of an integer will actually be a bit different when working with HashMap.

Mena · Accepted Answer · 2018-05-10 12:33:51Z

From the docs:

The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

--> Integer#hashCode fulfills this.

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

--> Integer#hashCode fulfills this too.

It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

--> Integer#hashCode fulfills this to the maximum extent, i.e. two unequal Integers will never have the same hash code.

Collectives™ on Stack Overflow

Using Integer as a key with HashMap in Java

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related