CODEWITHSUNDEEP
javamultithreadingconcurrencyhashmap
lryk
lryk

Reputation: 83

Concurrent HashMap Null key and concurrency level

Can someone please provide answers for the following questions:

  1. I understand the reason why null value is not allowed in ConcurrentHashMap. But why is a null key not allowed?

  2. The concurrency level determines how many threads can concurrently access the map and the default value is 16. This means map is divided into 16 parts and lock is placed on each of the part. This works fine as long as initial capacity is also 16 so there are 16 buckets and 16 locks which works out one lock per bucket. How does this work when the initial capacity is greater than concurrency level and also in case of initial capacity lesser than concurrency level?

Upvotes: 3

Views: 608

Answers (3)

Solomon Slow
Solomon Slow

Reputation: 27125

[...the] map is divided into 16 parts and lock is placed on each of the part. This works fine as long as initial capacity is also 16 so there are 16 buckets and 16 locks which works out one lock per bucket.

Why do you assume that each of 16 threads is going to want to access a different bucket? What if they all want to access the same bucket?

Don't think of it as 16 different buckets, think of it as 16 completely different sub-tables. The hash, k.hashCode(), determines not only in which bucket of a table the key k belongs, but also in which sub-table.

If two threads are interested in two unrelated keys, j, and k, Then the probability is 15/16 that the keys belong to different sub-tables and, that the threads can access the tables with no contention. The other 1/16 of the time, it's tough luck, and one of the threads will have to wait; but that's a whole lot better than the case where they collide 100% of the time.

Upvotes: 1

steffen
steffen

Reputation: 16968

Question 1 I guess supporting null keys would be possible in general. But that would have an impact on readability and probably a little impact on performance. The latter stands in conflict with the goal to provide a high-performance multithreading map implementation.

Question 2 If the initial capacity is less than the expected level of concurrency, the initial capacity is adjusted to the estimated threads accessing the Map (initialCapacity = concurrencyLevel). Apart from that, concurrent access to the ConcurrentHashMap is largely independent from the capacity as threads lock whole buckets on access (to be more specific, they lock the first element from a bucket).

Upvotes: 0

V G
V G

Reputation: 19002

  1. Why null keys are not allowed in ConcurrentHashMaps? HashMap takes its internal keys from Object.hash() which cannot be computed for null values. In order to solve this problem, non-concurrent HashMaps map the null to the hash code 0. In order to solve this problem in ConcurrentHashMap the performance should be PROBABLY sacrificed.
  2. Check the implementation of ConcurrentHashMap: even if you try to set the initalCapacity to something, it makes its own internal computations, so those arguments are rather hints.

Upvotes: 1

Related Questions