Java HashMap Tutorial with Examples
1. HashMap
No ADS
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
- Map
- TreeMap
- WeakHashMap
- LinkedHashMap
- IdentityHashMap
- ConcurrentHashMap
- ConcurrentSkipListMap
- EnumMap
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?
No ADS
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.
No ADS
Java Collections Framework Tutorials
- Java PriorityBlockingQueue Tutorial with Examples
- Java Collections Framework Tutorial with Examples
- Java SortedSet Tutorial with Examples
- Java List Tutorial with Examples
- Java Iterator Tutorial with Examples
- Java NavigableSet Tutorial with Examples
- Java ListIterator Tutorial with Examples
- Java ArrayList Tutorial with Examples
- Java CopyOnWriteArrayList Tutorial with Examples
- Java LinkedList Tutorial with Examples
- Java Set Tutorial with Examples
- Java TreeSet Tutorial with Examples
- Java CopyOnWriteArraySet Tutorial with Examples
- Java Queue Tutorial with Examples
- Java Deque Tutorial with Examples
- Java IdentityHashMap Tutorial with Examples
- Java WeakHashMap Tutorial with Examples
- Java Map Tutorial with Examples
- Java SortedMap Tutorial with Examples
- Java NavigableMap Tutorial with Examples
- Java HashMap Tutorial with Examples
- Java TreeMap Tutorial with Examples
- Java PriorityQueue Tutorial with Examples
- Java BlockingQueue Tutorial with Examples
- Java ArrayBlockingQueue Tutorial with Examples
- Java TransferQueue Tutorial with Examples
Show More