Why HashMap should not be used in multi threaded environment?
Can it cause infinite loop as well?
When get method go to infinite loop in HashMap?
If HashMap is used in Multi threading environment, there are chances that Get and Put operation can lead you to Infinite loop.
Overview
Default capacity of HashMap is 16 and Load factor is 0.75, which means HashMap will double its capacity when 12th Key-Value pair enters in map (16 * 0.75 = 12).
For more details on Load Factor, Please refer: What is Load factor and Rehashing in Hashmap?
What will happen when 2 Threads try to put 12th Key-Value pair in HashMap?
When 2 Thread tries to access HashMap simultaneously, then you may encounter infinite Loop.
Let see how it happens,
Thread 1 and Thread 2 tries to put 12th key-value pair.
Thread 1 got execution chance.
1. Thread 1 tries to put 12th key-value pair,
2. Thread 1 founds that Threshold limit is reached and it creates new Buckets of increased capacity.
So map's capacity is increased from 16 to 32.
3. Thread 1 now transfers all existing key-value pairs to new buckets.
4. Thread 1 points to first key-value pair and next(second) key-value pair to start transfer process.
Thread 1 after pointing to key-value pairs and before starting the transfer process, loose the control and Thread 2 got a chance for execution.
Thread 2 got execution chance.
1. Thread 2 tries to put 12th key-value pair,
2. Thread 2 founds that Threshold limit is reached and it creates new Buckets of increased capacity.
So map's capacity is increased from 16 to 32.
3. Thread 2 now transfers all existing key-value pairs to new buckets.
4. Thread 2 points to first key-value pair and next(second) key-value pair to start transfer process.
5. While transferring key-value pairs from old buckets to new buckets, key-value pairs will be
reversed in new buckets because hashmap will add key-value pairs at the start and not at the end.
Hashmap adds new key-value pairs at start to avoid traversing linked list every time and keep
constant performance.
6. Thread 2 will transfer all key-value pairs from old buckets to new buckets and Thread 1 will get
chance for execution.
Thread 1 got execution chance.
1. Thread 1 before leaving control was pointing to first element and next element of old bucket.
According to Thread 1, Next element of (1, val) is ("a", val) but actually it is not because Thread 2 has changed Next element of (1, val) to (90, val).2. Now when Thread 1 started putting key-value pairs from old bucket to new bucket,
It successfully puts (90, val) and (1, val) in new Bucket.
3. When it tries to add next element of (1, val) which is (90, val) into new Bucket, it will end up in
infinite loop.
Lets understand with few operations.
HashMap Methods.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
The next size value at which to resize (capacity * load factor). int threshold;
//This method is called when "put" method is called. It checks if total number of key-value pairs in
//map reached Threshold limit, then it resizes the buckets and transfers key-value pairs to new buckets.
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
//This method increase buckets and calls transfer method to transfers key-value pair to new buckets.
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);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
//This method transfers key-value pairs from old buckets to new buckets.
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next; //Thread 1 executed till this point before Thread 2 got chance to execute.
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
You may also like to see
What is Hashmap data structure? What is the need of Hashmap? How Hashmap data structure works in Java? What is Hashcode? Can 2 objects have same hashcode?
How Hashmap data structure works internally? How hashcode and equals method is used in hashmap? Explain with real time example.
How time complexity of Hashmap get() and put() operation is O(1)? Is it O(1) in any condition?
What is Load factor and Rehashing in Hashmap?
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
0 Response to "Infinite loop in HashMap"
Post a Comment