Package org.apache.lucene.facet.taxonomy

Class LRUHashMap<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.util.Map<K,​V>
    public class LRUHashMap<K,​V>
extends java.util.LinkedHashMap<K,​V>
    LRUHashMap is an extension of Java's HashMap, which has a bounded size(); When it reaches that size, each time a new element is added, the least recently used (LRU) entry is removed.

    Java makes it very easy to implement LRUHashMap - all its functionality is already available from LinkedHashMap, and we just need to configure that properly.

    Note that like HashMap, LRUHashMap is unsynchronized, and the user MUST synchronize the access to it if used from several threads. Moreover, while with HashMap this is only a concern if one of the threads is modifies the map, with LURHashMap every read is a modification (because the LRU order needs to be remembered) so proper synchronization is always necessary.

    With the usual synchronization mechanisms available to the user, this unfortunately means that LRUHashMap will probably perform sub-optimally under heavy contention: while one thread uses the hash table (reads or writes), any other thread will be blocked from using it - or even just starting to use it (e.g., calculating the hash function). A more efficient approach would be not to use LinkedHashMap at all, but rather to use a non-locking (as much as possible) thread-safe solution, something along the lines of java.util.concurrent.ConcurrentHashMap (though that particular class does not support the additional LRU semantics, which will need to be added separately using a concurrent linked list or additional storage of timestamps (in an array or inside the entry objects), or whatever).

    See Also:
    Serialized Form

    • Nested Class Summary

      • Nested classes/interfaces inherited from class java.util.AbstractMap

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>

    • Constructor Summary

      Constructors 
      Constructor Description
      LRUHashMap​(int maxSize)
      Create a new hash map with a bounded size and with least recently used entries removed.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      LRUHashMap<K,​V> clone()  
      int getMaxSize()
      Return the max size
      void setMaxSize​(int maxSize)
      setMaxSize() allows changing the map's maximal number of elements which was defined at construction time.

      • Methods inherited from class java.util.LinkedHashMap

        clear, containsValue, entrySet, forEach, get, getOrDefault, keySet, replaceAll, values

      • Methods inherited from class java.util.HashMap

        compute, computeIfAbsent, computeIfPresent, containsKey, isEmpty, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, size

      • Methods inherited from class java.util.AbstractMap

        equals, hashCode, toString

      • Methods inherited from class java.lang.Object

        getClass, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.util.Map

        compute, computeIfAbsent, computeIfPresent, containsKey, equals, hashCode, isEmpty, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, size

    • Constructor Detail

      • LRUHashMap

        public LRUHashMap​(int maxSize)
        Create a new hash map with a bounded size and with least recently used entries removed.
        Parameters:
        maxSize - the maximum size (in number of entries) to which the map can grow before the least recently used entries start being removed.
        Setting maxSize to a very large value, like Integer.MAX_VALUE is allowed, but is less efficient than using HashMap because our class needs to keep track of the use order (via an additional doubly-linked list) which is not used when the map's size is always below the maximum size.

    • Method Detail

      • getMaxSize

        public int getMaxSize()
        Return the max size

      • setMaxSize

        public void setMaxSize​(int maxSize)
        setMaxSize() allows changing the map's maximal number of elements which was defined at construction time.

        Note that if the map is already larger than maxSize, the current implementation does not shrink it (by removing the oldest elements); Rather, the map remains in its current size as new elements are added, and will only start shrinking (until settling again on the give maxSize) if existing elements are explicitly deleted.

      • clone

        public LRUHashMap<K,​V> clone()
        Overrides:
        clone in class java.util.HashMap<K,​V>