I am trying to implement a custom HashMap for multithreading environment. Why is this giving inconsistent results? I think multiple threads are accessing the put method simultaneously.
class Main{
public static void main(String[] args){
CustomMap<Integer,Integer> m = new CustomMap<>();
Thread thread1 = new Thread(new MyThread(m));
Thread thread2 = new Thread(new MyThread(m));
thread1.start();
thread2.start();
try{
thread1.join();
thread2.join();
}
catch(InterruptedException e){
System.out.println("interrupted exception");
}
for(int i=0;i<1000;i++){
System.out.println(i + " -> " + m.get(i));
}
}
}
class MyThread implements Runnable{
CustomMap<Integer,Integer> m;
public MyThread(CustomMap<Integer,Integer> m){
this.m = m;
}
public void run(){
for(int i=0;i<1000;i++){
m.put(i,m.getOrDefault(i,0)+1);
}
}
}
class CustomMap<K,V>{
private final int INITIAL_SIZE = 16;
private int size;
private int capacity;
private Node<K,V>[] hashTable;
public static class Node<K,V>{
private K key;
private V value;
private Node<K,V> next;
Node(K key, V val){
this.key = key;
this.value = val;
}
public V getValue(){
return this.value;
}
public Node getNext(){
return this.next;
}
public K getKey(){
return this.key;
}
}
public CustomMap(){
hashTable = (Node<K, V>[]) new Node[INITIAL_SIZE];
this.capacity = INITIAL_SIZE;
size = 0;
}
public int getHash(K key){
return key == null ? 0 : Math.abs(key.hashCode()) % capacity;
}
public synchronized void put(K key, V value){
int idx = getHash(key);
if(hashTable[idx]==null){
hashTable[idx] = new Node<>(key,value);
size++;
}
else{
Node<K,V> curr = hashTable[idx];
Node<K,V> prev = curr;
while(curr !=null){
if((key == null && curr.key == null) || (key != null && key.equals(curr.key))){
curr.value = value;
return;
}
prev = curr;
curr = curr.next;
}
prev.next = new Node<>(key,value);
size++;
}
}
public synchronized V get(K key){
int hash = getHash(key);
if(hashTable[hash]==null){
return null;
}
else{
Node<K,V> curr = hashTable[hash];
while(curr != null){
if((key == null && curr.key == null) || ( key!=null && key.equals(curr.key))){
return curr.value;
}
curr = curr.next;
}
return null;
}
}
public synchronized V getOrDefault(K key, V defaultVal){
V val = get(key);
return val != null ? val : defaultVal;
}
}
m.put(i, m.getOrDefault(i, 0) + 1)-- This isn't atomic. You aren't holding the lock between theputandgetOrDefaultcalls. So, thread A callsgetOrDefaultand gets0, then thread B calls the same method and also gets0, then both threads add0 + 1to get1, and finally both threads callput(i, 1). But sometimes thread A or B will perform the whole operation before the other thread even callsgetOrDefaultfor a giveni, leading to the second thread to callput(i, 1 + 1). Thus, inconsistent results.getOrDefaultmethod is synchronized. Making that method synchronized is not enough; you also need to dosynchronized (m) { m.put(i, m.getOrDefault(0, 1) + 1); }.