public class

LRUMap

extends AbstractLinkedMap
implements Serializable Cloneable BoundedMap
java.lang.Object
   ↳ java.util.AbstractMap<K, V>
     ↳ org.apache.commons.collections.map.AbstractHashedMap
       ↳ org.apache.commons.collections.map.AbstractLinkedMap
         ↳ org.apache.commons.collections.map.LRUMap

Class Overview

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 synchronizedMap(Map). This class may throw NullPointerException's when accessed by concurrent threads.

Summary

Constants
int DEFAULT_MAX_SIZE Default maximum size
[Expand]
Inherited Constants
From class org.apache.commons.collections.map.AbstractHashedMap
[Expand]
Inherited Fields
From class org.apache.commons.collections.map.AbstractLinkedMap
From class org.apache.commons.collections.map.AbstractHashedMap
Public Constructors
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 initial capacity and load factor.
LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable)
Constructs a new, empty map with the specified initial capacity and load factor.
LRUMap(Map map)
Constructor copying elements from another map.
LRUMap(Map map, boolean scanUntilRemovable)
Constructor copying elements from another map.
Public Methods
Object clone()
Clones the map without cloning the keys or values.
Object get(Object key)
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 Methods
void addMapping(int hashIndex, int hashCode, Object key, Object value)
Adds a new key-value mapping into this map.
void doReadObject(ObjectInputStream in)
Reads the data necessary for put() to work in the superclass.
void doWriteObject(ObjectOutputStream out)
Writes the data necessary for put() to work in deserialization.
void moveToMRU(AbstractLinkedMap.LinkEntry entry)
Moves an entry to the MRU position at the end of the list.
boolean removeLRU(AbstractLinkedMap.LinkEntry entry)
Subclass method to control removal of the least recently used entry from the map.
void reuseMapping(AbstractLinkedMap.LinkEntry entry, int hashIndex, int hashCode, Object key, Object value)
Reuses an entry by removing it and moving it to a new place in the map.
void updateEntry(AbstractHashedMap.HashEntry entry, Object newValue)
Updates an existing key-value mapping.
[Expand]
Inherited Methods
From class org.apache.commons.collections.map.AbstractLinkedMap
From class org.apache.commons.collections.map.AbstractHashedMap
From class java.util.AbstractMap
From class java.lang.Object
From interface java.util.Map
From interface org.apache.commons.collections.BoundedMap
From interface org.apache.commons.collections.IterableMap
From interface org.apache.commons.collections.OrderedMap

Constants

protected static final int DEFAULT_MAX_SIZE

Default maximum size

Constant Value: 100 (0x00000064)

Public Constructors

public LRUMap ()

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

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

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

public LRUMap (int maxSize, float loadFactor)

Constructs a new, empty map with the specified initial capacity and load factor.

Parameters
maxSize the maximum size of the map, -1 for no limit,
loadFactor the load factor
Throws
IllegalArgumentException if the maximum size is less than one
IllegalArgumentException if the load factor is less than zero

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

Constructs a new, empty map with the specified initial capacity and load factor.

Parameters
maxSize the maximum size of the map, -1 for no limit,
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

public LRUMap (Map 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

public LRUMap (Map 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

Public Methods

public Object clone ()

Clones the map without cloning the keys or values.

Returns
  • a shallow clone

public Object 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 (first).

Parameters
key the key
Returns
  • the mapped value, null if no match

public boolean isFull ()

Returns true if this map is full and no new mappings can be added.

Returns
  • true if the map is full

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

public int maxSize ()

Gets the maximum size of the map (the bound).

Returns
  • the maximum number of elements the map can hold

Protected Methods

protected void addMapping (int hashIndex, int hashCode, Object key, Object 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.

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

protected void doReadObject (ObjectInputStream in)

Reads the data necessary for put() to work in the superclass.

Parameters
in the input stream
Throws
IOException
ClassNotFoundException

protected void doWriteObject (ObjectOutputStream out)

Writes the data necessary for put() to work in deserialization.

Parameters
out the output stream
Throws
IOException

protected void moveToMRU (AbstractLinkedMap.LinkEntry 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

protected boolean removeLRU (AbstractLinkedMap.LinkEntry 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

protected void reuseMapping (AbstractLinkedMap.LinkEntry entry, int hashIndex, int hashCode, Object key, Object value)

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

This method uses removeEntry(AbstractHashedMap.HashEntry, int, AbstractHashedMap.HashEntry), reuseEntry(AbstractHashedMap.HashEntry, int, int, Object, Object) and addEntry(AbstractHashedMap.HashEntry, 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

protected void updateEntry (AbstractHashedMap.HashEntry entry, Object newValue)

Updates an existing key-value mapping.

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

Parameters
entry the entry to update
newValue the new value to store