org.apache.kahadb.util
Class LFUCache<Key,Value>
java.lang.Object
org.apache.kahadb.util.LFUCache<Key,Value>
- All Implemented Interfaces:
- java.util.Map<Key,Value>
public class LFUCache<Key,Value>
- extends java.lang.Object
- implements java.util.Map<Key,Value>
LFU cache implementation based on http://dhruvbird.com/lfu.pdf, with some notable differences:
-
Frequency list is stored as an array with no next/prev pointers between nodes: looping over the array should be faster and more CPU-cache friendly than
using an ad-hoc linked-pointers structure.
-
The max frequency is capped at the cache size to avoid creating more and more frequency list entries, and all elements residing in the max frequency entry
are re-positioned in the frequency entry linked set in order to put most recently accessed elements ahead of less recently ones,
which will be collected sooner.
-
The eviction factor determines how many elements (more specifically, the percentage of) will be evicted.
As a consequence, this cache runs in *amortized* O(1) time (considering the worst case of having the lowest frequency at 0 and having to evict all
elements).
- Author:
- Sergio Bossa
Nested classes/interfaces inherited from interface java.util.Map |
java.util.Map.Entry<K,V> |
Constructor Summary |
LFUCache(int maxCacheSize,
float evictionFactor)
|
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Methods inherited from interface java.util.Map |
equals, hashCode |
LFUCache
public LFUCache(int maxCacheSize,
float evictionFactor)
put
public Value put(Key k,
Value v)
- Specified by:
put
in interface java.util.Map<Key,Value>
putAll
public void putAll(java.util.Map<? extends Key,? extends Value> map)
- Specified by:
putAll
in interface java.util.Map<Key,Value>
get
public Value get(java.lang.Object k)
- Specified by:
get
in interface java.util.Map<Key,Value>
remove
public Value remove(java.lang.Object k)
- Specified by:
remove
in interface java.util.Map<Key,Value>
frequencyOf
public int frequencyOf(Key k)
clear
public void clear()
- Specified by:
clear
in interface java.util.Map<Key,Value>
keySet
public java.util.Set<Key> keySet()
- Specified by:
keySet
in interface java.util.Map<Key,Value>
values
public java.util.Collection<Value> values()
- Specified by:
values
in interface java.util.Map<Key,Value>
entrySet
public java.util.Set<java.util.Map.Entry<Key,Value>> entrySet()
- Specified by:
entrySet
in interface java.util.Map<Key,Value>
size
public int size()
- Specified by:
size
in interface java.util.Map<Key,Value>
isEmpty
public boolean isEmpty()
- Specified by:
isEmpty
in interface java.util.Map<Key,Value>
containsKey
public boolean containsKey(java.lang.Object o)
- Specified by:
containsKey
in interface java.util.Map<Key,Value>
containsValue
public boolean containsValue(java.lang.Object o)
- Specified by:
containsValue
in interface java.util.Map<Key,Value>
Copyright © 2005-2015. All Rights Reserved.