Top Description Fields Constructors Methods
org.apache.commons.collections4.map

public Class LRUMap<K, V>

extends AbstractLinkedMap<K, V>
implements BoundedMap<K, V>, Serializable, Cloneable
Class Inheritance
All Implemented Interfaces
java.lang.Cloneable, java.io.Serializable, org.apache.commons.collections4.BoundedMap, org.apache.commons.collections4.IterableMap, org.apache.commons.collections4.IterableGet, org.apache.commons.collections4.Get, org.apache.commons.collections4.Put, java.util.Map
Type Parameters
<K>
the type of the keys in this map
<V>
the type of the values in this map
Imports
java.io.IOException, .ObjectInputStream, .ObjectOutputStream, .Serializable, java.util.Map, org.apache.commons.collections4.BoundedMap

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

Since
3.0 (previously in main package v1.0)

Field Summary

Modifier and TypeField 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

Inherited from org.apache.commons.collections4.map.AbstractLinkedMap:
header

Constructor Summary

AccessConstructor and Description
public
LRUMap()

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

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
LRUMap(final Map<? extends K, ? extends V>
the map to copy
map
)

Constructor copying elements from another map.

public
LRUMap(final Map<? extends K, ? extends V>
the map to copy
map
,
final boolean
scan until a removeable entry is found, default false
scanUntilRemovable
)

Constructor copying elements from another map.

Method Summary

Modifier and TypeMethod 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.apache.commons.collections4.map.AbstractHashedMap.addMapping.

Adds a new key-value mapping into this map.
public LRUMap<K, V>

Returns:

a shallow clone
clone
()

Overrides org.apache.commons.collections4.map.AbstractHashedMap.clone.

Clones the map without cloning the keys or values.
protected void
doReadObject(final ObjectInputStream
the input stream
in
)

Overrides org.apache.commons.collections4.map.AbstractHashedMap.doReadObject.

Reads the data necessary for put() to work in the superclass.
protected void
doWriteObject(final ObjectOutputStream
the output stream
out
)

Overrides org.apache.commons.collections4.map.AbstractHashedMap.doWriteObject.

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

Returns:

the mapped value, null if no match
get
(final Object
the key
key
)

Overrides org.apache.commons.collections4.map.AbstractHashedMap.get.

Implements java.util.Map.get, org.apache.commons.collections4.Get.get.

Gets the value mapped to the key specified.
public V

Returns:

the mapped value, null if no match
get
(final Object
the key
key
,
final boolean
whether the key shall be updated to the most recently used position
updateToMRU
)

Gets the value mapped to the key specified.

public boolean

Returns:

true if the map is full
isFull
()

Implements org.apache.commons.collections4.BoundedMap.isFull.

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

Returns:

true if this map scans
isScanUntilRemovable
()

Whether 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 hold
maxSize
()

Implements org.apache.commons.collections4.BoundedMap.maxSize.

Gets the maximum size of the map (the bound).
protected void
moveToMRU(final AbstractLinkedMap.LinkEntry<K, V>
the entry to update
entry
)

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

private void
readObject(final ObjectInputStream
the input stream
in
)

Read the map in using a custom routine.

protected boolean

Returns:

true
removeLRU
(final AbstractLinkedMap.LinkEntry<K, V>
the entry to be removed
entry
)

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

protected void
reuseMapping(final AbstractLinkedMap.LinkEntry<K, V>
the entry to reuse
entry
,
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
)

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

protected void
updateEntry(final AbstractHashedMap.HashEntry<K, V>
the entry to update
entry
,
final V
the new value to store
newValue
)

Overrides org.apache.commons.collections4.map.AbstractHashedMap.updateEntry.

Updates an existing key-value mapping.
private void
writeObject(final ObjectOutputStream
the output stream
out
)

Write the map out using a custom routine.

Inherited from org.apache.commons.collections4.map.AbstractLinkedMap:
addEntryclearcontainsValuecreateEntrycreateEntrySetIteratorcreateKeySetIteratorcreateValuesIteratorentryAfterentryBeforefirstKeygetEntrygetEntryinitlastKeymapIteratornextKeypreviousKeyremoveEntry

Field Detail

DEFAULT_MAX_SIZEback to summary
protected static final int DEFAULT_MAX_SIZE

Default maximum size

maxSizeback to summary
private transient int maxSize

Maximum size

scanUntilRemovableback to summary
private boolean scanUntilRemovable

Scan behaviour

serialVersionUIDback to summary
private static final long serialVersionUID

Serialisation version

Constructor Detail

LRUMapback to summary
public LRUMap()

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

LRUMapback to summary
public LRUMap(final int maxSize)

Constructs a new, empty map with the specified maximum size.

Parameters
maxSize:int

the maximum size of the map

Exceptions
IllegalArgumentException:
if the maximum size is less than one
LRUMapback to summary
public LRUMap(final int maxSize, final int initialSize)

Constructs a new, empty map with the specified maximum size.

Parameters
maxSize:int

the maximum size of the map

initialSize:int

the initial size of the map

Exceptions
IllegalArgumentException:
  • if the maximum size is less than one
  • if the initial size is negative or larger than the maximum size
Since
4.1
LRUMapback to summary
public LRUMap(final int maxSize, final boolean scanUntilRemovable)

Constructs a new, empty map with the specified maximum size.

Parameters
maxSize:int

the maximum size of the map

scanUntilRemovable:boolean

scan until a removeable entry is found, default false

Exceptions
IllegalArgumentException:
if the maximum size is less than one
Since
3.1
LRUMapback to summary
public LRUMap(final int maxSize, final float loadFactor)

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

Parameters
maxSize:int

the maximum size of the map

loadFactor:float

the load factor

Exceptions
IllegalArgumentException:
  • if the maximum size is less than one
  • if the load factor is less than zero
LRUMapback 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.

Parameters
maxSize:int

the maximum size of the map

initialSize:int

the initial size of the map

loadFactor:float

the load factor

Exceptions
IllegalArgumentException:
  • if the maximum size is less than one
  • if the initial size is negative or larger than the maximum size
  • if the load factor is less than zero
Since
4.1
LRUMapback 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.

Parameters
maxSize:int

the maximum size of the map

loadFactor:float

the load factor

scanUntilRemovable:boolean

scan until a removeable entry is found, default false

Exceptions
IllegalArgumentException:
  • if the maximum size is less than one
  • if the load factor is less than zero
Since
3.1
LRUMapback 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.

Parameters
maxSize:int

the maximum size of the map

initialSize:int

the initial size of the map

loadFactor:float

the load factor

scanUntilRemovable:boolean

scan until a removeable entry is found, default false

Exceptions
IllegalArgumentException:
  • if the maximum size is less than one
  • if the initial size is negative or larger than the maximum size
  • if the load factor is less than zero
Since
4.1
LRUMapback 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.

Parameters
map:Map<? extends K, ? extends V>

the map to copy

Exceptions
NullPointerException:
if the map is null
IllegalArgumentException:
if the map is empty
LRUMapback 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.

Parameters
map:Map<? extends K, ? extends V>

the map to copy

scanUntilRemovable:boolean

scan until a removeable entry is found, default false

Exceptions
NullPointerException:
if the map is null
IllegalArgumentException:
if the map is empty
Since
3.1

Method Detail

addMappingback to summary
protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value)

Overrides org.apache.commons.collections4.map.AbstractHashedMap.addMapping.

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:int

the index into the data array to store at

hashCode:int

the hash code of the key to add

key:K

the key to add

value:V

the value to add

Annotations
@Override
cloneback to summary
public LRUMap<K, V> clone()

Overrides org.apache.commons.collections4.map.AbstractHashedMap.clone.

Clones the map without cloning the keys or values.

Returns:LRUMap<K, V>

a shallow clone

Annotations
@Override
doReadObjectback to summary
protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException

Overrides org.apache.commons.collections4.map.AbstractHashedMap.doReadObject.

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

Parameters
in:ObjectInputStream

the input stream

Annotations
@Override
Exceptions
IOException:
if an error occurs while reading from the stream
ClassNotFoundException:
if an object read from the stream can not be loaded
doWriteObjectback to summary
protected void doWriteObject(final ObjectOutputStream out) throws IOException

Overrides org.apache.commons.collections4.map.AbstractHashedMap.doWriteObject.

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

Parameters
out:ObjectOutputStream

the output stream

Annotations
@Override
Exceptions
IOException:
if an error occurs while writing to the stream
getback to summary
public V get(final Object key)

Overrides org.apache.commons.collections4.map.AbstractHashedMap.get.

Implements java.util.Map.get, org.apache.commons.collections4.Get.get.

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).

Parameters
key:Object

the key

Returns:V

the mapped value, null if no match

Annotations
@Override
getback to summary
public V get(final Object key, final 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:Object

the key

updateToMRU:boolean

whether the key shall be updated to the most recently used position

Returns:V

the mapped value, null if no match

Since
4.1
isFullback to summary
public boolean isFull()

Implements org.apache.commons.collections4.BoundedMap.isFull.

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

Returns:boolean

true if the map is full

Annotations
@Override
isScanUntilRemovableback to summary
public boolean isScanUntilRemovable()

Whether this LRUMap will scan until a removable entry is found when the map is full.

Returns:boolean

true if this map scans

Since
3.1
maxSizeback to summary
public int maxSize()

Implements org.apache.commons.collections4.BoundedMap.maxSize.

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

Returns:int

the maximum number of elements the map can hold

Annotations
@Override
moveToMRUback to summary
protected void moveToMRU(final 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:AbstractLinkedMap.LinkEntry<K, V>

the entry to update

readObjectback to summary
private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException

Read the map in using a custom routine.

Parameters
in:ObjectInputStream

the input stream

Exceptions
IOException:
if an error occurs while reading from the stream
ClassNotFoundException:
if an object read from the stream can not be loaded
removeLRUback to summary
protected boolean removeLRU(final 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:AbstractLinkedMap.LinkEntry<K, V>

the entry to be removed

Returns:boolean

true

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

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

This method uses removeEntry, reuseEntry and addEntry.

Parameters
entry:AbstractLinkedMap.LinkEntry<K, V>

the entry to reuse

hashIndex:int

the index into the data array to store at

hashCode:int

the hash code of the key to add

key:K

the key to add

value:V

the value to add

updateEntryback to summary
protected void updateEntry(final AbstractHashedMap.HashEntry<K, V> entry, final V newValue)

Overrides org.apache.commons.collections4.map.AbstractHashedMap.updateEntry.

Updates an existing key-value mapping.

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

Parameters
entry:AbstractHashedMap.HashEntry<K, V>

the entry to update

newValue:V

the new value to store

Annotations
@Override
writeObjectback to summary
private void writeObject(final ObjectOutputStream out) throws IOException

Write the map out using a custom routine.

Parameters
out:ObjectOutputStream

the output stream

Exceptions
IOException:
if an error occurs while writing to the stream