CODEWITHSUNDEEP
java
Phate
Phate

Reputation: 6602

Limited size hash map

I'd like to make an hash map to use like a cache. Cache has an initial size, if you try inserting an item when cache is full last recently used item should be replaced...any ideas?

Upvotes: 10

Views: 8764

Answers (6)

Maciej Trybiło
Maciej Trybiło

Reputation: 1207

You could keep a bound queue together with your hash map. In that way you would easily know which item is the oldest.

Upvotes: 1

auselen
auselen

Reputation: 28087

Look at LRUMap from Apache Commons.

A Map implementation with a fixed maximum size which removes the least recently used entry if an entry is added when full.

The least recently used algorithm works on the get and put operations only. Iteration of any kind, including setting the value by iteration, does not change the order. Queries such as containsKey and containsValue or access via views also do not change the order.

The map implements OrderedMap and entries may be queried using the bidirectional OrderedMapIterator. The order returned is least recently used to most recently used. Iterators from map views can also be cast to OrderedIterator if required.

All the available iterators can be reset back to the start by casting to ResettableIterator and calling reset().

Note that LRUMap is not synchronized and is not thread-safe. If you wish to use this map from multiple threads concurrently, you must use appropriate synchronization. The simplest approach is to wrap this map using Collections.synchronizedMap(Map). This class may throw NullPointerException's when accessed by concurrent threads.

Upvotes: 1

Tobias Ritzau
Tobias Ritzau

Reputation: 3327

On Android you can use http://developer.android.com/reference/android/util/LruCache.html. I quite sure that you can take that implementation from the AOSP and use it under the Apache License.

Upvotes: 2

jarnbjo
jarnbjo

Reputation: 34313

The most trivial approach would be to extend LinkedHashMap, override the removeEldestEntry(Map.Entry<K,V> eldest) method and decide in its implementation if your cache is "full" or not.

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533432

You can use a LinkedHashMap by implementing removeEldest 

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K,V>(maxSize*4/3, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return size() > maxSize;
        }
    };
}

For more details

http://vanillajava.blogspot.co.uk/2011/06/java-secret-lru-cache-in-java.html

http://blog.meschberger.ch/2008/10/linkedhashmaps-hidden-features.html

Upvotes: 19

Brian Agnew
Brian Agnew

Reputation: 272207

Have you looked at Guava ? It has factory-based methods for creating collections with caches etc.

e.g. (from the linked article)

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
   .maximumSize(1000)
   .expireAfterWrite(10, TimeUnit.MINUTES)
   .removalListener(MY_LISTENER)
   .build(
       new CacheLoader<Key, Graph>() {
         public Graph load(Key key) throws AnyException {
           return createExpensiveGraph(key);
         }
       });

Upvotes: 8

Related Questions