• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

ConcurrentHashMap vs synchronizedMap

 
Ranch Hand
Posts: 115
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, am trying to understand the subtleties between these two maps in a multi-threaded environment.

http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html

The iterators returned by the iterator method of the collections returned by all of this class's collection view methods are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.


This means if I have an Iterator going through the LinkedHashMap, I'll get a ConcurrentModificationException if the map is changed (ie insert or remove a key). But does it happen even if I wrap it with Collections.synchronizedMap() like this which is also shown on the page?


http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html

Similarly, Iterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. They do not throw ConcurrentModificationException. However, iterators are designed to be used by only one thread at a time.


Again, this sounds like it will have issues if an Iterator is going through the ConcurrentHashMap, if the map is changed (ie insert or remove a key), except I wouldn't be getting a ConcurrentModificationException. What would be the behavior in this case? Also what does it mean by "iterators are designed to be used by only one thread at a time"? How can it be a concurrent map if I can't do concurrent read from multiple threads?

BTW the JavaDoc doesn't provide an example but I'd imagine usage is as follow ...


But this page suggests the following implementation however.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Cheung wrote:
http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html

The iterators returned by the iterator method of the collections returned by all of this class's collection view methods are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.


This means if I have an Iterator going through the LinkedHashMap, I'll get a ConcurrentModificationException if the map is changed (ie insert or remove a key). But does it happen even if I wrap it with Collections.synchronizedMap() like this which is also shown on the page?



This can happen even if the application is single threaded. Just create a LinkedHashMap(), put in some items, get an iterator, and ... in the loop that processes the iterator, add/remove items from the map. This will cause the exception.

Obviously, this means that the Collections.synchronizedMap() wrapper can't prevent the exception from happening.

Henry
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Cheung wrote:Again, this sounds like it will have issues if an Iterator is going through the ConcurrentHashMap, if the map is changed (ie insert or remove a key), except I wouldn't be getting a ConcurrentModificationException. What would be the behavior in this case?


Well, the docs also say: "Retrievals reflect the results of the most recently completed update operations holding upon their onset."

This is sometimes referred to as "weakly consistent" in that it will return the logically "next" key/value/entry based on the current state of the Map at the time the method is actioned. I suspect also (although it's not explicitly stated, and TBH, I'm not sure) that it means it could possibly throw NoSuchElementException if there is no "next" element to be had.

Also what does it mean by "iterators are designed to be used by only one thread at a time"? How can it be a concurrent map if I can't do concurrent read from multiple threads?


Not with the same Iterator, no.

Winston
 
Marshal
Posts: 79179
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That is hardly surprising. What is happening is this, with thread 1 onthe left and thread 2 on the right.

add element → map
                        map ← add element
add element → map
                        map ← add element
new Iterator
iterate          → map
                        map ← add element ***
iterate          → map
                        map ← remove element

The line marked *** will be a structural alteration whether you are single‑threaded or multithreaded, and will cause an Exception in the next line, so you never reach the second structural alteration.
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Also what does it mean by "iterators are designed to be used by only one thread at a time"? How can it be a concurrent map if I can't do concurrent read from multiple threads?


Not with the same Iterator, no.



Agreed. It isn't common for multiple threads to share one iterator -- if you want to do some sort of producer / consumer setup, it is better to use some sort of collection that has methods that returns elements in an order, like a thread safe queue.

Henry
 
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If I run the following code,


I get the following output.

Testing ConcurrentHashMap
two
one
three
Testing Synchronized LinkedHashMap
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.LinkedHashMap$LinkedHashIterator.nextEntry(Unknown Source)
at java.util.LinkedHashMap$KeyIterator.next(Unknown Source)
at threadandsynchronization.CHMTest.main(CHMTest.java:38)



The iterator returned by ConcurrentHashMap is a screenshot of the map at a particular time. It may reflect some of those changes that happened after you created the iterator but there is no guarantee. I think the state changes that take place after you start iterating are never reflected. But these are implementation details. As such we know that iterating through a ConcurrentHashMap may not give us the most recent updates that happened to the Map ( the ones that happened after we created the iterator ). We would use it if we either don't care about missing some of the updates or if we know that such updates are not likely and we want maximum concurrency in that kind of a setting.

This isn't the case with the iterator returned by a LinkedHashMap or a synchronized view of a LinkedHashMap.


 
Mike Cheung
Ranch Hand
Posts: 115
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:Well, the docs also say: "Retrievals reflect the results of the most recently completed update operations holding upon their onset."

This is sometimes referred to as "weakly consistent" in that it will return the logically "next" key/value/entry based on the current state of the Map at the time the method is actioned. I suspect also (although it's not explicitly stated, and TBH, I'm not sure) that it means it could possibly throw NoSuchElementException if there is no "next" element to be had.


Okay my interpretation of this means the iterator will only provide the view of what is in the map, when the iterator is created, and wouldn't know of anything afterwards? However based on Heena Agarwal's test, it appears the change to ConcurrentHashMap on line 21 was reflected after the iterator was created on line 17, but not for the change on line 23. So there's no guarantee apparently.

Winston Gutkowski wrote:

Also what does it mean by "iterators are designed to be used by only one thread at a time"? How can it be a concurrent map if I can't do concurrent read from multiple threads?


Not with the same Iterator, no.

Winston


Okay I was thinking in the line of having multiple iterators created by the multiple threads, not sharing the same iterator by multiple threads. Thanks for highlighting this possiblity, not that I know how this can be done.


Henry Wong wrote:
Agreed. It isn't common for multiple threads to share one iterator -- if you want to do some sort of producer / consumer setup, it is better to use some sort of collection that has methods that returns elements in an order, like a thread safe queue.

Henry


Um... I'm actually trying to create a table like structure in memory, and when an incoming request asks for the table, the program can return the table as of that moment in time. I guess the best case is to have a read lock (ie whenever someone is in the process of getting the content of the table the table can't be changed). However from my initial investigation of the Java collections, read lock isn't supported. The only thing I can think of is to learn about the common caching framework (ie EhCache, JBoss Cache, etc) to see if this problem can be solved but it appears all caching framework I can find now only supports key-value pair type of structure rather than a table structure. So I have to create a map of a map, which means I have to some how think how I can gurantee each inner map is going to have the same consistent set of columns in the same exact ordering (ie to prevent one row having a different set of columns than another row). :S


Heena Agarwal wrote:The iterator returned by ConcurrentHashMap is a screenshot of the map at a particular time. It may reflect some of those changes that happened after you created the iterator but there is no guarantee. I think the state changes that take place after you start iterating are never reflected. But these are implementation details. As such we know that iterating through a ConcurrentHashMap may not give us the most recent updates that happened to the Map ( the ones that happened after we created the iterator ). We would use it if we either don't care about missing some of the updates or if we know that such updates are not likely and we want maximum concurrency in that kind of a setting.


Heena Agarwal, thanks!!! Your example is great.


Basically what I need is the following:
1) Multiple tables to be held in memory.
2) Each table's structure (ie name and number of columns, number of rows, content of the cells) are to be determined at run time.
3) Ability to insert / remove columns anywhere after table is created.
4) Ability to insert / remove rows anywhere after table is created.
5) Ability to populate / update cells anywhere after table is created.
6) Ability to inject call back methods to be well ... call backed, upon changes to the table.
This I think I can do easily by creating an array of funciton pointers, and iterate them through whenever the methods that are used to update the table are called upon.
7) Ability to allow incoming request for the current view of the table, to get the table without being corrupted by incoming requests to make changes to the table (ie insert / remove columns / rows, populate / update cells).
8) Ability to do simple joins across different tables.

I've also taken a look at in memory databases such as HSQLDB but don't think it has the performance of what I need. Faster implementataions such as Oracle Times Ten (update is about 1.7 micro second), eXtremeDB, HyperXtremeSQL (a million rows per second), and ObjectDB should fit the bill but they are most likely quite expensive (based on what I see Oracle is charging) and has vendor lock in. Since I don't need full SQL support other than basic joins across different tables, in memory dBs that fully support the SQL syntax though are nice but not necessary. Any suggestions or pointers on how this can be done is appreciated. Also interest to hear any experiences of whether writing this through EhCache or map of maps will be as fast as these prorietory in memory dBs. Thanks.

Thanks.
 
Heena Agarwal
Ranch Hand
Posts: 262
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Heena wrote:It may reflect some of those changes that happened after you created the iterator but there is no guarantee. I think the state changes that take place after you start iterating are never reflected. But these are implementation details. As such we know that iterating through a ConcurrentHashMap may not give us the most recent updates that happened to the Map ( the ones that happened after we created the iterator ). We would use it if we either don't care about missing some of the updates or if we know that such updates are not likely and we want maximum concurrency in that kind of a setting.

This isn't the case with the iterator returned by a LinkedHashMap or a synchronized view of a LinkedHashMap.



There are some small but significant incorrect things I have said in my response. Here is a better response.

It may reflect some of those structural changes that happened after you created the iterator but there is no guarantee. I think the state changes that take place after you start iterating are never reflected. But these are implementation details. (This is an just an untested observation. Not even an implementation detail. As such we know that iterating through a ConcurrentHashMap may not give us the most recent structural updates that happened to the Map ( the ones that happened after we created the iterator ). We would use it if we either don't care about missing some of the structural updates or if we know that such updates are not likely and we want maximum concurrency in that kind of a setting.

 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic