Class Cache.ConcurrentLinkedHashMap<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
gw.util.concurrent.Cache.ConcurrentLinkedHashMap<K,V>
All Implemented Interfaces:
Serializable, ConcurrentMap<K,V>, Map<K,V>
Enclosing class:
Cache<K,V>

static class Cache.ConcurrentLinkedHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable
A ConcurrentMap with a doubly-linked list running through its entries.

This class provides the same semantics as a ConcurrentHashMap in terms of iterators, acceptable keys, and concurrency characteristics, but perform slightly worse due to the added expense of maintaining the linked list. It differs from LinkedHashMap in that it does not provide predictable iteration order.

This map is intended to be used for caches and provides the following eviction policies:

  • First-in, First-out: Also known as insertion order. This policy has excellent concurrency characteristics and an adequate hit rate.
  • Second-chance: An enhanced FIFO policy that marks entries that have been retrieved and saves them from being evicted until the next pass. This enhances the FIFO policy by making it aware of "hot" entries, which increases its hit rate to be equal to an LRU's under normal workloads. In the worst case, where all entries have been saved, this policy degrades to a FIFO.
  • Least Recently Used: An eviction policy based on the observation that entries that have been used recently will likely be used again soon. This policy provides a good approximation of an optimal algorithm, but suffers by being expensive to maintain. The cost of reordering entries on the list during every access operation reduces the concurrency and performance characteristics of this policy.

The Second Chance eviction policy is recommended for common use cases as it provides the best mix of performance and efficiency of the supported replacement policies.

If the Least Recently Used policy is chosen then the sizing should compensate for the proliferation of dead nodes on the linked list. While the values are removed immediately, the nodes are evicted only when they reach the head of the list. Under FIFO-based policies, dead nodes occur when explicit removals are requested and does not normally produce a noticeable impact on the map's hit rate. The LRU policy creates a dead node on every successful retrieval and a new node is placed at the tail of the list. For this reason, the LRU's efficiency cannot be compared directly to a LinkedHashMap evicting in access order. Ben Manes