In ConcurrentHashMap how the segments are defined
Hello friends I am new to Java Concurrency. I have 2 questions as below.
Q.1 In ConcurrentHashMap how the segments are defined? Means if there are 64 elements in that Map and concurrencyLevel value as 16 (there are 16 threads that can work simultaneously) then how the segments are defined? The Q is are they equal sized 16 segments with 4 elements in each? Or it will be unequal sized segments?
Q.2. If I define ConcurrentHashMap with initial capacity as 62 and concurrencyLevel as 16. If I put 62 elements in that map. As per my understanding there will be 15 segments with 4 elements each and 16th segment will have 2 elements? Am I correct here?
Thanks in advance
Q.1 In ConcurrentHashMap how the segments are defined? Means if there are 64 elements in that Map and concurrencyLevel value as 16 (there are 16 threads that can work simultaneously) then how the segments are defined? The Q is are they equal sized 16 segments with 4 elements in each? Or it will be unequal sized segments?
ANS - IF you defined 16 as Concurrency level then 16 Segments will be creating.
Each segment internally maintains of HashTable S[0] -> HASHTABLE().
So if you have 64 Elements then for each element Hash(Key) will calculate segment number you may have all segment with unequal size. Segment hashcode is calculated in such a way that it will return you any number between (0-15).
Q.2. If I define ConcurrentHashMap with initial capacity as 62 and concurrencyLevel as 16. If I put 62 elements in that map. As per my understanding there will be 15 segments with 4 elements each and 16th segment will have 2 elements? Am I correct here?
ANS- As explained above each selection of segment is done based on calculated hashcode so it is not certain that all the 16 segment will be of same size.
Think of implementations of ConcurrentHashMap which use segments (not all do) as basically being a two-level hash table. Given a key, K , and the hashcode for the key h = K.hashCode() , you first hash into your array of 16 segments using h , just like a normal hash map (eg, by taking h % 16 or something like that). This gives you the segment your key lives in, this is just another map - again use h to look up the key within this map.
The difference is that any locking operations, which generally occur during mutating operations like put() , only need to lock the involved segment, so other operations have a chance to proceed in parallel.
To answer your questions specifically:
Q1
The segments are equally sized in capacity, but they will, in general, have unequal number of elements because the segment for the elements are selected using hashing, which won't result in a perfectly uniform except in unusual cases. It's the same as if you asked if the first half the array backing in a HashMap has the same number of elements as the second half. On average the expected number of elements is the same, but for any given HashMap it's highly unlike to have exactly the same number of elements in both halves, due to random variation.
Q2
No, the map will not be laid out like that. As above, the selection of elements into segments is done using a hash, which means (for a good hash function) the segments are chosen essentially at random. Imagine you had a jar of balls marked from 1 to 16, and you chose one ball at a time, 62 times, and recorded the number you got before replacing the ball. You would not expect to get a distribution like 4, 4, 4, 4, 4, 4, 4, 4, 4, ... , 4, 2, 2] ! It would be more random.