put method of Hashmap

Question

I see that in the implementation of put method of HashMap class, the table bucket is got using int i = indexFor(hash, table.length); and then it adds an entry to that bucket - 'i' if the hashcode and the key are not equal. If they are equal, the old value is replaced.

How does it find the right bucket using the key? What if the bucket does not exist?
How does it evaluate if it needs to add it in the same bucket or different bucket?
What happens when the hash codes are same and keys are different? If the hashcodes are same, then the entry should be in the same bucket but I do not see that in the code of put method!

Source code:

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}


void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

There are too many questions here for one questions. Moreover, these questions are readily answered by reading about how hashed collections work in general. — Boris the Spider, Aug 04 '14 at 07:15
possible duplicate of [Internals of how the HashMap put() and get() methods work (basic logic only )](http://stackoverflow.com/questions/11559954/internals-of-how-the-hashmap-put-and-get-methods-work-basic-logic-only) — codelion, Aug 04 '14 at 07:15
To get answers for *all* your questions, I think its better if you look at the source code of `HashMap, — TheLostMind, Aug 04 '14 at 07:19
For example I used [Google](https://www.google.com) and I arrived and [this article](http://www.dineshonjava.com/2013/06/how-does-java-hashmap-work-internally.html#.U980MfldWHM) which answers many of your questions. Google is your friend. — Boris the Spider, Aug 04 '14 at 07:24
All the links you have provided is fine and I do understand what happens when the keys and hashcodes are same and when the hashcodes are different but my question was that I could not see that in the source code. I've added the source code. Please comment — Mercenary, Aug 05 '14 at 12:11

score 0 · Answer 1 · answered Aug 05 '14 at 12:59

Some times ago for exercise purpose I have written simple implementation of hash map(code) I think that reading that you can get answers on yours questions.

Test for that implementation you can find here

Another implementation utilizing lists you can find here

score 0 · Answer 2 · answered Aug 26 '14 at 08:24

return of indexOf() method will never be exceed the array size. check the HashTable implementation ,its not exactly as the HashMap, but you will get the idea about basic hashing.

suppose you have 4 MyClass object. its hashcode value is 11,12,13,14 respectively. and your default hashmap size is 10. then index would be like that-

     index =   hashcode % table.length; 
                     1 =      11     %  10 ;
                     2 =      12     %  10 ;
                     3 =      13     %  10 ;

1,2,3 are the index value, where your entry get stored in array.

if your class hashcode is 21 then its index would be 21 % 10 = 1;

index 1 have already a Entry object , so it will be stored as LinkedList.

put method of Hashmap

2 Answers2