-1

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;
    }
}
7
  • 2
    Please be much more specific about (a) the nature of the inconsistent results, and (b) what steps you have taken to attempt to debug this. Commented Jan 25 at 18:54
  • 8
    m.put(i, m.getOrDefault(i, 0) + 1) -- This isn't atomic. You aren't holding the lock between the put and getOrDefault calls. So, thread A calls getOrDefault and gets 0, then thread B calls the same method and also gets 0, then both threads add 0 + 1 to get 1, and finally both threads call put(i, 1). But sometimes thread A or B will perform the whole operation before the other thread even calls getOrDefault for a given i, leading to the second thread to call put(i, 1 + 1). Thus, inconsistent results. Commented Jan 25 at 18:54
  • @Slaw making getOrDefault synchronized it also giving inconsistent results Commented Jan 25 at 18:59
  • 1
    I saw your question after your edit, so my comment was made with the knowledge that your getOrDefault method is synchronized. Making that method synchronized is not enough; you also need to do synchronized (m) { m.put(i, m.getOrDefault(0, 1) + 1); }. Commented Jan 25 at 19:03
  • @Slaw if i am using synchronized (m) { m.put(i, m.getOrDefault(0, 1) + 1); } is it required to make put, getOrDefault methods synchronized? Commented Jan 25 at 19:17

1 Answer 1

7

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.

Sign up to request clarification or add additional context in comments.

4 Comments

As a followup, to 'fix' this, you have to move the synchronization to a wider scope. Either the caller does the synchronization, or, the map offers more 'primitives' - whatever you want 'synchronized' must be done in one single method or 'synchronized' won't do what you want. computeIfAbsent (already exists, on Map) is what you want here. This is why Collections.synchronizedMap / Hashtable are strongly disrecommended; that's not how you go about 'thread safety', and this question+answer shows why.
@rzwitserloot in this case map.merge(i, 1, (a, b) -> a + b) is probably better. If there is no entry for i then it will simply add an entry with value 1. Otherwise it will take the existing value, add the 1 to it, and use that as new value. Using that on a ConcurrentHashMap means the custom map implementation isn't even necessary.
The CustomMap must be replaced by a ConcurrentHashMap or Collections.synchronizedMap then, as it isn’t a Map implementation, so it doesn’t have the merge method (but inheriting the default method wouldn’t work either, as it’s still not atomic). This demonstrates (again) why reinventing the wheel is not a good idea. There are other pitfalls lying around, e.g. the custom map doesn’t consider that Math.abs(key.hashCode()) can be negative.
You're right on all accounts. Especially the latter is a tricky one to notice, as it only occurs if key.hashCode() returns Integer.MIN_VALUE (as documented!)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.