public class LRUMap<K,V> extends AbstractLinkedMap<K ,V> implements BoundedMap <K ,V>, Serializable , Cloneable
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 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. This class may throw NullPointerException's when accessed by concurrent threads.
AbstractLinkedMap.EntrySetIterator <K,V>, AbstractLinkedMap.KeySetIterator <K>, AbstractLinkedMap.LinkEntry <K,V>, AbstractLinkedMap.LinkIterator <K,V>, AbstractLinkedMap.LinkMapIterator <K,V>, AbstractLinkedMap.ValuesIterator <V> AbstractHashedMap.EntrySet <K,V>, AbstractHashedMap.HashEntry <K,V>, AbstractHashedMap.HashIterator <K,V>, AbstractHashedMap.HashMapIterator <K,V>, AbstractHashedMap.KeySet <K>, AbstractHashedMap.Values <V> AbstractMap.SimpleEntry <K,V>, AbstractMap.SimpleImmutableEntry <K,V> | Modifier and Type | Field and Description |
|---|---|
protected static int |
DEFAULT_MAX_SIZE
Default maximum size
|
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 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
Constructor copying elements from another map.
|
LRUMap(Map
Constructor copying elements from another map.
|
| 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 |
clone()
Clones the map without cloning the keys or values.
|
protected void |
doReadObject(ObjectInputStream
Reads the data necessary for
put() to work in the superclass.
|
protected void |
doWriteObject(ObjectOutputStream
Writes the data necessary for
put() to work in deserialization.
|
V |
get(Object
Gets the value mapped to the key specified.
|
V |
get(Object
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
Moves an entry to the MRU position at the end of the list.
|
protected boolean |
removeLRU(AbstractLinkedMap
Subclass method to control removal of the least recently used entry from the map.
|
protected void |
reuseMapping(AbstractLinkedMap
Reuses an entry by removing it and moving it to a new place in the map.
|
protected void |
updateEntry(AbstractHashedMap
Updates an existing key-value mapping.
|
addEntry, clear, containsValue, createEntry, createEntrySetIterator, createKeySetIterator, createValuesIterator, entryAfter, entryBefore, firstKey, getEntry, getEntry, init, lastKey, mapIterator, nextKey, previousKey, removeEntrycalculateNewCapacity, calculateThreshold, checkCapacity, containsKey, convertKey, destroyEntry, ensureCapacity, entryHashCode, entryKey, entryNext, entrySet, entryValue, equals, hash, hashCode, hashIndex, isEmpty, isEqualKey, isEqualValue, keySet, put, putAll, remove, removeMapping, reuseEntry, size, toString, valuesfinalize, getClass, notify, notifyAll, wait, wait, waitclear, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, entrySet, equals, forEach, getOrDefault, hashCode, isEmpty, keySet, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size, valuesmapIteratorcontainsKey, containsValue, entrySet, isEmpty, keySet, remove, size, valuesprotected static final int DEFAULT_MAX_SIZE
public LRUMap()
public LRUMap(int maxSize)
maxSize - the maximum size of the map
IllegalArgumentException - if the maximum size is less than one
public LRUMap(int maxSize,
int initialSize)
maxSize - the maximum size of the map
initialSize - the initial size of the map
IllegalArgumentException - if the maximum size is less than one
IllegalArgumentException - if the initial size is negative or larger than the maximum size
public LRUMap(int maxSize,
boolean scanUntilRemovable)
maxSize - the maximum size of the map
scanUntilRemovable - scan until a removeable entry is found, default false
IllegalArgumentException - if the maximum size is less than one
public LRUMap(int maxSize,
float loadFactor)
maxSize - the maximum size of the map
loadFactor - the load factor
IllegalArgumentException - if the maximum size is less than one
IllegalArgumentException - if the load factor is less than zero
public LRUMap(int maxSize,
int initialSize,
float loadFactor)
maxSize - the maximum size of the map
initialSize - the initial size of the map
loadFactor - the load factor
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
public LRUMap(int maxSize,
float loadFactor,
boolean scanUntilRemovable)
maxSize - the maximum size of the map
loadFactor - the load factor
scanUntilRemovable - scan until a removeable entry is found, default false
IllegalArgumentException - if the maximum size is less than one
IllegalArgumentException - if the load factor is less than zero
public LRUMap(int maxSize,
int initialSize,
float loadFactor,
boolean scanUntilRemovable)
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
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
public LRUMap(Map<? extends K ,? extends V> map)
The maximum size is set from the map's size.
map - the map to copy
NullPointerException - if the map is null
IllegalArgumentException - if the map is empty
public LRUMap(Map<? extends K ,? extends V> map, boolean scanUntilRemovable)
map - the map to copy
scanUntilRemovable - scan until a removeable entry is found, default false
NullPointerException - if the map is null
IllegalArgumentException - if the map is empty
public V get(Objectkey)
This operation changes the position of the key in the map to the most recently used position (last).
public V get(Objectkey, boolean updateToMRU)
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.
key - the key
updateToMRU - whether the key shall be updated to the most recently used position
protected void moveToMRU(AbstractLinkedMap.LinkEntry <K ,V> entry)
This implementation moves the updated entry to the end of the list.
entry - the entry to update
protected void updateEntry(AbstractHashedMap.HashEntry <K ,V> entry, V newValue)
This implementation moves the updated entry to the end of the list using moveToMRU(AbstractLinkedMap.LinkEntry).
updateEntry in class
AbstractHashedMap<K,V>
entry - the entry to update
newValue - the new value to store
protected void addMapping(int hashIndex,
int hashCode,
K key,
V value)
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.
addMapping in class
AbstractHashedMap<K,V>
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 reuseMapping(AbstractLinkedMap.LinkEntry <K ,V> entry, int hashIndex, int hashCode, K key, V value)
This method uses AbstractLinkedMap, AbstractHashedMap and AbstractLinkedMap.
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 boolean removeLRU(AbstractLinkedMap.LinkEntry <K ,V> entry)
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.
entry - the entry to be removed
true
public boolean isFull()
isFull in interface
BoundedMap<K,V>
true if the map is full
public int maxSize()
maxSize in interface
BoundedMap<K,V>
public boolean isScanUntilRemovable()
public LRUMap<K ,V> clone()
clone in class
AbstractHashedMap<K,V>
protected void doWriteObject(ObjectOutputStreamout) throws IOException
put() to work in deserialization.
doWriteObject in class
AbstractHashedMap<K,V>
out - the output stream
IOException - if an error occurs while writing to the stream
protected void doReadObject(ObjectInputStreamin) throws IOException , ClassNotFoundException
put() to work in the superclass.
doReadObject in class
AbstractHashedMap<K,V>
in - the input stream
IOException - if an error occurs while reading from the stream
ClassNotFoundException - if an object read from the stream can not be loaded