3

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?

steffen
  • 16,138
  • 4
  • 42
  • 81
lryk
  • 63
  • 7
  • Question 1 is answered here: http://stackoverflow.com/a/9298113/1343161 – Keppil Aug 13 '15 at 14:36
  • @Keppil No, there's only an answer for `null` values. – steffen Aug 13 '15 at 14:44
  • Hmm. The first part of the answer mentions `null` in general in concurrent maps, but the example only uses `null` as value. However, the original linked answer is also to a question regarding both keys and values, so I interpret the first part about the ambiguity to be the reason for both. – Keppil Aug 13 '15 at 14:50
  • @Keppil Can you please elaborate a bit on what are the ambiguities in case we have a null key – lryk Aug 13 '15 at 14:53
  • @Keppil The arguments for not supporting `null` values (ambiguities) are easily comprehensible - in contrast to `null` keys. My guess is there's actually no specific reason for it. – steffen Aug 13 '15 at 15:00
  • The language has moved in the direction of not supporting null for _any_ new collection types, with good reason frankly. Guava, for example, did research demonstrating that for 95% of collections, it would be a bug to encounter null, so all of Guava's immutable collections reject null outright. – Louis Wasserman Aug 13 '15 at 16:06

3 Answers3

1
  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.
V G
  • 18,822
  • 6
  • 51
  • 89
  • `HashMap` does allow `null` as key, `ConcurrentHashMap` on the other hand does not. – Keppil Aug 13 '15 at 14:54
  • 1
    @Andrei I think, the OP question is in regards to the design decision: why doesn't the author want null keys? It's pretty obvious, that there was some solution for that NPE , if the creator of ConcurrentHashMap would want to allow null. – SME_Dev Aug 13 '15 at 14:58
  • 1
    (1) `Objects.hash()` returns `0` for `null`. – steffen Aug 13 '15 at 15:01
  • 1
    @steffen `Objects` (not `Object`) is there since Java 7. Older versions did nor have this, so `object.hash()` had to be called. Implementations of HashMap matches indeed null to the hash key 0. – V G Aug 13 '15 at 15:03
1

[...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.

Solomon Slow
  • 25,130
  • 5
  • 37
  • 57
0

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).

steffen
  • 16,138
  • 4
  • 42
  • 81
  • The phrases "_I guess_" and "_probably a little_" make it unclear whether this is an answer or a shot in the dark. – jaco0646 Aug 13 '15 at 16:19
  • 1
    @jaco0646 While the source code contains lots of comments about the implications of `null` values, there's nothing about `null` keys except for they are unsupported! I think all code concerning map keys could deal with `null`, especially because they are wrapped in `Node` instances. The class contains about 6000 lines, and I didn't talk to the author so I can't tell, why he decided to not support `null` keys. Therefore writing _i guess_ is the most precise thing I can do. – steffen Aug 13 '15 at 16:55