3

Say I have a hash map and multiple threads. If I have a synchronized method that adds to the hash map, how would I make it possible that two different threads can put different keys simultaneously (concurrently) into the hash map?

My current implementation is a synchronized method. Would this allow two different threads to put two different keys simultaneously into the hash map?

I am using a regular hash map, not Java's concurrent hash map. I am not allowed to use a concurrent hash map.

EDIT: I think I found a solution! I think I may have miswrote this post. Let's say that the hash map is initialized as a Integer as its key and a LinkedList as its value. In order to put a totally new key, I realize that the whole hash map has to be synchronized (i.e. locked). However, if I am trying to add another String into an already contained key's corresponding LinkedList, I can just synchronize the hash map's get method. I think this will allow multiple threads to simultaneously (concurrently) add to the LinkedLists of different, already contained keys. Please let me know if I'm wrong.

Here's a concrete example. I have a hash map hashMap that uses an Integer as its key and a LinkedList as its value. The keys 5, and 10 are already in the hash map. The key 5 contains a LinkedList of Joey, Joe, Kerry. The key 10 contains the LinkedList of Jerry, Mary, Tim. I have two threads t1 and t2. t1 wants to add Moe to the LinkedList corresponding to key 5. t2 wants to add Harry to the LinkedList corresponding to key 10. Both will be concurrently added to the hash map, since the hash map's value is only locked.

Improve this question
5
  • "Would this allow two different threads to put two different keys simultaneously into the hash map?" <-- well, if your map is only accessed from within this method, the answer is no
    – fge
    Commented Dec 9, 2014 at 20:45
  • It would be better if you provide the piece of code to analyze rather than just describing it. And maybe you should have another method called putIfAbsent where the value will be set only if such key doesn't exist before.
    – Luiggi Mendoza
    Commented Dec 9, 2014 at 20:46
  • Concurrent insertions will corrupt the internal record keeping of HashMap. This is why ConcurrentHashMap was created.
    – Joni
    Commented Dec 9, 2014 at 20:47
  • @Joni Not if each method is synchronized.
    – yshavit
    Commented Dec 9, 2014 at 20:47
  • @Joni If the method that calls map.put is itself synchronized, then HashMap will benefit from that synchronization. Of course, all getters (get(..), the iterators, size(), etc) must also be synchronized under the same lock.
    – yshavit
    Commented Dec 9, 2014 at 20:49

4 Answers 4

Reset to default
2

My current implementation is a synchronized method. Would this allow two different threads to put two different keys simultaneously into the hash map?

No. Only a ConcurrentHashMap or a specifically designed concurrent map would support this safely, so it's impossible for you to put two keys simultaneously into the same map from two threads.

how would I make it possible that two different threads can put different keys simultaneously (concurrently) into the hash map?

You cannot, without using ConcurrentHashMap, another ConcurrentMap implementation, or implementing your own.

Improve this answer
3
  • I guess OP's asking how to implement its own ConcurrentHashMap#put.
    – Luiggi Mendoza
    Commented Dec 9, 2014 at 20:50
  • That's an extremely complicated and tricky subject, for which my best advice is to read the implementations of other concurrent map implementations.
    – Louis Wasserman
    Commented Dec 9, 2014 at 20:51
  • 1
    And if that's the case, the OP should ask a new question. This one is kinda stuck on his original idea of a synchronized HashMap, which doesn't work.
    – markspace
    Commented Dec 9, 2014 at 20:53
0

The easiest answer is to use a ConcurrentHashMap, which does exactly what you're looking for.

If you can't do that (I see you edited your post after I answered), then you'll have to duplicate the same thing that ConcurrentHashMap does. No, simply synchronizing the method of a HashMap will not allow two threads to add a key-value pair at the same time, they have to wait and go one at a time.

Improve this answer
4
  • 1
    That's not the answer to OP's specific question.
    – Luiggi Mendoza
    Commented Dec 9, 2014 at 20:44
  • Also, read OP's question again: I am not allowed to use a concurrent hash map.
    – Luiggi Mendoza
    Commented Dec 9, 2014 at 20:46
  • 1
    Read my post: he added that after I answered.
    – markspace
    Commented Dec 9, 2014 at 20:47
  • Still the ConcurrentHashMap is not the answer. Keeping my downvote.
    – Luiggi Mendoza
    Commented Dec 9, 2014 at 20:48
0

The answer to your question is NO. Because synchronized block forces every tread to wait in the single queue. With ConcurrentHashMap you have more chances for simultaneously add, because it locks only basket where element will be inserted instead of locking whole HashMap.

Improve this answer
0

However, if I am trying to add another String into an already contained key's corresponding LinkedList, I can just synchronize the hash map's get method. I think this will allow multiple threads to simultaneously (concurrently) add to the LinkedLists of different, already contained keys.

Read-only access to a HashMap is safe: you can have multiple threads call the get method with no synchronization at all and nothing breaks. If the linked lists are not shared between threads you don't need synchronization either. To be sure the threads never share a list the map key should be something specific to the thread, like an object created locally or the thread ID.

What's not safe is to let another thread modify a map or a list concurrently with a read or write. This is the use case for a read-write lock: it allows multiple concurrent reads but writes have to be exclusive.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.