HashMap 運作原理 (from Internal Working of HashMap in Java )

Internal Structure of HashMap

HashMap conatins an array of Node.

Node class containis:

1. int hash
2. K key
3. V value
4. Node next

Buckets

• A bucket is one element of HashMap array. It is used to store nodes.
• A single bucket can have more than one nodes, it depends on hashCode() method.
• Default initial capacity(number of bucket) = 16, load factor = 0.75f(75%)
• When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed so that the hash table has approximately twice the number of buckets.

  after storing the 12th(16 * 0.75) data into the HashMap, its capacity becomes 32(16*2).

Index Calculation in HashMap

index = hashCode(key) % n

n: number of buckets or size of array

91 % 16 = 11, 155 % 16 = 11, 171 % 16 = 11

from: Java之美[從菜鳥到高手演變]之HashMap、HashTable

Put Data

• Initially Empty hashMap

  HashMap map = new HashMap();
  

  

• Inserting Key-Value Pair

  map.put(new Key("vishal"), 20);
  

  Steps:

  1. Hash code of Key{"vishal"} is 118.
  2. Index is 6.

  3. Create a node object as :

     {
        int hash = 118
     
        // {"vishal"} is not a string but 
        // an object of class Key
        Key key = {"vishal"}
     
        Integer value = 20
        Node next = null
     }
     

  4. Place this object at index 6, if no other object is presented there.

  

• Inserting another Key-Value Pair

  map.put(new Key("sachin"),30);
  

  

• In Case of collision

  map.put(new Key("vaibhav"),40);
  

  Steps:

  1. Hash code of Key {“vaibhav”} is 118.
  2. Index is 6.

  3. Create a node object a:

     {
       int hash = 118
       Key key = {"vaibhava"}
       Integer value = 40
       Node next = null
     }
     

  4. In this case a node object is found at the index 6 – this is a case of collision.

  5. Check if both the keys are same via equals().

     • if key are same, replace the value with current value.
     • Otherwise connect this node object to the previous node object via linked list.

  

Get Data

• Fetch the data for key vaibahv

  map.put(new Key("vaibhav"),40);
  

  Steps:

  1. Hash code of Key {“vaibhav”} is 118.
  2. Index is 6.
  3. Go to index 6 of array and compare first element’s key with given key. If both are equals then return the value,
     otherwise check for next element if it exists.

Java Code

import java.util.HashMap;

class Key
{
    String key;
    Key(String key)
    {
        this.key = key;
    }

    @Override
    public int hashCode()
    {
        int hash = (int)key.charAt(0);
        System.out.println("hashCode for key: "
                           + key +" = "+ hash);
        return hash;
    }

    @Override
    public boolean equals(Object obj)
    {
        return key.equals(((Key)obj).key);
    }
}

// Driver class
public class GFG
{
    public static void main(String[] args)
    {
        HashMap map = new HashMap();
        map.put(new Key("vishal"), 20);
        map.put(new Key("sachin"), 30);
        map.put(new Key("vaibhav"), 40);

        System.out.println();
        System.out.println("Value for key sachin: " +
                            map.get(new Key("sachin")));
        System.out.println("Value for key vaibhav: " +
                            map.get(new Key("vaibhav")));
    }
}

Reference

Java中equals()與hashCode()方法詳解 HashMap的工作原理，HashMap工作原理