Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java HashMap implementation has 'next' member in Entry class. What's the use of it

Tags:

java

hashmap

Java HashMap implementation has 'next' member in Entry private class. Since, a new value for a key will override the old value, what's the use of 'next' member in the Entry class.

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
   .....

}
like image 945
Sidd K Avatar asked Dec 11 '12 19:12

Sidd K


People also ask

What is the purpose of HashMap class in Java?

The HashMap class of the Java collections framework provides the functionality of the hash table data structure. It stores elements in key/value pairs. Here, keys are unique identifiers used to associate each value on a map. The HashMap class implements the Map interface.

How is a Java HashMap actually implemented?

How the java implements it, is discussed in detail below: Hashmap uses the array of Nodes(named as table), where Node has fields like the key, value (and much more). Here the Node is represented by class HashMapEntry. Basically, HashMap has an array where the key-value data is stored.

What is the implementation of HashMap in Java?

It is possible to provide your implementation of hashCode(). In HashMap, hashCode() is used to calculate the bucket and therefore calculate the index. equals() method: This method is used to check whether 2 objects are equal or not. This method is provided by the Object class.

What happens if we put a key object in a HashMap which exists?

What happens if we put a key object in a HashMap which exists? Explanation: HashMap always contains unique keys. If same key is inserted again, the new object replaces the previous object.


2 Answers

next refers to the next entry in the same bucket.

You can have multiple entries in each bucket -- a bucket contains all the entries with hash code equal to some i mod 2^n for some n, not just the entry for one particular key.

like image 57
Louis Wasserman Avatar answered Sep 24 '22 21:09

Louis Wasserman


If more than one item hashes to the same bucket, then the bucket needs to be able to contain all the items, therefore in many implementations it'll become a collection of some sort, like a list.

like image 29
digitaljoel Avatar answered Sep 23 '22 21:09

digitaljoel