Algorithm to create custom ConcurrentHashMap?

Question

I tried to look into concurrent HashMap source code to look in to how it is implemented. To me it looked very difficult to understand((In no way i am saying its not required :))). I thought if i need to implement it myself and how should i go about it. Here is brief algo about it :-

1) Maintain a list of 16(Default) custom lock objects extending Reentrant lock.

2) Lock will have the state(of type AtomicInteger) say lockState which will be 0 if not in use. If somebody has acquired the lock, it will be 1

3) Before any update/create operation (For example :- in PUT operation), CMH will see if any lock in the list is available with lockState.compareAndSet(int 0, int 1) If result of compareAndSet is true then acquire the lock

4) Once done set lockState to 0 again.

This is just skelton and in know there will be much scope of optimization. But just wanted to confirm if i am on write track or you guys see some serious flaw in it? .

• kdgregory: You're missing the most important part: what is being locked. Start with how a hash-table works (it's unclear whether you know that from your post). Then think about how multiple concurrent updates to that table could be managed, and how locks might control those updates. Extra credit: how can reads proceed at the same time as writes.
• M Sach: @kdgregory i know bucket is being lockeg here. I also know how hash-table works here. My proposed solution handles exactly how lock object could control multiple concurrent updates.
• kdgregory: In that case your point #3 is poorly described rather than being completely wrong. I suppose a list of locked buckets (and consequent linear search) would work. The JDK implementation, however, locks segments of the table -- a range of buckets. This is rather more efficient, as it can be done with simple math.

Answer 1

ConcurrentHashMap does not use any Lock instances at all. It uses directly the Unsafe class which calls directly processor instructions (such as compareAndSet or volatile read). This means it's way more faster than with Lock.

What you can do is to use ReadWriteLock instead of ReentrantLock to have a better performance when reading.