How does put() work in HashMap

Question

I read in the internet that put() inserts element at the "head" of the linkedlist in case of collisions.

For example:

map location 1 has 1,0 -> 2,0 -> 3,0 -> 4,0 -> null

Now, I will insert an element 5,0 to the linkedlist (I hope hash() returns location 1 value for element 5). After inserting, the location 1 linkedlist will be 5,0 -> 1,0 -> 2,0 -> 3,0 -> 4,0 -> null

Now, I want to update the value of 3 to 30. Therefore I use map.put(KEY = 3, VALUE = 30);

My question is how does put() know whether to update or to insert?

To know if the element is present in the linkedlist, it has to scan the linkedlist. From what I have read in the internet, put() inserts element at the "head" of the linkedlist if there is a collision.

Thanks in advance

The answer is: "all keys have to be unique". If the map is ordered to add a key that already exists, it simply replaces the value. See my code-example. — , Jan 29 '17 at 22:06
Whatsmore, it seems that you're maybe mixing up LinkedList, which is both a List and a double ended Queue, and HashMap. Because the LinkedList API has no put()-method. It only has add(), offer() and push() depending on the mode in which you want to use it... — , Jan 29 '17 at 22:19

score 0 · Answer 1 · answered Jan 29 '17 at 22:07

import java.util.HashMap;

public class Test {

    public static void main(String[] args) {

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

        map.put(1, "Value 1");
        map.put(2, "Value 2");
        map.put(3, "Value 3");
        map.put(4, "Value 4");
        map.put(5, "Value 5");

        System.out.println(map);

        // existing key but new value
        map.put(2, "Value 7");

        System.out.println(map);

    }
}

score 0 · Answer 2 · answered Jan 29 '17 at 22:38

My question is how does put() know whether to update or to insert?

It has to get the bucket associated with the given key in the hashtable, and iterate over the linked-list stored there to try to find an element which matches both the key and the value provided. If such element is found, it will be updated with the new value, otherwise a new one will be added at the head of the linked list.

To keep this operation efficient (amortized constant time), the linked-list at each element should be as short as possible. This is done by:

The hash function should distribute the elements equally among all buckets.
The hash-map capacity should grow and add more buckets as new elements are added.

score 0 · Answer 3 · edited May 23 '17 at 12:33

In case of collision, If there is already an object sitting on calculated index, its next attribute is checked. If it is null, and current Entry object becomes next node in LinkedList. If next variable is not null, procedure is followed until next is evaluated as null.

You can learn details from the following video : "minute 3:26:

https://www.coursera.org/learn/data-structures-optimizing-performance/lecture/ozYZh/core-collisions-in-hash-tables

but if you need to add item at the 1. place, you can use the following answer :

https://stackoverflow.com/a/27214791

How does put() work in HashMap

3 Answers3