ConcurrentHashMap
Published by Kaustubh Saha on December 31st, 2018
A ConcurrentHashMap is a thread safe implementation of a hash table data structure. A ConcurrentHashMap has the same functional specifications as HashTable with the performance benchmarks comparable to a HashMap. Before we look into ConcurrentHashMap's internal structure, let's have a look at HahMap's internal implementation first.
HashMap
There have been several improvements made to HashMap class over the years most notably in Java 1.8. Let's look at the pre Java 1.8 implementation first
HashMap maintains an array of buckets. Each bucket is a linked-list of key value pairs encapsulated as Entry objects. This array of buckets is called table. Each node of the linked list is an instance of a private class called Entry
transient Entry[] table;
An entry is a private static class inside HashMap which implements Map.Entry
private static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
final int hash;
V value;
Entry<K,V> next;
}
Each entry object exists only for a particular key but values may change (if same key is reinserted later with a different value) - hence key is final while value is not
Each Entry object has a field called next which points to the next Entry thus behaving like a singly linked list. The hash field stores the hashed value of the key
HashMap provides overloaded constructors with parameters for initial capacity and load factor but typically no args constructor is the one most frequently used
default values of these fields are :
- initial capacity : 1 << 4 (ie 16)
- load factor : 0.75
Whenever the element count of the hashmap reaches the load factor fraction of capacity, the map is resized and capacity is doubled.
If initial capacity provided by client is a power of 2, then real capacity will be same as capacity, else real capacity = nearest power of 2 > provided capacity. (In a short while, we'll see why this is important)
Maximum capacity is 1<<30 (ie 2 ^30) if capacity provided is greater than that, then real capacity = 2^30
Note that capacity indicates the size of the table array (the array of buckets) and not the number of key-value pairs the HashMap can support
Fail Fast Iterator
HashMap specifications require that iterators should throw ConcurrentMoodificationException if the map contents are changed while a client is iterating over an iterator
This done by keeping track of number of modifications. HashMap has a member int variable named modCount which is incremented every time the map is altered (any invocation of put(), remove(), putAll() or clear() methods)
A similar field (lets say iteratorModCount) is maintained in the iterator implementation class. When the iterator is created, the iteratorModCount value is initialized with the same value as HashMap modCount. For every call to any of iterator methods (next(), hasNext() and remove() ) the iteratorModCount is checked against the HashMap modCount. If these two values don't tally, that means HashMap has been modified and ConcurrentModificationException is thrown
When the remove() method of iterator is invoked, after internally calling remove() on the map, the iteratorModCount is reinitialized with the HashMap's modCount
Note: the HashMap's modCount and iterator's modCount fields are neither atomic nor volatile - hence they are vulnerable to interleaving and are not guaranteed to work correctly in a multithreaded context.
Datastructure representing keySet and values
HashMap specifications require that keySet(), values() and entrySet() methods complete with O(1) space complexity - which basically means HashMap can't copy the data into a new collection and return it. Rather these collections have to point to the same location in memory as the actual HashMap contents
This is done by maintaining non-static inner classes called KeySet and EntrySet both of which extend AbstractSet. By virtue of being non static, they implicitly carry a reference to the outer class object (HashMap.this)
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size ;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap. this.clear();
}
}
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size ;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap. this.clear();
}
}
Now, as we see above, special private classes have been created which internally invoke methods of the outer class.
For the iterators to this classes, special iterator instance is created which iterates over the buckets and entries. This iterator base class HashIterator is again a non static inner class thus having reference to the outer HashMap class through HashMap.this
private abstract class HashIterator <E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount ; // For fast-fail
int index ; // current slot
Entry<K,V> current; // current entry
}
In order to be able to iterate over all the elements successfully, HashIterator needs to keep track of the following :
1. the current entry
2. the index of the current bucket
3. the next entry
4. the expected mod count (for ensuring that it is fail-fast)
at every call to next(), the current field is initialized as next and next is calculated (as well as the index). hasNext() returns false when next is null
For iterating over key, value and entry objects, multiple implementations of HashIterator are provided :
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value ;
}
}
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
Rehashing
As a protection against poorly written hash functions, HashMap rehashes the hashcode of every key.
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
In HashMap the decision regarding which bucket a key should go to is made on the basis of this :
static int indexFor( int hash, int capacity) {
return hash & (capacity-1);
}
Note that capacity is always a power of 2 (ie 1 followed by a sequence of zeroes in binary). So (capacity - 1) is a sequence of 1's in binary. So if the capacity is 2^n, then only the lower n bits of hash are useful and the upper bits beyond that are ignored
Tests show that too many hash functions are not random enough in their lower bits, and that many hashmaps are not large enough to ever use the higher bits
So, as a guard against poorly written hash functions, the hashcodes of the keys are rehashed
- Why is effective capacity always a power of 2 ? *
capacity - 1 will have lower n bits as 1 only when capacity is 2^n. Since the bucket is decided based on bitwise AND between hash value and (capacity - 1), it's important that (capacity - 1) has as many 1 bits as possible in it's binary representation. The only way to guarantee this is by making capacity a power of 2
Dynamic Resizing
As the number of elements in the map grows, the hash chains will grow longer and retrieval time will increase. At some point, it makes sense to increase the number of buckets and rehash the values. Remember finding the correct bucket takes O(1) time (just a bitwise AND operation) while finding the correct entry in the bucket takes O(n) time (iteration over a Linked List). So it makes sense to have more number of buckets instead of having a few crowded buckets
HashMap always doubles up the capacity during resizing. It creates a new bucket array of twice the size and copies data from old array to new array. Then the table variable is reinitialized with the new array
void resize( int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length ;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry [newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
}
During transfer from old array to new array, it iterates over the elements of the old array, for every Entry element computes the new bucket array index and sets the next pointer of that element to the head of the bucket (ie adds elements to the head of the singly linked list). So, the order of the linked list elements are effectively reversed.
Suppose original linkedlist was 1->2->3. Lets assume after resizing, every element again goes into same bucket
So, after first iteration, the new list becomes: 1->null
after second iteration, the list becomes: 2->1->null
after third iteration, the list becomes: 3->2->1->null and thus the link list gets reversed
This creates a potential race condition during resizing. Suppose two threads running in parallel decide that the HashMap needs resizing and try to resize. In the absence of synchronization, due to interleaving, this may lead to an infinite loop by making a linked list node point to itself
Of course the user had no business using HashMap in a multithreaded context to begin with
put operation
The put operation performs the following steps :
1. calculate hashcode for key
2. rehash it. lets call the rehashed results as h
3. calculate bucket index as h & (capacity -1)
4. now iterate over the bucket and compare key with all existing keys using equals()
5. if the key already exists, change the value of that Entry object
6. else create a new Entry object and add to the head of the linked list
7. increment mod count
8. resize if necessary
get operation
The get operation performs the following steps :
1. calculate hashcode for key
2. rehash it. lets call the rehashed results as h
3. calculate bucket index as h & (capacity -1)
4. now iterate over the bucket and compare key with all existing keys using equals()
5. if the key already exists return the corresponding value in the Entry object. If done with iteration and no match can be found for key, return null
Changes to HashMap in Java 8
There have been a few changes to the HashMap implementation in Java 1.8 :
1. If the number of elements in a bucket exceeds a threshold, the inner implementation for a bucket changes from a linked list to a balanced binary search tree. We'll explore this in more details. This JDK 8 change applies only to HashMap, LinkedHashMap and ConcurrentHashMap and not to every Map implementation.
2. The rehashing logic has become much simpler and has changed from
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
to:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
It appears from the code that the new function is a simpler XOR of the lower 16 bits with the upper 16 leaving the upper 16 bits unchanged, as opposed to several different shifts in the previous implementation. This is less effective at allocating the results of hash functions with a high number of collisions in lower bits to different buckets, but saves CPU cycles by having to do less operations.
This is probably because the optimization for bucket inner implementation means that the performance hit due to a poorly distributed hash function is less important, and that the cost-benefit analysis for the hash method changes; i.e. the more complex version is less beneficial on average. (Bear in mind that when the key type's hashcode method generates high quality codes, then gymnastics in the complex version of the hash method are a waste of time.)
HashMap in Java 8 has two internally defined thresholds - the treefy threshold and the untreefy threshold. The treefy threshold is the point (number of elements in a bucket) at which the bucket implementation switches from linked list to a BST whereas the untreefy threshold is for the opposite transition
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
Also there's a minimum capacity (the size of the table array) after which the buckets are considered for tree-fication.
static final int MIN_TREEIFY_CAPACITY = 64;
Note that treefication and untreefecation happen only during resizing
For treefication, HashMap uses a Red Black tree which is a form of self balancing binary search tree. In order to be able to switch form from BST to linked-list or vice versa effectively, the BST nodes are represented using a static inner class called TreeNode which internally extends Entry :
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
That way the same set of nodes can be used either as BST Nodes or as linked list nodes and conversion from one data-structure to another doesn't involve allocating new O(n) number of objects in memory.
- A BST, by definition, works on the principle of comparison but a HashMap keys are not necessarily Comparable, nor does HashMap provide a mechanism to define a Comparator. How does HashMap decide which node goes where in the BST ? *
If the keys are Comparable, then HashMap uses the natural comparison order of keys to navigate/populate the BST. If not, the hash code value of the keys (which is an Integer and is hence always Comparable) decide the comparison order. HashMap uses the following method to determine Comparison class for keys :
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
If the input object to this method if of type Comparable
Once the inner implementation changes to a BST, the time complexity for locating an element within a bucket changes from O(n) to O(log n) improving the performance benchmarks significantly for large maps
Here are a few performance benchmarks for HashMap put and get operations in different versions of Java:
HashMap performance benchmarks
Lock Striping
Clearly HashMap is not thread-safe either in Java 8 or in the earlier implementations and isn't meant to be used in a multithreaded context. We can wrap it with Collections.synchronizedMap() or use a HashTable instead but that would essentially make it single threaded and introduce a high cost of memory barrier (and associated cache flush) because of synchronized method/block.
If you think about HashMap implementation and the operations provided, we actually have race conditions only in the following scenarios (apart from lack of happens-before guarantees):
1. A thread resizing a HashMap's inner table array while other threads are still active.
2. Two threads trying to access same bucket and at least one thread is modifying the bucket
3. A thread iterating over the contents of a HashMap while other threads are modifying the Map
ConcurrentHashMap attempts to solve the 2nd problem listed here by applying the concept of lock striping. Lock Striping is the process of reducing lock contention by using finer grained locks. If you have only one lock for the whole data structure like Array or Map and you are synchronizing it and using it in a multi-threaded environment, then effectively any given time only one thread can manipulate the map, as there is only a single lock. All the other threads would be waiting to get the monitor. So instead of locking down the whole data structure we can lock only that part of the data structure which is undergoing modification. So a thread working on another part of the data structure can continue to do so without being blocked. Consider a single linked list like 1->2 ->3->4->5-> null. Now lets say we have two threads T1 and T2. T1 wants to insert a new element 2.5 between nodes 2 and 3, whereas T2 wants to insert a new element at the end of the linked list. These two operations are not in conflict with each other but if we lock the whole list, only one of them can proceed. On the other hand, if we lock only the two adjacent nodes when inserting a new node, T1 and T2 wont block each other. This process of increasing effective concurrency level of a data structure by splitting a coarse grained lock into multiple fine grained ones is called lock striping.
ConcurrentHashMap
Just like we did with HashMap, we'll explore the structure of ConcurrentHashMap as defined in Java 7 first and then look into Java 8 improvements
ConcurrentHashMap introduces an additional abstraction layer called Segment. A segment is a specialized version of hash table which also extends ReentrantLock. A segment also represents a smaller section of the map which can be locked to ensure mutual exclusion and atomicity. The basic strategy is to subdivide the table among Segments, each of which itself is a concurrently readable hash table. To reduce footprint, all but one segments are constructed only when first needed.
The loadFactor, threshold etc info are stored in segments[0] and segments[0] and is used as a prototype whenever new segments need to be created. While creating new segment CAS is used to make sure that two threads do not parallely end up creating different Segment objects for the same segment index
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K,V>[] table;
transient int count;
transient int modCount;
final float loadFactor;
}
Overall a ConcurrentHashMap can be thought of as an array of Segments.
final Segment<K,V>[] segments;
Note that each Segment contains a table array just like a HashMap and functions like an individual HashMap as well. The table array is an array of HashEntry
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
}
This looks very similar to the static inner class Entry
private static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
final int hash;
V value;
Entry<K,V> next;
}
Unlike Entry
How to determine the number of Segments
In addition to providing similar constructors as that of HashMap, ConcurrentHashMap also provides another constructor which exposes an extra configurable parameter - the concurrency level. This is an indicator of the maximum number of threads that can perform write operations simultaneously without blocking each other
ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
The default value of concurrency level is 16
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
The number of segments to be used is guided by the concurrency level parameter.
if concurrency level is a power of 2,
number of segments = concurrency level
else
number of segments = power of 2 immediately greater than concurrency level
Hashing
Just like HashMap, key hash codes in a concurrenthashmap are rehashed as protection against poorly written hashcode
Determining which Segment and Bucket an entry goes into
For every key hash, the upper bits are used to identify a segment and the lower bits are used to identify a bucket index within the segment. So, HashCode being a 32 bit int variable, maximum number of segments = 2^16
put operation
The put operation performs the following steps :
1. calculate hashcode for key
2. rehash it.
3. calculate the segment index and identify the Segment
4. Acquire lock on the Segment
5. Identify the bucket index
6. now iterate over the bucket and compare key with all existing keys using equals()
7. if the key already exists, change the value of that Entry object
8. else create a new Entry object and add to the head of the linked list
9. increment mod count
10. resize if necessary
get operation
The get operation performs the following steps :
1. calculate hashcode for key
2. rehash it
3. calculate the segment index and the bucket index within a segment
4. now iterate over the bucket and compare key with all existing keys using equals()
5. if the key already exists return the corresponding value in the Entry object. If done with iteration and no match can be found for key, return null
In Java 1.8 the following changes have been made to ConcurrentHashMap :
In Java 8, ConcurrentHashMap implementation changed from array of Segments (and each segment representing an array of LinkedLists) to simple one-dimensional array of Nodes
transient volatile Node<K,V>[] table;
Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
}
Each Node is a table bucket and is initialized only when we put the first entry in that bucket.
One major difference is that unlike HashEntry in Java 7 ConcurrentHashMap a Node isn't a ReentrantLock and hence can't be used for locking. Infact ConcurrentHashMap in Java 8 is largely lock free and uses CAS based optimistic locking wherever needed instead of pessimistic locking.
A few side effects of getting rid of Segments and using pessimistic locking :
1. The concurrency level constructor arg isn't relevant anymore. It is still supported for backward compatibility sake, but it only acts as a hint for initial sizing of the map
2. size() is no longer guaranteed to be accurate. In the earlier versions, a call to size() meant acquiring locks on all the segments, iterating over them and summing up to calculate size. Since now there's no concept of segments and locks, size() can only be an approximate estimate and cant be guaranteed to be accurate
Weakly Consistent Iterators
ConcurrentHashMap (and other concurrent collection classes which rely on CAS) expose weakly consistent iterators and not fail-safe iterators which reflect some but not necessarily all of the changes that have been made to their backing collection since they were created. For example, if elements in the collection have been modified or removed before the iterator reaches them, it definitely will reflect these changes, but no such guarantee is made for insertions. Weakly consistent iterators behave like snapshot iterators - they are guaranteed to traverse elements as they existed upon construction exactly once, and may (but are not guaranteed to) reflect any modifications subsequent to construction. Also they would never throw ConcurrentModificationException as they are not guaranteed to detect modifications.
Posted on December 31st, 2018