Use ConcurrentSkipListMap if size >1.3M

[GoogleCodeExporter]

Current Behavior:
The FAQ describes why a hash table approach is attractive at average use-
case sizes, but performs poorly at extremely large use-cases. In the 
Ehcache forum, a user had performance problems with a cache size of 60M 
entries. This would result in 915 comparisions on the segment's list.

Desired Behavior:
If the data store was a instead skip-list based then at 60M entries it 
would require 26 comparisions. The cross-over is at 1.33M entries when a 
skip-list provides better performance characteristics. 

Complexity / Amount of Change Required:
The adoption of ConcurrentSkipListMap would require that clients have 
adopted Java-6. The current expectation is Java-5.

Alternatively, the data store could be specified either by a constructor 
argument or retrieved from a protected delegate method. While both 
approaches would work, they would leak implementation details. The class 
name shouldn't be "ConcurrentLinkedHashMap" any longer, as hashing may not 
be the strategy.

Another approach is to migrate to a package-private 
"AbstractConcurrentLinkedMap" and provide a "ConcurrentLinkedHashMap" and 
"ConcurrentLinkedSkipListMap" implementations. This hides internal details 
and allows exposure of the NavigatableMap methods. Unfortunately this 
would require conditional compilation to build a Java-5 compatible jar 
that lacked the second data structure.

Original issue reported on code.google.com by Ben.Manes@gmail.com on 26 May 2009 at 9:12

[GoogleCodeExporter]

Original comment by Ben.Manes@gmail.com on 26 May 2009 at 9:12

• Added labels: Priority-Low
• Removed labels: Priority-Medium

[GoogleCodeExporter]

I misunderstood some of the details of how a hashtable was implemented, making 
my 
analysis incorrect.

Original comment by Ben.Manes@gmail.com on 31 May 2009 at 10:26

• Changed state: Invalid