org.apache.commons.collections4.map

## Class LRUMap<K,V>

- java.lang.Object
- - java.util.AbstractMap<K,V>
  - - org.apache.commons.collections4.map.AbstractHashedMap<K,V>
    - - org.apache.commons.collections4.map.AbstractLinkedMap<K,V>
      - - org.apache.commons.collections4.map.LRUMap<K,V>

- All Implemented Interfaces:
    Serializable, Cloneable, Map<K,V>, BoundedMap<K,V>, Get<K,V>, IterableGet<K,V>, IterableMap<K,V>, OrderedMap<K,V>, Put<K,V>

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

  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.

  A somewhat subtle ramification of the least recently used algorithm is that calls to `get(Object)` stand a very good chance of modifying the map's iteration order and thus invalidating any iterators currently in use. It is therefore suggested that iterations over an `LRUMap` instance access entry values only through a `MapIterator` or `AbstractHashedMap.entrySet()` iterator.

  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.

  Since:
    3.0 (previously in main package v1.0)
  Version:
    $Id: LRUMap.java 1683016 2015-06-01 22:40:56Z tn $
  See Also:
    Serialized Form

- - ### Nested Class Summary

    - ### Nested classes/interfaces inherited from class org.apache.commons.collections4.map.AbstractLinkedMap

      `AbstractLinkedMap.EntrySetIterator<K,V>, AbstractLinkedMap.KeySetIterator<K>, AbstractLinkedMap.LinkEntry<K,V>, AbstractLinkedMap.LinkIterator<K,V>, AbstractLinkedMap.LinkMapIterator<K,V>, AbstractLinkedMap.ValuesIterator<V>`

    - ### Nested classes/interfaces inherited from class org.apache.commons.collections4.map.AbstractHashedMap

      `AbstractHashedMap.EntrySet<K,V>, AbstractHashedMap.HashEntry<K,V>, AbstractHashedMap.HashIterator<K,V>, AbstractHashedMap.HashMapIterator<K,V>, AbstractHashedMap.KeySet<K>, AbstractHashedMap.Values<V>`

    - ### Nested classes/interfaces inherited from class java.util.AbstractMap

      `AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>`

    - ### Nested classes/interfaces inherited from interface java.util.Map

      `Map.Entry<K,V>`

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected static int` | `DEFAULT_MAX_SIZE` Default maximum size

    - ### Fields inherited from class org.apache.commons.collections4.map.AbstractHashedMap

      `DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD, GETKEY_INVALID, GETVALUE_INVALID, MAXIMUM_CAPACITY, NO_NEXT_ENTRY, NO_PREVIOUS_ENTRY, NULL, REMOVE_INVALID, SETVALUE_INVALID`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `LRUMap()` Constructs a new empty map with a maximum size of 100.
    `LRUMap(int maxSize)` Constructs a new, empty map with the specified maximum size.
    `LRUMap(int maxSize, boolean scanUntilRemovable)` Constructs a new, empty map with the specified maximum size.
    `LRUMap(int maxSize, float loadFactor)` Constructs a new, empty map with the specified max capacity and load factor.
    `LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable)` Constructs a new, empty map with the specified max capacity and load factor.
    `LRUMap(int maxSize, int initialSize)` Constructs a new, empty map with the specified maximum size.
    `LRUMap(int maxSize, int initialSize, float loadFactor)` Constructs a new, empty map with the specified max / initial capacity and load factor.
    `LRUMap(int maxSize, int initialSize, float loadFactor, boolean scanUntilRemovable)` Constructs a new, empty map with the specified max / initial capacity and load factor.
    `LRUMap(Map<? extends K,? extends V> map)` Constructor copying elements from another map.
    `LRUMap(Map<? extends K,? extends V> map, boolean scanUntilRemovable)` Constructor copying elements from another map.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected void` | `addMapping(int hashIndex, int hashCode, K key, V value)` Adds a new key-value mapping into this map.
    `LRUMap<K,V>` | `clone()` Clones the map without cloning the keys or values.
    `protected void` | `doReadObject(ObjectInputStream in)` Reads the data necessary for `put()` to work in the superclass.
    `protected void` | `doWriteObject(ObjectOutputStream out)` Writes the data necessary for `put()` to work in deserialization.
    `V` | `get(Object key)` Gets the value mapped to the key specified.
    `V` | `get(Object key, boolean updateToMRU)` Gets the value mapped to the key specified.
    `boolean` | `isFull()` Returns true if this map is full and no new mappings can be added.
    `boolean` | `isScanUntilRemovable()` Whether this LRUMap will scan until a removable entry is found when the map is full.
    `int` | `maxSize()` Gets the maximum size of the map (the bound).
    `protected void` | `moveToMRU(AbstractLinkedMap.LinkEntry<K,V> entry)` Moves an entry to the MRU position at the end of the list.
    `protected boolean` | `removeLRU(AbstractLinkedMap.LinkEntry<K,V> entry)` Subclass method to control removal of the least recently used entry from the map.
    `protected void` | `reuseMapping(AbstractLinkedMap.LinkEntry<K,V> entry, int hashIndex, int hashCode, K key, V value)` Reuses an entry by removing it and moving it to a new place in the map.
    `protected void` | `updateEntry(AbstractHashedMap.HashEntry<K,V> entry, V newValue)` Updates an existing key-value mapping.

    - ### Methods inherited from class org.apache.commons.collections4.map.AbstractLinkedMap

      `addEntry, clear, containsValue, createEntry, createEntrySetIterator, createKeySetIterator, createValuesIterator, entryAfter, entryBefore, firstKey, getEntry, getEntry, init, lastKey, mapIterator, nextKey, previousKey, removeEntry`

    - ### Methods inherited from class org.apache.commons.collections4.map.AbstractHashedMap

      `calculateNewCapacity, calculateThreshold, checkCapacity, containsKey, containsValue, convertKey, destroyEntry, ensureCapacity, entryHashCode, entryKey, entryNext, entrySet, entryValue, equals, hash, hashCode, hashIndex, isEmpty, isEqualKey, isEqualValue, keySet, put, putAll, remove, removeMapping, reuseEntry, size, toString, values`

    - ### Methods inherited from class java.lang.Object

      `finalize, getClass, notify, notifyAll, wait, wait, wait`

    - ### Methods inherited from interface java.util.Map

      `clear, containsKey, containsValue, entrySet, equals, hashCode, isEmpty, keySet, put, putAll, remove, size, values`

    - ### Methods inherited from interface org.apache.commons.collections4.Put

      `clear, put, putAll`

    - ### Methods inherited from interface org.apache.commons.collections4.IterableGet

      `mapIterator`

    - ### Methods inherited from interface org.apache.commons.collections4.Get

      `containsKey, containsValue, entrySet, isEmpty, keySet, remove, size, values`

- - ### Field Detail

    - #### DEFAULT_MAX_SIZE

          protected static final int DEFAULT_MAX_SIZE

      Default maximum size
      See Also:
        Constant Field Values

  - ### Constructor Detail

    - #### LRUMap

          public LRUMap()

      Constructs a new empty map with a maximum size of 100.

    - #### LRUMap

          public LRUMap(int maxSize)

      Constructs a new, empty map with the specified maximum size.
      Parameters:
        `maxSize` - the maximum size of the map
      Throws:
        `IllegalArgumentException` - if the maximum size is less than one

    - #### LRUMap

          public LRUMap(int maxSize,
                int initialSize)

      Constructs a new, empty map with the specified maximum size.
      Parameters:
        `maxSize` - the maximum size of the map
        `initialSize` - the initial size of the map
      Throws:
        `IllegalArgumentException` - if the maximum size is less than one
        `IllegalArgumentException` - if the initial size is negative or larger than the maximum size
      Since:
        4.1

    - #### LRUMap

          public LRUMap(int maxSize,
                boolean scanUntilRemovable)

      Constructs a new, empty map with the specified maximum size.
      Parameters:
        `maxSize` - the maximum size of the map
        `scanUntilRemovable` - scan until a removeable entry is found, default false
      Throws:
        `IllegalArgumentException` - if the maximum size is less than one
      Since:
        3.1

    - #### LRUMap

          public LRUMap(int maxSize,
                float loadFactor)

      Constructs a new, empty map with the specified max capacity and load factor.
      Parameters:
        `maxSize` - the maximum size of the map
        `loadFactor` - the load factor
      Throws:
        `IllegalArgumentException` - if the maximum size is less than one
        `IllegalArgumentException` - if the load factor is less than zero

    - #### LRUMap

          public LRUMap(int maxSize,
                int initialSize,
                float loadFactor)

      Constructs a new, empty map with the specified max / initial capacity and load factor.
      Parameters:
        `maxSize` - the maximum size of the map
        `initialSize` - the initial size of the map
        `loadFactor` - the load factor
      Throws:
        `IllegalArgumentException` - if the maximum size is less than one
        `IllegalArgumentException` - if the initial size is negative or larger than the maximum size
        `IllegalArgumentException` - if the load factor is less than zero
      Since:
        4.1

    - #### LRUMap

          public LRUMap(int maxSize,
                float loadFactor,
                boolean scanUntilRemovable)

      Constructs a new, empty map with the specified max capacity and load factor.
      Parameters:
        `maxSize` - the maximum size of the map
        `loadFactor` - the load factor
        `scanUntilRemovable` - scan until a removeable entry is found, default false
      Throws:
        `IllegalArgumentException` - if the maximum size is less than one
        `IllegalArgumentException` - if the load factor is less than zero
      Since:
        3.1

    - #### LRUMap

          public LRUMap(int maxSize,
                int initialSize,
                float loadFactor,
                boolean scanUntilRemovable)

      Constructs a new, empty map with the specified max / initial capacity and load factor.
      Parameters:
        `maxSize` - the maximum size of the map
        `initialSize` - the initial size of the map
        `loadFactor` - the load factor
        `scanUntilRemovable` - scan until a removeable entry is found, default false
      Throws:
        `IllegalArgumentException` - if the maximum size is less than one
        `IllegalArgumentException` - if the initial size is negative or larger than the maximum size
        `IllegalArgumentException` - if the load factor is less than zero
      Since:
        4.1

    - #### LRUMap

          public LRUMap(Map<? extends K,? extends V> map)

      Constructor copying elements from another map.

      The maximum size is set from the map's size.

      Parameters:
        `map` - the map to copy
      Throws:
        `NullPointerException` - if the map is null
        `IllegalArgumentException` - if the map is empty

    - #### LRUMap

          public LRUMap(Map<? extends K,? extends V> map,
                boolean scanUntilRemovable)

      Constructor copying elements from another map.

      The maximum size is set from the map's size.
      Parameters:
        `map` - the map to copy
        `scanUntilRemovable` - scan until a removeable entry is found, default false
      Throws:
        `NullPointerException` - if the map is null
        `IllegalArgumentException` - if the map is empty
      Since:
        3.1

  - ### Method Detail

    - #### get

          public V get(Object key)

      Gets the value mapped to the key specified.

      This operation changes the position of the key in the map to the most recently used position (last).

      Specified by:
        `get` in interface `Map<K,V>`
      Specified by:
        `get` in interface `Get<K,V>`
      Overrides:
        `get` in class `AbstractHashedMap<K,V>`
      Parameters:
        `key` - the key
      Returns:
        the mapped value, null if no match
      See Also:
        `Map.get(Object)`

    - #### get

          public V get(Object key,
              boolean updateToMRU)

      Gets the value mapped to the key specified.

      If `updateToMRU` is `true`, the position of the key in the map is changed to the most recently used position (last), otherwise the iteration order is not changed by this operation.

      Parameters:
        `key` - the key
        `updateToMRU` - whether the key shall be updated to the most recently used position
      Returns:
        the mapped value, null if no match
      Since:
        4.1

    - #### moveToMRU

          protected void moveToMRU(AbstractLinkedMap.LinkEntry<K,V> entry)

      Moves an entry to the MRU position at the end of the list.

      This implementation moves the updated entry to the end of the list.

      Parameters:
        `entry` - the entry to update

    - #### updateEntry

          protected void updateEntry(AbstractHashedMap.HashEntry<K,V> entry,
                         V newValue)

      Updates an existing key-value mapping.

      This implementation moves the updated entry to the end of the list using `moveToMRU(AbstractLinkedMap.LinkEntry)`.

      Overrides:
        `updateEntry` in class `AbstractHashedMap<K,V>`
      Parameters:
        `entry` - the entry to update
        `newValue` - the new value to store

    - #### addMapping

          protected void addMapping(int hashIndex,
                        int hashCode,
                        K key,
                        V value)

      Adds a new key-value mapping into this map.

      This implementation checks the LRU size and determines whether to discard an entry or not using `removeLRU(AbstractLinkedMap.LinkEntry)`.

      From Commons Collections 3.1 this method uses `isFull()` rather than accessing `size` and `maxSize` directly. It also handles the scanUntilRemovable functionality.

      Overrides:
        `addMapping` in class `AbstractHashedMap<K,V>`
      Parameters:
        `hashIndex` - the index into the data array to store at
        `hashCode` - the hash code of the key to add
        `key` - the key to add
        `value` - the value to add

    - #### reuseMapping

          protected void reuseMapping(AbstractLinkedMap.LinkEntry<K,V> entry,
                          int hashIndex,
                          int hashCode,
                          K key,
                          V value)

      Reuses an entry by removing it and moving it to a new place in the map.

      This method uses `AbstractLinkedMap.removeEntry(org.apache.commons.collections4.map.AbstractHashedMap.HashEntry<K, V>, int, org.apache.commons.collections4.map.AbstractHashedMap.HashEntry<K, V>)`, `AbstractHashedMap.reuseEntry(org.apache.commons.collections4.map.AbstractHashedMap.HashEntry<K, V>, int, int, K, V)` and `AbstractLinkedMap.addEntry(org.apache.commons.collections4.map.AbstractHashedMap.HashEntry<K, V>, int)`.

      Parameters:
        `entry` - the entry to reuse
        `hashIndex` - the index into the data array to store at
        `hashCode` - the hash code of the key to add
        `key` - the key to add
        `value` - the value to add

    - #### removeLRU

          protected boolean removeLRU(AbstractLinkedMap.LinkEntry<K,V> entry)

      Subclass method to control removal of the least recently used entry from the map.

      This method exists for subclasses to override. A subclass may wish to provide cleanup of resources when an entry is removed. For example:

           protected boolean removeLRU(LinkEntry entry) {
             releaseResources(entry.getValue());  // release resources held by entry
             return true;  // actually delete entry
           }

      Alternatively, a subclass may choose to not remove the entry or selectively keep certain LRU entries. For example:

           protected boolean removeLRU(LinkEntry entry) {
             if (entry.getKey().toString().startsWith("System.")) {
               return false;  // entry not removed from LRUMap
             } else {
               return true;  // actually delete entry
             }
           }

      The effect of returning false is dependent on the scanUntilRemovable flag. If the flag is true, the next LRU entry will be passed to this method and so on until one returns false and is removed, or every entry in the map has been passed. If the scanUntilRemovable flag is false, the map will exceed the maximum size.

      NOTE: Commons Collections 3.0 passed the wrong entry to this method. This is fixed in version 3.1 onwards.

      Parameters:
        `entry` - the entry to be removed
      Returns:
        `true`

    - #### isFull

          public boolean isFull()

      Returns true if this map is full and no new mappings can be added.
      Specified by:
        `isFull` in interface `BoundedMap<K,V>`
      Returns:
        `true` if the map is full

    - #### maxSize

          public int maxSize()

      Gets the maximum size of the map (the bound).
      Specified by:
        `maxSize` in interface `BoundedMap<K,V>`
      Returns:
        the maximum number of elements the map can hold

    - #### isScanUntilRemovable

          public boolean isScanUntilRemovable()

      Whether this LRUMap will scan until a removable entry is found when the map is full.
      Returns:
        true if this map scans
      Since:
        3.1

    - #### clone

          public LRUMap<K,V> clone()

      Clones the map without cloning the keys or values.
      Overrides:
        `clone` in class `AbstractHashedMap<K,V>`
      Returns:
        a shallow clone

    - #### doWriteObject

          protected void doWriteObject(ObjectOutputStream out)
                                throws IOException

      Writes the data necessary for `put()` to work in deserialization.
      Overrides:
        `doWriteObject` in class `AbstractHashedMap<K,V>`
      Parameters:
        `out` - the output stream
      Throws:
        `IOException` - if an error occurs while writing to the stream

    - #### doReadObject

          protected void doReadObject(ObjectInputStream in)
                               throws IOException,
                                      ClassNotFoundException

      Reads the data necessary for `put()` to work in the superclass.
      Overrides:
        `doReadObject` in class `AbstractHashedMap<K,V>`
      Parameters:
        `in` - the input stream
      Throws:
        `IOException` - if an error occurs while reading from the stream
        `ClassNotFoundException` - if an object read from the stream can not be loaded

Copyright © 2001–2015 The Apache Software Foundation. All rights reserved.