LRU缓存算法简单设计

采用双链表+HashMap的形式实现LRU缓存算法，节点代码结构如下：

package com.Ycb.lru;

public class LRUNode {
	String key;
	Object value;
	LRUNode next;
	LRUNode pre;

	public LRUNode() {

	}

	public LRUNode(String key, Object value) {
		this.key = key;
		this.value = value;
	}
}

LRUCache如下，为了方便后续的操作，head和tail使用两个哨兵节点，代码如下：

package com.Ycb.lru;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
	Map<String, LRUNode> map;
	LRUNode head;
	LRUNode tail;

	// 缓存的最大容量
	int capacity;

	public LRUCache(int capacity) {
		if (capacity <= 0) {
			throw new IllegalArgumentException("Illegal initial capacity: " + capacity);
		}
		this.capacity = capacity;
		map = new HashMap<String, LRUNode>(capacity);

		// head 和 tail都采用哨兵节点解决,不进入HashMap
		head = new LRUNode();
		tail = new LRUNode();

		// 头节点与尾节点相连
		head.next = tail;
		tail.pre = head;
	}

	public void put(String key, Object value) {
		// 先从map中查询，看是否在map中
		LRUNode node = map.get(key);

		if (node != null) {
			// 说明在map中存在，则直接放到链表头，并且设置value
			node.value = value;

			// 移动到头节点之后
			removeAndInsert(node);
		} else {
			// 构造新节点
			LRUNode newNode = new LRUNode(key, value);

			if (map.size() >= capacity) {
				// 最后的一个节点
				LRUNode lastNode = tail.pre;

				// map移除
				map.remove(lastNode.key);

				// 双链表移除
				lastNode.pre.next = tail;
				tail.pre = lastNode.pre;
			}

			// 添加到字典中
			map.put(key, newNode);

			newNode.next = head.next;
			newNode.next.pre = newNode;
			head.next = newNode;
			newNode.pre = head;
		}
	}

	public Object get(String key) {
		LRUNode node = map.get(key);
		if (node != null) {
			// 添加到头节点
			removeAndInsert(node);

			// 返回值
			return node.value;
		}
        
        //如果找不到，此处返回-1.当然可以进行一些其他额外的操作
		return -1;
	}

	private void removeAndInsert(LRUNode node) {
		// 移动到链表头
		if (node.pre == head) {
			// 如果已经在链表头，则不移动
			return;
		} else {
			LRUNode nodePre = node.pre;
			LRUNode nodeNext = node.next;

			// 链表移动到头节点之后
			node.next = head.next;
			node.next.pre = node;
			head.next = node;
			node.pre = head;

			// 删除原节点
			nodePre.next = nodeNext;
			nodeNext.pre = nodePre;
		}
	}
}

仅作为个人记录