LRUMap
org.clapper.util.misc

Class LRUMap<K,V>

  • All Implemented Interfaces:
    Serializable, Cloneable, Map<K,V>


    public class LRUMap<K,V>extends AbstractMap<K,V>implements Cloneable, Serializable

    An LRUMap implements a Map of a fixed maximum size that enforces a least recently used discard policy. When the LRUMap is full (i.e., contains the maximum number of entries), any attempt to insert a new entry causes one of the least recently used entries to be discarded.

    Note:

    • The put() method "touches" (or "refreshes") an object, making it "new" again, even if it simply replaces the value for an existing key.
    • The get() method also refreshes the retrieved object, but the iterator(), containsValue() and containsKey() methods do not refresh the objects in the cache.
    • This implementation is not synchronized. If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. Unlike other Map implementations, even a simple get() operation structurally modifies an LRUMap. Synchronization can be accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap() method. This is best done at creation time, to prevent accidental unsynchronized access to the map:
      Map m = Collections.synchronizedMap (new LRUMap (...));

    There are other, similar implementations. For instance, see the LRUMap class in the Apache Jakarta Commons Collection API. (This leads to the obvious question: Why write another one? The primary answer is that I did not want to add another third-party library dependency. Plus, I wanted to experiment with this algorithm.)

    See Also:
    Serialized Form
    • Field Summary

      Fields 
      Modifier and TypeField and Description
      static intDEFAULT_INITIAL_CAPACITY
      The default initial capacity, if one isn't specified to the constructor
      static floatDEFAULT_LOAD_FACTOR
      The default load factor, if one isn't specified to the constructor
    • Constructor Summary

      Constructors 
      Constructor and Description
      LRUMap(int maxCapacity)
      Construct a new empty map with a default capacity and load factor, and the specified maximum capacity.
      LRUMap(int initialCapacity, float loadFactor, int maxCapacity)
      Constructs a new, empty map with the specified initial capacity, load factor, and maximum capacity.
      LRUMap(int initialCapacity, int maxCapacity)
      Construct a new empty map with the specified initial capacity, a default load factor, and the specified maximum capacity.
      LRUMap(LRUMap<? extends K,? extends V> map)
      Constructs a new map with the same mappings and parameters as the given LRUMap.
    • Field Detail

      • DEFAULT_LOAD_FACTOR

        public static final float DEFAULT_LOAD_FACTOR
        The default load factor, if one isn't specified to the constructor
        See Also:
        Constant Field Values
      • DEFAULT_INITIAL_CAPACITY

        public static final int DEFAULT_INITIAL_CAPACITY
        The default initial capacity, if one isn't specified to the constructor
        See Also:
        Constant Field Values
    • Constructor Detail

      • LRUMap

        public LRUMap(int maxCapacity)
        Construct a new empty map with a default capacity and load factor, and the specified maximum capacity.
        Parameters:
        maxCapacity - the maximum number of entries permitted in the map. Must not be negative.
      • LRUMap

        public LRUMap(int initialCapacity,      int maxCapacity)
        Construct a new empty map with the specified initial capacity, a default load factor, and the specified maximum capacity.
        Parameters:
        initialCapacity - the initial capacity
        maxCapacity - the maximum number of entries permitted in the map. Must not be negative.
      • LRUMap

        public LRUMap(int initialCapacity,      float loadFactor,      int maxCapacity)
        Constructs a new, empty map with the specified initial capacity, load factor, and maximum capacity.
        Parameters:
        initialCapacity - the initial capacity
        loadFactor - the load factor
        maxCapacity - the maximum number of entries permitted in the map. Must not be negative.
      • LRUMap

        public LRUMap(LRUMap<? extends K,? extends V> map)
        Constructs a new map with the same mappings and parameters as the given LRUMap. The initial capacity and load factor is the same as for the parent HashMap class. The insertion order of the keys is preserved.
        Parameters:
        map - the map whose mappings are to be copied
    • Method Detail

      • addRemovalListener

        public void addRemovalListener(ObjectRemovalListener listener,                      boolean automaticOnly)

        Add an EventListener that will be called whenever an object is removed from the cache. If automaticOnly is true, then the listener is only notified for objects that are removed automatically when the cache needs to be cleared to make room for new objects. If automaticOnly is false, then the listener is notified whenever an object is removed for any reason, include a call to the remove() method.

        Note that when this map announces the removal of an object, it passes an ObjectRemovalEvent that contains a java.util.Map.Entry object that wraps the actual object that was removed. That way, both the key and the value are available for the removed object.

        Parameters:
        listener - the listener to add
        automaticOnly - see above
        See Also:
        removeRemovalListener(org.clapper.util.misc.ObjectRemovalListener)
      • clear

        public void clear()
        Remove all mappings from this map.
        Specified by:
        clear in interface Map<K,V>
        Overrides:
        clear in class AbstractMap<K,V>
      • containsKey

        public boolean containsKey(Object key)
        Determine whether this map contains a mapping for a given key. Note that this implementation of containsKey() does not refresh the object in the cache.
        Specified by:
        containsKey in interface Map<K,V>
        Overrides:
        containsKey in class AbstractMap<K,V>
        Parameters:
        key - the key to find
        Returns:
        true if the key is in the map, false if not
      • containsValue

        public boolean containsValue(Object value)
        Determine whether this map contains a given value. Note that this implementation of containsValue() does not refresh the objects in the cache.
        Specified by:
        containsValue in interface Map<K,V>
        Overrides:
        containsValue in class AbstractMap<K,V>
        Parameters:
        value - the value to find
        Returns:
        true if the value is in the map, false if not
      • entrySet

        public Set<Map.Entry<K,V>> entrySet()
        Get a set view of the mappings in this map. Each element in this set is a Map.Entry. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.
        Specified by:
        entrySet in interface Map<K,V>
        Specified by:
        entrySet in class AbstractMap<K,V>
        Returns:
        the entry set
      • get

        public V get(Object key)
        Retrieve an object from the map. Retrieving an object from an LRU map "refreshes" the object so that it is among the most recently used objects.
        Specified by:
        get in interface Map<K,V>
        Overrides:
        get in class AbstractMap<K,V>
        Parameters:
        key - the object's key in the map.
        Returns:
        the associated object, or null if not found
      • getInitialCapacity

        public int getInitialCapacity()
        Get the initial capacity of this LRUMap.
        Returns:
        the initial capacity, as passed to the constructor
        See Also:
        getLoadFactor(), getMaximumCapacity()
      • isEmpty

        public boolean isEmpty()
        Determine whether this map is empty or not.
        Specified by:
        isEmpty in interface Map<K,V>
        Overrides:
        isEmpty in class AbstractMap<K,V>
        Returns:
        true if the map has no mappings, false otherwise
      • keySet

        public Set<K> keySet()

        Return a Set view of the keys in the map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set does supports element removal, which removes the corresponding mapping from this map; however, the Iterator returned by the set currently does not support element removal. The set does not support the add or addAll operations.

        Specified by:
        keySet in interface Map<K,V>
        Overrides:
        keySet in class AbstractMap<K,V>
        Returns:
        the set of keys in this map
      • put

        public V put(K key,    V value)
        Associates the specified value with the specified key in this map. If the key already has a value in this map, the existing value is replaced by the new value, and the old value is replaced. If the key already exists in the map, it is moved to the end of the key insertion order list.
        Specified by:
        put in interface Map<K,V>
        Overrides:
        put in class AbstractMap<K,V>
        Parameters:
        key - the key with which the specified value is to be associated
        value - the value to associate with the specified key
        Returns:
        the previous value associated with the key, or null if (a) there was no previous value, or (b) the previous value was a null
      • putAll

        public void putAll(Map<? extends K,? extends V> map)
        Copies all of the mappings from a specified map to this one. These mappings replace any mappings that this map had for any of the keys.
        Specified by:
        putAll in interface Map<K,V>
        Overrides:
        putAll in class AbstractMap<K,V>
        Parameters:
        map - the map whose mappings are to be copied
      • remove

        public V remove(Object key)
        Removes the mapping for a key, if there is one.
        Specified by:
        remove in interface Map<K,V>
        Overrides:
        remove in class AbstractMap<K,V>
        Parameters:
        key - the key to remove
        Returns:
        the previous value associated with the key, or null if (a) there was no previous value, or (b) the previous value was a null
      • setMaximumCapacity

        public int setMaximumCapacity(int newCapacity)
        Set or change the maximum capacity of this LRUMap. If the maximum capacity is reduced to less than the map's current size, then the map is reduced in size by discarding the oldest entries.
        Parameters:
        newCapacity - the new maximum capacity
        Returns:
        the old maximum capacity
        See Also:
        getMaximumCapacity()
      • size

        public int size()
        Get the number of entries in the map. Note that this value can temporarily exceed the maximum capacity of the map. See the class documentation for details.
        Specified by:
        size in interface Map<K,V>
        Overrides:
        size in class AbstractMap<K,V>
        Returns:
        the number of entries in the map
      • values

        public Collection<V> values()

        Returns a collection view of the values contained in this map. The returned collection is a "thin" view of the values contained in this map. The collection contains proxies for the actual disk-resident values; the values themselves are not loaded until a Collection method such as contains() is called.

        The collection is backed by the map, so changes to the map are reflected in the set. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined.

        The set does not support any of the add() methods.

        Warning:: The toArray() methods can be dangerous, since they will attempt to load every value from the data file into an in-memory array.

        Specified by:
        values in interface Map<K,V>
        Overrides:
        values in class AbstractMap<K,V>
        Returns:
        a collection view of the values contained in this map.
        See Also:
        keySet(), values()

SCaVis 1.8 © jWork.org