CODEWITHSUNDEEP
javaarrayslinked-listhashmaphashset
dexterousashish
dexterousashish

Reputation: 443

Is HashMap internally implemented in Java using LinkedList or Array?

How is HashMap internally implemented? I read somewhere that it uses LinkedList while other places it mentions Arrays.

I tried studying the code for HashSet and found Entry array. Then where is LinkedList used?

Upvotes: 17

Views: 24600

Answers (5)

Sivaram Rasathurai
Sivaram Rasathurai

Reputation: 6333

The map is something that retrieves/puts a value based on a key since the key is mapped with that particular value.

enter image description here

But Internally, this mapping technique is slightly different.

  1. This HashMap is defined as an array(Let's say for simplicity we have a size of 8). enter image description here

  2. Hashing is done to the key to identifying the place of the array where that particular key-value pair is going to store.

    a. Key may be primitive type or object

    b. Get the hashcode based on the key (If an object, we should implement better hashcode and equal methods in their class)

    c. This hashcode makes the indexing and searching faster.

    d. Maths - 12112, Science - 23454, Tamil - 3222112, English - 3243212

  3. We can't put that key-value pair into the index which we have as hashcode since it is greater than the length of the array. So we do mod to get the place of the array where we have to put the key-value pair. a. Maths will be in 12112 % 8 = 0

    b. Science will be in 23454 % 8 = 4

    c. Tamil will be in 3222112 % 8 = 0

    d. English will be in 3243212 % 8 = 6

  4. If your look carefully, we have collisions in the 0th index. How can we solve this collision? We have to save both key-value pairs in the same index For that, they introduce Node or Entry.Node has Key, Value, Hashcode and next node of that particular index.

enter image description here

  1. when we have collisions It will add up to the next node. So finally It would be like this. enter image description here

  2. The hashMap is nothing but an array of linked lists. So each position has a linked list of the array to avoid collisions.

After Java 8

This LinkedList mechanism is changed to balance Tree since the time complexity of searching in the linked list is O(n). We have to go one by one to find the exact element in the LinkedList. in the balance Tree, It will be O(log(n)).

After Java 8, The hashmap is nothing but an array of balance Trees.

Upvotes: 2

piet.t
piet.t

Reputation: 11911

Each HashMap has an Array and in that Array it places each Entry in a position according to its key's hash code (e.g. int position = entry.getKey().hashCode() % array.length). The position where an Entry is stored is called a bucket.

If more than one Entry ends up in the same bucket, those Entries are combined in a LinkedList (also see @Dukeling's answer). Thus the bucket metaphor: each Array index is a "bucket" where you dump in all matching keys.

You have to use an Array for the buckets in order to achieve the desired constant time performance for random access. Within a bucket you have to traverse all elements to find the desired key anyways, so you can use a LinkedList as it is easier to append to (no resize needed).

This also shows the need for a good hash function, because if all keys hash to only a few values you will get long LinkedLists to search and a lot of (fast to access) empty buckets.

Upvotes: 10

Ankit Mittal
Ankit Mittal

Reputation: 1369

HashMap internally uses Entry for storing key-value pair. Entry is of LinkedList type.

Entry contains following ->

K key,

V value and

Entry next > i.e. next entry on that location of bucket.

static class Entry<K, V> {
     K key;
     V value;
     Entry<K,V> next;

     public Entry(K key, V value, Entry<K,V> next){
         this.key = key;
         this.value = value;
         this.next = next;
     }
}

HashMap diagram -

custom Implementation of HashMap

From : http://www.javamadesoeasy.com/2015/02/hashmap-custom-implementation.html

Upvotes: 3

user2813148
user2813148

Reputation:

HashMap has an array of HashMap.Entry objects :

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry<K,V>[] table;

We can say that Entry is a one-way linked list (such HashMap.Entry linkage is called "Bucket") but it is not actually a java.util.LinkedList.

See for yourself :

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

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

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }

Upvotes: 5

Bernhard Barker
Bernhard Barker

Reputation: 55589

It basically looks like this:

 this is the main array
   ↓
[Entry] → Entry → Entry      ← here is the linked-list
[Entry]
[Entry] → Entry
[Entry]
[null ]
[null ]

So you have the main array where each index corresponds to some hash value (mod'ed* to the size of the array).

Then each of them will point to the next entry with the same hash value (again mod'ed*). This is where the linked-list comes in.

*: As a technical note, it's first hashed with a different function before being mod'ed, but, as a basic implementation, just modding will work.

Upvotes: 25

Related Questions