Java synchronization not working properly

Question

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;
    }
}

Answer 1

The synchronized keyword on a method ensures that only one thread, that holds the lock, can call any method marked with synchronized. This lock spans only for the duration of the (first) method call.

However, your line

m.put(i,m.getOrDefault(i,0)+1);

has two separated method calls. The first one is m.getOrDefault(), the second one is m.put(). They both are locked individually with the synchronized keyword, but they are not locked "together". This means you have an execution sequence like this:

m.getOrDefault()  // acquired and released lock

  *nothing*       // object 'm' is not locked here, it's free for everyone

m.put()           // acquired and released lock

The *nothing* part is the time when other threads have a chance to get themself into the synchronized methods since the lock on the object m is released. So one other thread does get into m.getOrDefault() (or m.put()) while you are still trying to increment the stored integer value with your first thread.