Q&A for Work

Setup a private space for you and your coworkers to ask questions and share information. Learn more about Teams

I understand that in HashMap, the entries (Key, Value) are placed in buckets based on hash(Key.hashCode)--> The index that denotes the bucket location. In case an entry is already placed at that location, there is a linked list created and the new entry (if it has different key --> via equals() method) is placed at the beginning of the linked list.

Can i co-relate this concept with that of ConcurrentHashMap, but instead of Buckets, there are Segments upon which individual threads have a lock. And instead of Entries, there are HashEntry(ies). In similar fashion, a linked list is created and if the Key-Value pair being inserted is different, based on equals() of the key, it is placed at end of the linked list.

Am i correct when i say that: put of CHM is not synchronized, thus any thread can access this method, this put method calculates hash value of the key passed to it and gets the segment index (Kinda like buckets). Then for that segment only, it calls the put method. Now under Segment , the put method specifies that there will be a lock(), so that only one thread can alter data in a particular segment, thus concluding that if the concurrency level is 16 there shall be 16 threads and thus these threads will be able to PUT values only one segment at a time.

A bucket is an individual slot in the map's array. This is the same with both HashMap and ConcurrentHashMap . Conceptually, the latter has its array broken into segments (each segment is an array of references), but that's it. Note that the CHM in Java 8 no longer has segments, it's all a single array.

Yes, it's the scheme known as segmented locking . It reduces inter-thread contention, but does not eliminate it.

For pt. 1 in your answer : Does that mean that the buckets in CHM are divided too? And under those segments there are HashEntry linked lists? – Jatin Shashoo Sep 1 '15 at 12:36 Buckets cannot be divided, they are linked lists. A segment is a bucket array, there's just more of them per one map instance. – Marko Topolnik Sep 1 '15 at 13:18 But the structure as i saw in code is like: CHM has an instance of Segment Segment has an instance of HashEntry Where does the bucket come into picture – Jatin Shashoo Sep 1 '15 at 14:29 I guess you saw wrong, both are arrays. grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… and grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… – Marko Topolnik Sep 1 '15 at 14:40 Segment = array of HashEntry. One HashEntry = one bucket. Does that clear your vision? – Marko Topolnik Sep 2 '15 at 6:27

Thanks for contributing an answer to Stack Overflow!

• Please be sure to answer the question . Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.
• Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers .

Related

site design / logo © 2019 Stack Exchange Inc; user contributions licensed under cc by-sa 3.0 with attribution required . rev 2019.9.3.34774