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 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 java.. This class may throw
NullPointerException's when accessed by concurrent threads.
| Modifier and Type | Field and Description |
|---|---|
| protected static final int | DEFAULT_MAX_SIZE
Default maximum size |
| private transient int | maxSize
Maximum size |
| private boolean | scanUntilRemovable
Scan behaviour |
| private static final long | serialVersionUID
Serialisation version |
| Access | Constructor and Description |
|---|---|
| public | |
| public | LRUMap(final int
the maximum size of the map maxSize)Constructs a new, empty map with the specified maximum size. |
| public | LRUMap(final int
the maximum size of the map maxSize, final int the initial size of the map initialSize)Constructs a new, empty map with the specified maximum size. |
| public | LRUMap(final int
the maximum size of the map maxSize, final boolean scan until a removeable entry is found, default false scanUntilRemovable)Constructs a new, empty map with the specified maximum size. |
| public | LRUMap(final int
the maximum size of the map maxSize, final float the load factor loadFactor)Constructs a new, empty map with the specified max capacity and load factor. |
| public | LRUMap(final int
the maximum size of the map maxSize, final int the initial size of the map initialSize, final float the load factor loadFactor)Constructs a new, empty map with the specified max / initial capacity and load factor. |
| public | LRUMap(final int
the maximum size of the map maxSize, final float the load factor loadFactor, final boolean scan until a removeable entry is found, default false scanUntilRemovable)Constructs a new, empty map with the specified max capacity and load factor. |
| public | LRUMap(final int
the maximum size of the map maxSize, final int the initial size of the map initialSize, final float the load factor loadFactor, final boolean scan until a removeable entry is found, default false scanUntilRemovable)Constructs a new, empty map with the specified max / initial capacity and load factor. |
| public | |
| public |
| Modifier and Type | Method and Description |
|---|---|
| protected void | addMapping(final int
the index into the data array to store at hashIndex, final int the hash code of the key to add hashCode, final K the key to add key, final V the value to add value)Overrides org. |
| public LRUMap | Returns: a shallow cloneOverrides org. |
| protected void | doReadObject(final ObjectInputStream
the input stream in)Overrides org. put() to work in the superclass.
|
| protected void | doWriteObject(final ObjectOutputStream
the output stream out)Overrides org. put() to work in deserialization.
|
| public V | Returns: the mapped value, null if no matchthe key key)Overrides org. Implements java. |
| public V | |
| public boolean | Returns: true if the map is fullImplements org. |
| public boolean | Returns: true if this map scansWhether this LRUMap will scan until a removable entry is found when the map is full. |
| public int | Returns: the maximum number of elements the map can holdImplements org. |
| protected void | moveToMRU(final AbstractLinkedMap.
the entry to update entryMoves an entry to the MRU position at the end of the list. |
| private void | |
| protected boolean | Returns: truethe entry to be removed entrySubclass method to control removal of the least recently used entry from the map. |
| protected void | reuseMapping(final AbstractLinkedMap.
the entry to reuse entry,the index into the data array to store at hashIndex, final int the hash code of the key to add hashCode, final K the key to add key, final V the value to add value)Reuses an entry by removing it and moving it to a new place in the map. |
| protected void | updateEntry(final AbstractHashedMap.
the entry to update entry,the new value to store newValue)Overrides org. |
| private void |
| DEFAULT_MAX_SIZE | back to summary |
|---|---|
| protected static final int DEFAULT_MAX_SIZE Default maximum size | |
| maxSize | back to summary |
|---|---|
| private transient int maxSize Maximum size | |
| scanUntilRemovable | back to summary |
|---|---|
| private boolean scanUntilRemovable Scan behaviour | |
| serialVersionUID | back to summary |
|---|---|
| private static final long serialVersionUID Serialisation version | |
| LRUMap | back to summary |
|---|---|
| public LRUMap() Constructs a new empty map with a maximum size of 100. | |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final int maxSize) Constructs a new, empty map with the specified maximum size.
| |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final int maxSize, final int initialSize) Constructs a new, empty map with the specified maximum size.
| |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final int maxSize, final boolean scanUntilRemovable) Constructs a new, empty map with the specified maximum size.
| |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final int maxSize, final float loadFactor) Constructs a new, empty map with the specified max capacity and load factor.
| |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final int maxSize, final int initialSize, final float loadFactor) Constructs a new, empty map with the specified max / initial capacity and load factor.
| |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final int maxSize, final float loadFactor, final boolean scanUntilRemovable) Constructs a new, empty map with the specified max capacity and load factor.
| |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final int maxSize, final int initialSize, final float loadFactor, final boolean scanUntilRemovable) Constructs a new, empty map with the specified max / initial capacity and load factor.
| |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final Map<? extends K, ? extends V> map) Constructor copying elements from another map. The maximum size is set from the map's size.
| |
| LRUMap | back to summary |
|---|---|
| public LRUMap(final Map<? extends K, ? extends V> map, final boolean scanUntilRemovable) Constructor copying elements from another map. The maximum size is set from the map's size.
| |
| addMapping | back to summary |
|---|---|
| protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) Overrides org. 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
From Commons Collections 3.1 this method uses
| |
| clone | back to summary |
|---|---|
| public LRUMap Overrides org. Clones the map without cloning the keys or values. | |
| doReadObject | back to summary |
|---|---|
| protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException Overrides org. Reads the data necessary for
| |
| doWriteObject | back to summary |
|---|---|
| protected void doWriteObject(final ObjectOutputStream out) throws IOException Overrides org. Writes the data necessary for
| |
| get | back to summary |
|---|---|
| public V get(final Object key) Overrides org. Implements java. 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). | |
| get | back to summary |
|---|---|
| public V get(final Object key, final boolean updateToMRU) Gets the value mapped to the key specified.
If
| |
| isFull | back to summary |
|---|---|
| public boolean isFull() Implements org. Returns true if this map is full and no new mappings can be added.
| |
| isScanUntilRemovable | back to summary |
|---|---|
| public boolean isScanUntilRemovable() Whether this LRUMap will scan until a removable entry is found when the map is full.
| |
| maxSize | back to summary |
|---|---|
| public int maxSize() Implements org. Gets the maximum size of the map (the bound).
| |
| moveToMRU | back to summary |
|---|---|
| protected void moveToMRU(final AbstractLinkedMap. 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.
| |
| readObject | back to summary |
|---|---|
| private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException Read the map in using a custom routine.
| |
| removeLRU | back to summary |
|---|---|
| protected boolean removeLRU(final AbstractLinkedMap. 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.
| |
| reuseMapping | back to summary |
|---|---|
| protected void reuseMapping(final AbstractLinkedMap. Reuses an entry by removing it and moving it to a new place in the map.
This method uses
| |
| updateEntry | back to summary |
|---|---|
| protected void updateEntry(final AbstractHashedMap. Overrides org. Updates an existing key-value mapping.
This implementation moves the updated entry to the end of the list
using
| |
| writeObject | back to summary |
|---|---|
| private void writeObject(final ObjectOutputStream out) throws IOException Write the map out using a custom routine.
| |