A linked list + hashtable of pointers to the linked list nodes is the usual way to implement LRU caches. This gives O(1) operations (assuming a decent hash). Advantage of this (being O(1)): you can do a multithreaded version by just locking the whole structure. You don’t have to worry about granular locking etc. Briefly, … Read more
You can use a LinkedHashMap (Java 1.4+) : // Create cache final int MAX_ENTRIES = 100; Map cache = new LinkedHashMap(MAX_ENTRIES+1, .75F, true) { // This method is called just after a new entry has been added public boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } }; // Add to cache Object key = … Read more
I like lots of these suggestions, but for now I think I’ll stick with LinkedHashMap + Collections.synchronizedMap. If I do revisit this in the future, I’ll probably work on extending ConcurrentHashMap in the same way LinkedHashMap extends HashMap. UPDATE: By request, here’s the gist of my current implementation. private class LruCache<A, B> extends LinkedHashMap<A, B> … Read more