[数据结构与算法]Java使用双向链表和哈希表实现LRU缓存

Java使用双向链表和哈希表实现LRU缓存

• getValue(Integer key)：获取键对应的值，并标记最近使用过。

• setKeyValue(Integer key, String value)：将键值对插入到缓存，如果存在则删除旧的值。

• removeKey(Integer key)：将键值对从缓存中移除。

public class LRUCache {
	private Integer maxCacheSize;
	private Map<Integer, DoubleListNode> map;
	private DoubleListNode head;
	private DoubleListNode tail;

	public LRUCache(Integer maxCacheSize) {
		this.maxCacheSize = maxCacheSize;
		this.map = new HashMap<>();
	}

	/**
	 * 获取键对应的值，并标记最近使用过
	 *
	 * @param key
	 * @return
	 */
	public String getValue(Integer key) {
		DoubleListNode node = map.get(key);
		if (node == null) {
			return null;
		}
		// 移动到链表头部并标记最近使用过
		if (node != head) {
			// 从链表中移除节点
			removeFromLinkedList(node);
			// 插入到链表头部
			insertAtFrontOfLinkedList(node);
		}
		return node.value;
	}

	/**
	 * 将键值对插入到缓存，如果存在则删除旧的值
	 *
	 * @param key
	 * @param value
	 */
	public void setKeyValue(Integer key, String value) {
		// 如果存在则删除旧的值
		removeKey(key);

		// 如果元素数目超过缓存最大容量，则移除 最近最少使用 的元素（最久没有使用的元素）
		if (map.size() >= maxCacheSize && tail != null) {
			// 移除 最近最少使用 的元素（最近最少使用的元素位于链表尾部）
			removeKey(tail.key);
		}

		// 将键值对插入到缓存
		DoubleListNode node = new DoubleListNode(key, value);
		insertAtFrontOfLinkedList(node);
		map.put(key, node);
	}

	/**
	 * 将键值对从缓存中移除，即从链表和散列表中都移除
	 *
	 * @param key
	 */
	public void removeKey(Integer key) {
		DoubleListNode node = map.get(key);
		// 从链表中移除
		removeFromLinkedList(node);
		// 从散列表中移除
		map.remove(key);
	}

	/**
	 * 从链表中移除节点
	 *
	 * @param node
	 */
	private void removeFromLinkedList(DoubleListNode node) {
		if (node == null) {
			return;
		}
		// 如果node存在前驱节点，让前驱节点的后继指向node的后继节点
		if (node.pre != null) {
			node.pre.next = node.next;
		}
		// 如果node存在后继节点，让后继节点的前驱指向node的前驱节点
		if (node.next != null) {
			node.next.pre = node.pre;
		}
		// 如果删除的是尾节点，需要将tail前移
		if (node == tail) {
			tail = node.pre;
		}
		// 如果删除的是头节点，需要将head后移
		if (node == head) {
			head = node.next;
		}
	}

	/**
	 * 在链表头部插入节点
	 *
	 * @param node
	 */
	private void insertAtFrontOfLinkedList(DoubleListNode node) {
		// 要将node指针清空，否则会导致错误链接
		node.pre = node.next = null;
		// 当前没有节点
		if (head == null) {
			head = node;
			tail = node;
		} else {
			// 头节点的前驱指向node
			head.pre = node;
			// node的后继指向头节点
			node.next = head;
			// head指向node，更新头节点
			head = node;
		}
	}

	static class DoubleListNode {
		private Integer key;
		private String value;
		private DoubleListNode next, pre;

		public DoubleListNode(Integer key, String value) {
			this.key = key;
			this.value = value;
		}
	}
}