简述
今天看dubbo源码学习了其中LFUCache的实现，今天把这种实现先记下来
思想
待完成~
代码实现
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
public class LFUCache<K, V> {
private Map<K, CacheNode<K, V>> map;
private CacheDeque<K, V>[] freqTable;
private final int capacity;
private int evictionCount;
private int curSize = 0;
private final ReentrantLock lock = new ReentrantLock();
private static final int DEFAULT_INITIAL_CAPACITY = 1000;
private static final float DEFAULT_EVICTION_FACTOR = 0.75f;
public LFUCache() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_EVICTION_FACTOR);
}
/**
* Constructs and initializes cache with specified capacity and eviction
* factor. Unacceptable parameter values followed with
* {@link IllegalArgumentException}.
*
* @param maxCapacity cache max capacity
* @param evictionFactor cache proceedEviction factor
*/
@SuppressWarnings("unchecked")
public LFUCache(final int maxCapacity, final float evictionFactor) {
if (maxCapacity <= 0) {
throw new IllegalArgumentException("Illegal initial capacity: " +
maxCapacity);
}
boolean factorInRange = evictionFactor <= 1 && evictionFactor > 0;
if (!factorInRange || Float.isNaN(evictionFactor)) {
throw new IllegalArgumentException("Illegal eviction factor value:"
+ evictionFactor);
}
this.capacity = maxCapacity;
this.evictionCount = (int) (capacity * evictionFactor);
this.map = new HashMap<>();
this.freqTable = new CacheDeque[capacity + 1];
for (int i = 0; i <= capacity; i++) {
freqTable[i] = new CacheDeque<>();
}
for (int i = 0; i < capacity; i++) {
freqTable[i].nextDeque = freqTable[i + 1];
}
freqTable[capacity].nextDeque = freqTable[capacity];
}
public int getCapacity() {
return capacity;
}
public V put(final K key, final V value) {
CacheNode<K, V> node;
lock.lock();
try {
node = map.get(key);
if (node != null) {
CacheNode.withdrawNode(node);
node.value = value;
freqTable[0].addLastNode(node);
map.put(key, node);
} else {
curSize++;
if (curSize > capacity) {
proceedEviction();
}
node = freqTable[0].addLast(key, value);
map.put(key, node);
}
} finally {
lock.unlock();
}
return node.value;
}
public V remove(final K key) {
CacheNode<K, V> node = null;
lock.lock();
try {
if (map.containsKey(key)) {
node = map.remove(key);
if (node != null) {
CacheNode.withdrawNode(node);
}
curSize--;
}
} finally {
lock.unlock();
}
return (node != null) ? node.value : null;
}
public V get(final K key) {
CacheNode<K, V> node = null;
lock.lock();
try {
if (map.containsKey(key)) {
node = map.get(key);
CacheNode.withdrawNode(node);
node.owner.nextDeque.addLastNode(node);
}
} finally {
lock.unlock();
}
return (node != null) ? node.value : null;
}
/**
* Evicts less frequently used elements corresponding to eviction factor,
* specified at instantiation step.
*
* @return number of evicted elements
*/
private int proceedEviction() {
int targetSize = capacity - evictionCount;
int evictedElements = 0;
FREQ_TABLE_ITER_LOOP:
for (int i = 0; i <= capacity; i++) {
CacheNode<K, V> node;
while (!freqTable[i].isEmpty()) {
node = freqTable[i].pollFirst();
remove(node.key);
if (targetSize >= curSize) {
break FREQ_TABLE_ITER_LOOP;
}
evictedElements++;
}
}
return evictedElements;
}
/**
* Returns cache current size.
*
* @return cache size
*/
public int getSize() {
return curSize;
}
static class CacheNode<K, V> {
CacheNode<K, V> prev;
CacheNode<K, V> next;
K key;
V value;
CacheDeque<K, V> owner;
CacheNode() {
}
CacheNode(final K key, final V value) {
this.key = key;
this.value = value;
}
/**
* This method takes specified node and reattaches it neighbors nodes
* links to each other, so specified node will no longer tied with them.
* Returns united node, returns null if argument is null.
*
* @param node note to retrieve
* @param <K> key
* @param <V> value
* @return retrieved node
*/
static <K, V> CacheNode<K, V> withdrawNode(
final CacheNode<K, V> node) {
if (node != null && node.prev != null) {
node.prev.next = node.next;
if (node.next != null) {
node.next.prev = node.prev;
}
}
return node;
}
}
/**
* Custom deque implementation of LIFO type. Allows to place element at top
* of deque and poll very last added elements. An arbitrary node from the
* deque can be removed with {@link CacheNode#withdrawNode(CacheNode)}
* method.
*
* @param <K> key
* @param <V> value
*/
static class CacheDeque<K, V> {
CacheNode<K, V> last;
CacheNode<K, V> first;
CacheDeque<K, V> nextDeque;
/**
* Constructs list and initializes last and first pointers.
*/
CacheDeque() {
last = new CacheNode<>();
first = new CacheNode<>();
last.next = first;
first.prev = last;
}
/**
* Puts the node with specified key and value at the end of the deque
* and returns node.
*
* @param key key
* @param value value
* @return added node
*/
CacheNode<K, V> addLast(final K key, final V value) {
CacheNode<K, V> node = new CacheNode<>(key, value);
node.owner = this;
node.next = last.next;
node.prev = last;
node.next.prev = node;
last.next = node;
return node;
}
CacheNode<K, V> addLastNode(final CacheNode<K, V> node) {
node.owner = this;
node.next = last.next;
node.prev = last;
node.next.prev = node;
last.next = node;
return node;
}
/**
* Retrieves and removes the first node of this deque.
*
* @return removed node
*/
CacheNode<K, V> pollFirst() {
CacheNode<K, V> node = null;
if (first.prev != last) {
node = first.prev;
first.prev = node.prev;
first.prev.next = first;
node.prev = null;
node.next = null;
}
return node;
}
/**
* Checks if link to the last node points to link to the first node.
*
* @return is deque empty
*/
boolean isEmpty() {
return last.next == first;
}
}
}
评论区