org.apache.lucene.util.collections
Class LRUHashMap<K,V>
java.lang.Object
java.util.AbstractMap<K,V>
java.util.HashMap<K,V>
java.util.LinkedHashMap<K,V>
org.apache.lucene.util.collections.LRUHashMap<K,V>
- All Implemented Interfaces:
- Serializable, Cloneable, Map<K,V>
public class LRUHashMap<K,V>
- extends LinkedHashMap<K,V>
LRUHashMap is an extension of Java's HashMap, which has a bounded size();
When it reaches that size, each time a new element is added, the least
recently used (LRU) entry is removed.
Java makes it very easy to implement LRUHashMap - all its functionality is
already available from LinkedHashMap
, and we just need to
configure that properly.
Note that like HashMap, LRUHashMap is unsynchronized, and the user MUST
synchronize the access to it if used from several threads. Moreover, while
with HashMap this is only a concern if one of the threads is modifies the
map, with LURHashMap every read is a modification (because the LRU order
needs to be remembered) so proper synchronization is always necessary.
With the usual synchronization mechanisms available to the user, this
unfortunately means that LRUHashMap will probably perform sub-optimally under
heavy contention: while one thread uses the hash table (reads or writes), any
other thread will be blocked from using it - or even just starting to use it
(e.g., calculating the hash function). A more efficient approach would be not
to use LinkedHashMap at all, but rather to use a non-locking (as much as
possible) thread-safe solution, something along the lines of
java.util.concurrent.ConcurrentHashMap (though that particular class does not
support the additional LRU semantics, which will need to be added separately
using a concurrent linked list or additional storage of timestamps (in an
array or inside the entry objects), or whatever).
- See Also:
- Serialized Form
- WARNING: This API is experimental and might change in incompatible ways in the next release.
Constructor Summary |
LRUHashMap(int maxSize)
Create a new hash map with a bounded size and with least recently
used entries removed. |
Method Summary |
int |
getMaxSize()
Return the max size |
protected boolean |
removeEldestEntry(Map.Entry<K,V> eldest)
|
void |
setMaxSize(int maxSize)
setMaxSize() allows changing the map's maximal number of elements
which was defined at construction time. |
Methods inherited from interface java.util.Map |
containsKey, entrySet, equals, hashCode, isEmpty, keySet, put, putAll, remove, size, values |
LRUHashMap
public LRUHashMap(int maxSize)
- Create a new hash map with a bounded size and with least recently
used entries removed.
- Parameters:
maxSize
- the maximum size (in number of entries) to which the map can grow
before the least recently used entries start being removed.
Setting maxSize to a very large value, like
Integer.MAX_VALUE
is allowed, but is less efficient than
using HashMap
because our class needs
to keep track of the use order (via an additional doubly-linked
list) which is not used when the map's size is always below the
maximum size.
getMaxSize
public int getMaxSize()
- Return the max size
setMaxSize
public void setMaxSize(int maxSize)
- setMaxSize() allows changing the map's maximal number of elements
which was defined at construction time.
Note that if the map is already larger than maxSize, the current
implementation does not shrink it (by removing the oldest elements);
Rather, the map remains in its current size as new elements are
added, and will only start shrinking (until settling again on the
give maxSize) if existing elements are explicitly deleted.
removeEldestEntry
protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
- Overrides:
removeEldestEntry
in class LinkedHashMap<K,V>
Copyright © 2000-2011 Apache Software Foundation. All Rights Reserved.