Java HashMap mechanism [duplicate]

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<Integer, int[]> then get will return int[]. If you actually wanted some element in that array, you'll have to search yourself. — Karolis Juodelė
– Karolis Juodelė, Commented Mar 15, 2013 at 16:10
grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… — assylias
– assylias, Commented Mar 15, 2013 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
– jlordo, Commented Mar 15, 2013 at 16:14
check stackoverflow.com/questions/6493605/how-does-java-hashmap-work — Biswajit
– Biswajit, Commented Mar 15, 2013 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
– Bhesh Gurung, Commented Mar 15, 2013 at 16:16

Evgeniy Dorofeev · Accepted Answer · 2013-03-15 16:10:16Z

2

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;
}

answered Mar 15, 2013 at 16:10

Evgeniy Dorofeev

137k31 gold badges208 silver badges288 bronze badges

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

Comments

user1230731 · Accepted Answer · 2013-03-15 16:12:08Z

0

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.

answered Mar 15, 2013 at 16:12

user1230731

551 gold badge1 silver badge6 bronze badges

Comments

Patricia Shanahan · Accepted Answer · 2013-03-15 16:27:34Z

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.
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.

Collectives™ on Stack Overflow

Java HashMap mechanism [duplicate]

3 Answers 3

Comments

Comments

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Linked

Related