有关缓存,缓存算法,缓存框架:part 5 [转]

上一节中我们实现了随机缓存算法和FIFO缓存算法。现在，我们会继续实现另外两个著名的缓存算法：LFU和LRU。再一次说明，这些代码只是作为演示使用，如果你想在应用程序中使用，你还需要加上额外的工作。

看看LFU缓存算法的实现

public synchronized Object getElement(Object key) {

Object obj;

obj = table.get(key);

if (obj != null) {
	CacheElement element = (CacheElement) obj;
	element.setHitCount(element.getHitCount() + 1);
	return element.getObjectValue();
}
	return null;

}

public final synchronized void addElement(Object key, Object value) {

Object obj;

obj = table.get(key);

if (obj != null) {
	CacheElement element;

	// Just replace the value.
	element = (CacheElement) obj;
	element.setObjectValue(value);
	element.setObjectKey(key);

	return;
}

if (!isFull()) {

	index = numEntries;
	++numEntries;
} else {
	CacheElement element = removeLfuElement();
	index = element.getIndex();
	table.remove(element.getObjectKey());
}

	cache[index].setObjectValue(value);
	cache[index].setObjectKey(key);
	cache[index].setIndex(index);
	table.put(key, cache[index]);
}

public CacheElement removeLfuElement() {

	CacheElement[] elements = getElementsFromTable();
	CacheElement leastElement = leastHit(elements);
	return leastElement;
}

public static CacheElement leastHit(CacheElement[] elements) {

	CacheElement lowestElement = null;
	for (int i = 0; i < elements.length; i++) {
		CacheElement element = elements[i];
		if (lowestElement == null) {
			lowestElement = element;

		} else {
			if (element.getHitCount() < lowestElement.getHitCount()) {
				lowestElement = element;
			}
		}
	}
	return lowestElement;
}

最重点的代码，就应该是 leastHit 这个方法，这段代码就是把 hitCount 最低的元素找出来，然后删除，给新进的缓存元素留位置。

看看LRU缓存算法实现

private void moveToFront(int index) {
int nextIndex, prevIndex;

if(head != index) {
	nextIndex = next[index];
	prevIndex = prev[index];

	// Only the head has a prev entry that is an invalid index so
	// we don't check.
	next[prevIndex] = nextIndex;

	// Make sure index is valid. If it isn't, we're at the tail
	// and don't set prev[next].
	if(nextIndex >= 0)
		prev[nextIndex] = prevIndex;
	else
		tail = prevIndex;

	prev[index] = -1;
	next[index] = head;
	prev[head] = index;
	head = index;
}
}

public final synchronized void addElement(Object key, Object value) {
int index;
Object obj;

obj = table.get(key);

if(obj != null) {
	CacheElement entry;

	// Just replace the value, but move it to the front.
	entry = (CacheElement)obj;
	entry.setObjectValue(value);
	entry.setObjectKey(key);

	moveToFront(entry.getIndex());

	return;
}

// If we haven't filled the cache yet, place in next available spot
// and move to front.
if(!isFull()) {
	if(_numEntries > 0) {
		prev[_numEntries] = tail;
		next[_numEntries] = -1;
		moveToFront(numEntries);
	}
	++numEntries;
} else {
	// We replace the tail of the list.
	table.remove(cache[tail].getObjectKey());
	moveToFront(tail);
}

cache[head].setObjectValue(value);
cache[head].setObjectKey(key);
table.put(key, cache[head]);
}

这段代码的逻辑如 LRU算法 的描述一样，把再次用到的缓存提取到最前面，而每次删除的都是最后面的元素。

结论

我们已经看到 LFU缓存算法 和 LRU缓存算法的实现方式，至于如何实现，采用数组还是 LinkedHashMap，都由你决定，不够我一般是小的缓存容量用数组，大的用LinkedHashMap。

在下面一节中，我们将扯扯缓存框架，他们使用的缓存算法，并且做一些比较。