o7planning

Java HashMap Tutorial with Examples

  1. HashMap
  2. How does HashMap work?

1. HashMap

HashMap<K,V> is a class in Java Collection Framework implementing Map<K,V> interface. HashMap fully supports all features specified in Map interface including optional features.
HashMap allows to store key and value pairs. Keys cannot be duplicated.
public class HashMap<K,V> extends AbstractMap<K,V>
                      implements Map<K,V>, Cloneable, Serializable
The characteristics of HashMap:
  • HashMap contains key and value pairs.
  • It can have one null key and multiple null values.
  • HashMap does not maintain keys order.
  • it works base on hashing technique. (See more explanation of this technique below).
Let's see this simple example, using HashMap to simulate a phonebook, in which phone number is the key and owner name is the value. Keys are never duplicated.
HashMapEx1.java
package org.o7planning.hashmap.ex;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
 
public class HashMapEx1 {
 
    public static void main(String[] args) {
        Map<String, String> phonebook = new HashMap<String, String>();
 
        phonebook.put("01000005", "Tom");
        phonebook.put("01000002", "Jerry");
        phonebook.put("01000003", "Tom");
        phonebook.put("01000004", "Donald");
        
        Set<String> phoneNumbers = phonebook.keySet();
 
        for (String phoneNumber : phoneNumbers) {
            String name = phonebook.get(phoneNumber);
            
            System.out.println("Phone Number: " + phoneNumber + " ==> Name: " + name);
        }
    }
}
Output:
Phone Number: 01000004 ==> Name: Donald
Phone Number: 01000003 ==> Name: Tom
Phone Number: 01000005 ==> Name: Tom
Phone Number: 01000002 ==> Name: Jerry
Basically all the features of HashMap comply with the specification of the Map interface, so you can read the following Map article to learn more about how to use HashMap:
See also: The WeakHashMap class is a memory-saving variant of the HashMap class. Mappings that are not really needed are automatically removed by the Java Garbage Collector.

2. How does HashMap work?

Java designers have used hashing technique for HashMap class to store data and improve its performance. Now lets see how this technique is used in HashMap. We basically analyze what happens when we call these methods: HashMap.put(K,V), HashMap.get(K) and HashMap.remove(key).
HashMap<K,V> manages an array of Node<K,V> objects that will be replaced by another larger array if all of its elements has been assigned value.
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Node<K,V> class consists of 4 fields. next field is a reference to the next Node object. It may not be the next element in the array.
static class Node<K,V> implements Map.Entry<K,V> {
    int hashcode;
    K key;
    V value;
    Node<K,V> next;
}
HashMap ensures those Node(s) having the same hashcode will have consecutive references. This helps it quickly find all Node(s) with the same specified hashcode .
HashMap.put(key,value)
When calling HashMap.put(key,value) method, HashMap looks for Node with condition node.hashcode == hash(key). If no match is found, a new Node object is assigned to the array. (See picture below)
Otherwise, HashMap quickly identifies those consecutive Node(s) satisfying condition node.hashcode == hash(key) and significantly narrows the scope of Node(s) to be searched by key.
  • If the Node corresponding to the key is found, new value will be assigned to Node.value.
  • Otherwise, a new Node object is created and assigned to the array (See picture below).
HashMap.get(key)
When HashMap.get(key) method is called, HashMap quickly identifies consecutive Node(s) that satisfy the condition node.hashcode == hash(key), which significantly narrows the scope of the Node(s) need to be searched by key. Then, it searches Node by key and returns node.value if found, otherwise it returns null.
HashMap.remove(key)
Conclusion: Object.hashcode() method returns hashcode of an object, which is generated by JVM by default, and rarely duplicate. The subclasses of Object class can override this method to return a custom hashcode.
HashMap uses hashing technique to help improve its performance, because comparing 2 numbers is always faster than comparing 2 objects.

Java Collections Framework Tutorials

Show More

Newest Articles

Show More