Does java have a "LinkedConcurrentHashMap" data structure?

There is one implementation available under Google code. A quote from their site:

A high performance version of java.util.LinkedHashMap for use as a software cache.

Design

• A concurrent linked list runs through a ConcurrentHashMap to provide eviction ordering.
• Supports insertion and access ordered eviction policies (FIFO, LRU, and Second Chance).

How about this.

Take your favourite open-source concurrent HashMap implementation. Sadly it can't be Java's ConcurrentHashMap as it's basically impossible to copy and modify that due to huge numbers of package-private stuff. (Why do the Java authors always do that?)

Add a ConcurrentLinkedDeque field.

Modify all of the put methods so that if an insertion is successful the Entry is added to the end of the deque. Modify all of the remove methods so that any removed entries are also removed from the deque. Where a put method replaces the existing value, we don't have to do anything to the deque.

Change all iterator/spliterator methods so that they delegate to the deque.

There's no guarantee that the deque and the map have exactly the same contents at all times, but concurrent hash maps don't make those sort of promises anyway.

Removal won't be super fast (have to scan the deque). But most maps are never (or very rarely) asked to remove entries anyway.

You could also achieve this by extending ConcurrentHashMap, or decorating it (decorator pattern).