Java HashMap mechanism

Question

In Java, if I have HashMap<Integer, int[]> map and want to lookup for a given int key like map.get(key) then the algorithm will compute key.hashCode(), go to the corresponding bucket and search linearly for objects of type int[] and compare them by using equals() ? So those int[] objects in a bucket will have the same key (computed by hashCode) and they will be compared by equals(). Is that right?

I can not find on the web an example, where it is shown clearly. Only words.

What you are redirecting me at does not contain a normal understandable example, I do not need theory.

If you have a `HashMap` then `get` will return `int[]`. If you actually wanted some element in that array, you'll have to search yourself. — Karolis Juodelė, Mar 15 '13 at 16:10
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/HashMap.java#HashMap.getEntry%28java.lang.Object%29 — assylias, Mar 15 '13 at 16:10
@SophieSperner: In a `HashMap` there can only be one value per key. For more values per key, you need a `MultiMap`. — jlordo, Mar 15 '13 at 16:14
check http://stackoverflow.com/questions/6493605/how-does-java-hashmap-work — Biswajit, Mar 15 '13 at 16:16
`hashCode` and `equals` are relevant to key only. It doesn't not do anything with the value, it just returns the reference to it. — Bhesh Gurung, Mar 15 '13 at 16:16

score 2 · Answer 1 · answered Mar 15 '13 at 16:10

Correction: ...go to the corresponding bucket and search linearly for an entry with the key (Integer) equal to the given key. And this is how this search actually implemented in HashMap

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

score 0 · Answer 2 · answered Mar 15 '13 at 16:12

I do not think this is a good solution to intermix an array as a value when you can clearly use a data structure seperately. The idea of a hash map is to condencs index relative to a table. You can easyly keep all the ints in a seperate data structure and enumerate with a for loop and pair the key with put. This underlying construction will give you the reference regardless of where the reference is stored.

score 0 · Answer 3 · answered Mar 15 '13 at 16:27

There are 2^32 possible hash codes, but the maximum number of buckets is Integer.MAX_VALUE, the largest possible int. That means HashMap must map multiple hash codes to the same bucket.

To look up a probe key, in your case an Integer, it first computes the probes's hash code. It goes to the bucket containing that hash code. It scans the keys in the (key,value) pairs in the bucket for keys whose hash code matches the probe hash code. It only runs the equals test for those keys that do have the required hash code.

If it finds a (key, value) pair whose key is equal to the probe, it returns the value, in your case an int[] reference.

See the code quoted in @Evgeniy's answer for details of handling of null.

But all keys inside a bucket are the same, is not it? That's why I'm suffering of no examples around. I just do not understand. — Sophie Sperner, Mar 15 '13 at 16:57
No, a bucket contains **all** (key, value) pairs whose key has a hash code that falls into a set of hash codes that are assigned to that bucket. — Patricia Shanahan, Mar 15 '13 at 17:39

Java HashMap mechanism

3 Answers3