The Map interface in Java is part of the Java Collections Framework and provides a way to store key-value pairs.
Each key in a Map is associated with a single value, and the keys in a Map must be unique.
On the other hand, the same value can be associated with several different keys.
What You Need
- About 19 minutes
- A favorite text editor or IDE
- Java 8 or later
1. Methods of Map Interface
The Map interface defines several methods :
| Method | Role |
|---|---|
| void clear() | Remove all items from the collection |
| boolean containsKey(Object) | Indicate if the key is contained in the collection |
| boolean containsValue(Object) | Indicate if the value is contained in the collection |
| Set entrySet() | Return a set containing the collection’s key/value pairs |
| Object get(Object) | Return the value associated with the key provided as a parameter |
| boolean isEmpty() | Indicate if the collection is empty |
| Set keySet() | Return a set containing the collection keys |
| boolean isEmpty() | Return a boolean indicating if the collection is empty |
| Object put(Object, Object) | Insert the key and its associated value provided as parameters |
| void putAll(Map) | Insert all the keys/values of the object provided as a parameter |
| Collection values() | Return a collection that contains all element values |
| Object remove(Object) | Delete the element whose key is provided as a parameter |
| int size() | Return the number of elements contained in the collection |
2. Implementations of Map Interface
| Implementation | Role |
|---|---|
| java.util.Hashtable<K,V> | It maps keys to values and is thread safe. Any non-null object can be used as a key or as a value. To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method. It can be traversed by Enumerator and Iterator. |
| java.util.HashMap<K,V> | Like Hashtable but it is not thread safe. It allows one null key and multiple null values. It can not be traversed by Enumerator. |
| java.util.TreeMap<K,V> | It keeps the entries sorted according to the natural ordering of keys or better using a comparator if provided at construction time. |
| java.util.EnumMap<K,V> | It exclusively takes Enum as its keys. It does not permits null key, but permits multiple null values. It is not thread-safe. Its performance is better than HashMap. |
| java.util.IdentityHashMap<K,V> | The Map interface mandates the use of the equals() method on the key comparison. However, the IdentityHashMap class violates that contract. Instead, it uses reference equality (==) on key search operations. |
| java.util.WeakHashMap<K,V> | It is a hashtable-based implementation of the Map interface, with keys that are of a WeakReference type. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use, meaning that there is no single Reference that point to that key. When the garbage collection (GC) process discards a key, its entry is effectively removed from the map. |
| java.util.LinkedHashMap<K,V> | The LinkedHashMap class is very similar to HashMap in most aspects. However, it is able to maintain the order of elements either by Insertion-Order or by Access-Order. |
| java.util.concurrent.ConcurrentHashMap<K,V> | HashMap is not a thread-safe implementation of Map interface. Even if Hashtable is thread safe, it is not very efficient. ConcurrentHashMap is thread-safe and efficient by locking only the portion of the map being modified, rather than the entire map. |
| java.util.concurrent.ConcurrentSkipListMap<K,V> | All the elements of ConcurrentSkipListMap are sorted based on natural ordering or by the Comparator passed during it’s construction time. This class uses a concurrent variation of SkipList data structure providing log(n) time cost for insertion, removal, update, and access operations. These operations are safe for executing concurrently by multiple threads. |
2.1 Hashtable
The Hashtable class, present since Java 1.0, makes it possible to associate elements in a collection in the form of key/value pairs.
It has below characteristics :
- It is thread-safe because all methods are synchronized;
- It is not possible to use null value as key or value.
All the objects which are used as keys in a Hashtable must redefine the methods equals() and hashCode().
The Hashtable class is made up of buckets: depending on the hash value of the key, the element is inserted into a particular bucket.
Multiple objects with the same hash value will be in the same bucket.
The Hashtable class has two properties that affect its performance :
- The initial capacity : the number of elements that Hashtable can contain when it is created;
- The load factor : it specifies the percentage of filling of Hashtable before its enlargement to be able to contain more elements, the default value is 0.75.
It is important not to use too large an initial capacity or too small a load factor so as not to degrade performance when traversing Hashtable.
When the number of elements in Hashtable is greater than the size of Hashtable multiplied by the load factor then Hashtable is enlarged.
This operation is costly because it requires a rehash of Hashtable (reconstruction of its data structure linked to an increase in the number of buckets).
The rehash() method is implemented for this operation.
The estimated capacity and the load factor of Hashtable must be taken into account when defining the initial capacity in order to avoid as much as possible the number of rehash type operations performed when increasing the size of Hashtable.
If a Hashtable must contain many elements, it is therefore interesting to create its instance with an initial capacity high enough to contain the elements plus a margin corresponding to the capacity multiplied by the load factor.
The performance will be improved because it will avoid one or more collection grow operations.
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Map.Entry;
import java.util.Iterator;
public class HashtableTest {
public static void main(String[] args) {
Hashtable<String, Integer> fruitPrices = new Hashtable<>();
fruitPrices.put("apple", 2);
fruitPrices.put("pear", 9);
fruitPrices.put("pineapple", 6);
try {
fruitPrices.put("orange", null);
} catch (NullPointerException e) {
System.out.println("value can not be null");
}
try {
fruitPrices.put(null, 0);
} catch (NullPointerException e) {
System.out.println("key can not be null");
}
System.out.println();
Iterator<Entry<String, Integer>> it = fruitPrices.entrySet().iterator();
while (it.hasNext()) {
Entry<String, Integer> fruit = it.next();
System.out.println(fruit.getKey() + " : " + fruit.getValue());
}
System.out.println();
Enumeration<String> fruits = fruitPrices.keys();
while (fruits.hasMoreElements()) {
String fruit = fruits.nextElement();
Integer price = fruitPrices.get(fruit);
System.out.println(fruit + " : " + price);
}
}
}
Below is the output of above code snippet :
value can not be null
key can not be null
apple : 2
pineapple : 6
pear : 9
apple : 2
pineapple : 6
pear : 9
2.2 HashMap
The HashMap class, added in Java 1.2, is an implementation of the Map interface that uses a Hashtable.
It is similar to the Hashtable class except that it is not synchronized and allows the use of null.
It uses an array of linked lists for storing its elements.
The index of a key in the array is determined by an algorithm using the hash value of the object.
If two objects have the same hash value, there is a collision because both objects must be placed in the same bucket.
To manage this problem, the bucket contains a linked list : each element (its key and its value) is encapsulated in an instance of type Entry.
The HashMap class has below characteristics :
- It allows the use of the null value as a key and as a value;
- It is not thread-safe;
- It does not guarantee any order when browsing the elements.
The HashMap class has two properties :
- The initial capacity;
- The load factor.
The capability value must be a power of 2 to allow the algorithm that determines the index into the array from the hash value to work.
The load factor defines the maximum filling percentage of HashMap before it is enlarged.
If the percentage of the number of elements contained in the HashMap compared to the capacity of the HashMap is greater than the load factor, then the maximum capacity of the HashMap is doubled.
As a HashMap is based on the use of the hash value of keys, the ideal is to use immutable instances of objects whose equals() and hashCode() methods are correctly implemented.
If multiple threads need to add or remove items from the collection, concurrency must be manually managed.
It is for example possible to use an instance of the collection returned by the synchronizedMap() method of the Collections class.
Map m = Collections.synchronizedMap(new HashMap());
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
public class HashMapTest {
public static void main(String[] args) {
HashMap<String, Integer> fruitPrices = new HashMap<>();
fruitPrices.put("apple", 2);
fruitPrices.put("pear", 9);
fruitPrices.put("pineapple", 6);
fruitPrices.put("orange", null);
fruitPrices.put(null, 0);
Iterator<Entry<String, Integer>> it = fruitPrices.entrySet().iterator();
while (it.hasNext()) {
Entry<String, Integer> fruit = it.next();
System.out.println(fruit.getKey() + " : " + fruit.getValue());
}
System.out.println();
for (String fruit : fruitPrices.keySet()) {
Integer price = fruitPrices.get(fruit);
System.out.println(fruit + " : " + price);
}
}
}
Below is the output of above code snippet :
orange : null
null : 0
apple : 2
pear : 9
pineapple : 6
orange : null
null : 0
apple : 2
pear : 9
pineapple : 6
2.3 TreeMap
The TreeMap class, added in Java 1.2, is a Map that stores elements in a sorted Red-black tree.
The elements of TreeMap are sorted according to the natural order of their key (if they implement the Comparable interface) or by using an instance of type Comparator supplied to the constructor of TreeMap.
The TreeMap class is not synchronized.
To obtain a synchronized instance, it has to invoke the synchronizedSortedMap() method of the Collections class :
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…));
import java.util.Map.Entry;
import java.util.Collections;
import java.util.Iterator;
import java.util.TreeMap;
public class TreeMapTest {
public static void main(String[] args) {
TreeMap<Integer, String> fruits = new TreeMap<>();
fruits.put(2, "pear");
fruits.put(1, "apple");
fruits.put(4, "banane");
fruits.put(5, "melon");
fruits.put(3, "strawberry");
Iterator<Entry<Integer, String>> it = fruits.entrySet().iterator();
while (it.hasNext()) {
Entry<Integer, String> fruit = it.next();
System.out.println(fruit.getKey() + " : " + fruit.getValue());
}
System.out.println();
fruits = new TreeMap<>(Collections.reverseOrder());
fruits.put(2, "pear");
fruits.put(1, "apple");
fruits.put(4, "banane");
fruits.put(5, "melon");
fruits.put(3, "strawberry");
for (int id : fruits.keySet()) {
System.out.println(id + " : " + fruits.get(id));
}
}
}
The output of above code snippet is below :
1 : apple
2 : pear
3 : strawberry
4 : banane
5 : melon
5 : melon
4 : banane
3 : strawberry
2 : pear
1 : apple
2.4 EnumMap
The EnumMap class, added in Java 5, is an implementation of the Map interface which can only use elements of an enumeration as keys.
It has several characteristics :
- All values usable as keys must belong to the same enumeration;
- It is not possible to use the value null as key otherwise an exception of type NullPointerException is raised when adding the element;
- The value associated with the key can be null.
Internally, the storage of the elements is done in an array.
The EnumMap class is not synchronized, it is possible to use synchronizedMap() method of Collections to make it synchronized.
Map<MonEnum, String> map = Collections.synchronizedMap(new EnumMap<MonEnum, String>());
import java.util.EnumMap;
public class EnumMapTest {
public static void main(String[] args) {
enum DayOfWeek {
MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY
}
EnumMap<DayOfWeek, String> activities = new EnumMap<>(DayOfWeek.class);
activities.put(DayOfWeek.MONDAY, "working");
activities.put(DayOfWeek.TUESDAY, "working");
activities.put(DayOfWeek.WEDNESDAY, "working");
activities.put(DayOfWeek.THURSDAY, "working");
activities.put(DayOfWeek.FRIDAY, "working");
activities.put(DayOfWeek.SATURDAY, "sleeping");
activities.put(DayOfWeek.SUNDAY, "sleeping");
for (DayOfWeek day : activities.keySet()) {
String activity = activities.get(day);
System.out.println(day + " : " + activity);
}
}
}
Below is the output of above code snippet :
MONDAY : working
TUESDAY : working
WEDNESDAY : working
THURSDAY : working
FRIDAY : working
SATURDAY : sleeping
SUNDAY : sleeping
2.5 IdentityHashMap
The IdentityHashMap class, added in Java 1.4, is an implementation of the Map interface that uses an equality test on references (usually Map interface implementations uses object equality).
Two keys key1 and key2 are therefore equal if key1 == key2.
It is therefore not a general-purpose implementation, but its use is limited to a few specific cases, such as keeping track of the objects used during serialization or cloning operations.
The IdentityHashMap class is not synchronized.
We can use the method synchronizedMap() of Collections to make it synchronized :
Map map = Collections.synchronizedMap(new IdentityHashMap());
import java.util.HashMap;
import java.util.IdentityHashMap;
public class IdentityHashMapTest {
public static void main(String[] args) {
Person p1 = new Person(1, "tom");
Person p2 = new Person(1, "tom");
HashMap<Person, Integer> hmap = new HashMap<>();
hmap.put(p1, 100);
hmap.put(p2, 200);
System.out.println("Number of elements in hash map : " + hmap.size());
for (Person p : hmap.keySet()) {
System.out.println(p + " : " + hmap.get(p));
}
System.out.println();
IdentityHashMap<Person, Integer> imap = new IdentityHashMap<>();
imap.put(p1, 100);
imap.put(p2, 200);
System.out.println("Number of elements in identity hash map : " + imap.size());
for (Person p : imap.keySet()) {
System.out.println(p + " : " + imap.get(p));
}
System.out.println();
p1.name = "jerry";
System.out.println(hmap.containsKey(p1));
System.out.println(imap.containsKey(p1));
}
private static class Person {
private int id;
private String name;
public Person(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
if (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
@Override
public String toString() {
return "Person [id=" + id + ", name=" + name + "]";
}
}
}
Below is the output of above code snippet :
Number of elements in hash map : 1
Person [id=1, name=tom] : 200
Number of elements in identity hash map : 2
Person [id=1, name=tom] : 100
Person [id=1, name=tom] : 200
false
true
2.6 WeakHashMap
The WeakHashMap class, added in Java 1.2, is an implementation of a Map whose keys are stored with WeakReference.
It automatically removes items whose key was garbage collected.
A key is not stored directly in a WeakHashMap : it is a weak reference to the instance that is stored.
An object that encapsulates a value is stored in the WeakHashMap with a strong reference.
If the object used as the key is no longer referenced by other objects, the garbage collector will pick it up and the item will be removed from the map.
It must be sure to use as keys only objects that can be recovered by the garbage collector : for example, it must not use character strings whose value is hard-coded.
The WeakHashMap class is often used as an implementation of a cache.
import java.util.HashMap;
import java.util.Map;
import java.util.WeakHashMap;
import java.util.concurrent.TimeUnit;
public class WeakHashMapTest {
public static void main(String[] args) throws InterruptedException {
Person p = new Person(1, "tom");
Map<Person, Integer> map = new HashMap<>();
map.put(p, 100);
System.out.println("Size of HashMap before setting key to null : " + map.size());
p = null;
System.gc();
TimeUnit.SECONDS.sleep(5);
System.out.println("Size of HashMap after setting key to null : " + map.size());
System.out.println();
map = new WeakHashMap<>();
p = new Person(2, "jerry");
map.put(p, 100);
System.out.println("Size of WeakHashMap before setting key to null : " + map.size());
p = null;
System.gc();
TimeUnit.SECONDS.sleep(5);
System.out.println("Size of WeakHashMap after setting key to null : " + map.size());
}
private static class Person {
private int id;
private String name;
public Person(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
if (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
@Override
public String toString() {
return "Person [id=" + id + ", name=" + name + "]";
}
}
}
Below is the output of above code snippet :
Size of HashMap before setting key to null : 1
Size of HashMap after setting key to null : 1
Size of WeakHashMap before setting key to null : 1
Size of WeakHashMap after setting key to null : 0
2.7 LinkedHashMap
The LinkedHashMap class, added in Java 1.4, is a Map implementation that uses a doubly linked list to maintain its elements in their insertion order by default.
When creating a LinkedHashMap, it is possible to give a boolean value (accessOrder) as a parameter to specify the order of the elements :
- False : elements are sorted in their insertion order;
- True : items are sorted from least accessed to most accessed.
This feature can be interesting to create an LRU cache.
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class LinkedHashMapTest {
public static void main(String[] args) {
// Insertion Order
// Map<Integer, String> map = new HashMap<>();
Map<Integer, String> map = new LinkedHashMap<>();
map.put(5, "five");
map.put(4, "four");
map.put(3, "three");
map.put(2, "two");
map.put(1, "one");
System.out.println(map.keySet().toString());
System.out.println();
// Access Order
map = new LinkedHashMap<>(16, .75f, true);
map.put(5, "five");
map.put(4, "four");
map.put(3, "three");
map.put(2, "two");
map.put(1, "one");
Set<Integer> keys = map.keySet();
System.out.println(keys.toString());
map.get(4);
System.out.println(keys.toString());
map.get(1);
System.out.println(keys.toString());
map.get(3);
System.out.println(keys.toString());
}
}
The output of above code snippet is below :
[5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]
[5, 3, 2, 1, 4]
[5, 3, 2, 4, 1]
[5, 2, 4, 1, 3]
2.8 ConcurrentHashMap
The ConcurrentHashMap class, added in Java 1.5, implements the ConcurrentMap interface which uses a HashMap ensuring concurrency and performance.
Its purpose is to replace the Hashtable class as it is similar to it with better concurrency handling.
Internally ConcurrentHashMap uses segments, so access to find an element and the updates of elements do not block the entire HashMap.
One of the constructors expects a parameter named concurrencyLevel which corresponds to this number of segments.
Ideally, the value of the concurrencyLevel parameter should be at least equal to the number of threads that can update the collection concurrently :
- If the value is too small, there is a risk of having contention;
- If the value is really too large, there is excessive consumption of the required memory.
The ConcurrentHashMap class is optimized for common operations but some operations can be expensive: this is particularly the case of the size() method which places a lock on all segments to calculate the number of elements each contains.
import java.util.HashMap;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
public class ConcurrentHashMapTest {
public static void main(String[] args) throws InterruptedException {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
// HashMap<String, Integer> map = new HashMap<>();
String key = "test";
map.put(key, 0);
ExecutorService es = Executors.newFixedThreadPool(5);
try {
for (int i = 0; i < 10000; i++) {
es.execute(() -> {
map.computeIfPresent(
key,
(k, v) -> v + 1);
});
}
} finally {
es.shutdown();
es.awaitTermination(5, TimeUnit.SECONDS);
}
int cnt = map.get(key);
System.out.println(cnt);
}
}
Below is the output of above code snippet :
10000
2.9 ConcurrentSkipListMap
The ConcurrentSkipListMap class, added in Java 6, is an implementation of the ConcurrentNavigableMap interface using a SkipList-like algorithm.
The functionality offered by the ConcurrentSkipListMap class can be seen as a fusion of the functionality of ConcurrentHashMap and TreeMap classes.
The elements of ConcurrentSkipListMap are sorted according to their natural order by implementing the Comparable interface or by using an instance of the Compator type provided as a parameter of the constructor.
The ConcurrentSkipListMap class has several characteristics :
- It allows concurrent modification without blocking;
- It is optimized for read operations that are non-blocking;
- By default, the elements are sorted according to their natural order or according to the order defined by the instance of Comparator associated with it;
- The use of null is not possible neither for the key nor for the value of an element.
The ConcurrentSkipListMap class offers better scalability of concurrent access than the ConcurrentHashMap class.
The performances of the basic operations are situated on average in log(n).
import java.util.Iterator;
import java.util.concurrent.ConcurrentSkipListMap;
public class ConcurrentSkipListMapTest {
public static void main(String[] args) {
ConcurrentSkipListMap<String, String> map = new ConcurrentSkipListMap<String, String>();
map.put("3", "World");
map.put("2", "Hello");
map.put("1", "Hi!");
System.out.println("Initial Map : " + map);
System.out.println();
Iterator<String> it = map.descendingKeySet().iterator();
while (it.hasNext()) {
String key = (String) it.next();
System.out.println(key + " : " + map.get(key));
}
System.out.println();
System.out.println("firstEntry: " + map.firstEntry());
System.out.println("lastEntry: " + map.lastEntry());
}
}
Below is the output of above code snippet :
Initial Map : {1=Hi!, 2=Hello, 3=World}
3 : World
2 : Hello
1 : Hi!
firstEntry: 1=Hi!
lastEntry: 3=World
3. The choice of a map implementation
Several implementations of Map interface are useful for some particular situations :
- The EnumMap class should only be used if the keys are elements of an enumeration;
- WeakHashMap class stores keys with weak references and it is useful to implement an efficient memory cache;
- The IdentityHashMap class can be used if we want to treat two objects as equal only if they are the same instance.
For a sorted Map, the TreeMap class must be used if there is no concurrent use, otherwise the ConcurrentSkipListMap class must be used.
Three classes can be used in a general and non-competitive context.
The criterion of choice is essentially the sort order of the elements that the map should use :
- HashMap : no precise order for the elements which must have the implementation of their hashCode() and equals() methods correctly coded;
- TreeMap : the natural order of the elements or the order defined by the Comparator type instance associated with the collection;
- LinkedHashMap : the order of elements is their insertion order.
If the map can be used concurrently, multiple classes can be used :
- Hashtable : the methods of this class being synchronized, the performances are not too good under strong concurrency;
- ConcurrentHashMap : the locks are only placed on the elements being modified and the get() method is not blocking;
- ConcurrentSkipListMap : maintains the order of its elements and offers a quick scan at the cost of an additional cost during insertion.