LFU缓存算法（理解容易，主要是代码实现内外双map+双双向链表）

package arithmetic;

import java.util.HashMap;

public class FaceTest82 {
//LFU缓存置换算法
//比较词频，词频相同看时间点
//置换之后，词频重新开始累计
public FaceTest82(int k) {
capacity = k;
size = 0;
records = new HashMap<Integer, FaceTest82.Node>();
heads = new HashMap<>();
headList = null;
}

private int capacity;//最大缓存大小
private int size;//目前的节点数
private HashMap<Integer, Node> records;//表示key（Integer）由哪个节点代表
private HashMap<Node,NodeList> heads;//表示节点（Node）在哪个桶（NodeList） 里面
private NodeList headList;//整个结构中位于最左的桶 头桶

//节点的数据结构
public static class Node{
	public Integer key;
	public Integer value;
	public Integer times;//节点操作次数总和
	public Node up; //节点之间是双向链表所以有上一个节点
	public Node down; //节点之间是双向链表所以有下一个节点
	public Node(int k,int v,int t) {
		key = k;
		value = v;
		times = t;
	}
}

//桶结构
public static class NodeList {
	public Node head;//桶的头结点
	public Node tail;//桶的尾结点
	public NodeList last;//桶之间是双向链表所以有前一个
	public NodeList next;//桶之间是双向链表所以有后一个
	public NodeList(Node node) {
		head = node;
		tail = node;
	}
	//把一个新节点加入这个桶，新的节点都放在顶端变成新头结点
	public void addNodeFromHead(Node newHead) {
		newHead.down = head;
		head.up = newHead;
		head = newHead;
	}
	
	//判断这个桶是不是空的桶
	public boolean isEmpty() {
		return head == null;
	}
	
	//删除节点并保证node的上下文环境重新连接
	public void deleteNode(Node node) {
		if (head == tail) {
			head = null;
			tail = null;
		} else {
			//先保证上下节点重新连接
			if (node == head) {
				head = node.down;//移除顶端，下面的上来
				head.up = null;
			}else if (node == tail) {
				tail = node.up;
				tail.down = null;
			}else {
				node.up.down = node.down;
				node.down.up = node.up;
			}
		}
		//移除该节点
		node.up = null;
		node.down = null;
	}
	
}

// removeNodeList刚刚减少一个节点的桶
// 判断这个桶是不是已经空了
// 如果已经空了，再根据removeNodeList他是不是最左边的桶
// 如果是让removeNodeList他下一个桶做头桶，如果不是删掉后保证左右相连
// 函数返回值表示这个桶减少一个节点后是不是空桶
public boolean modifyHeadList(NodeList removeNodeList) {
	if (removeNodeList.isEmpty()) {
		if (headList == removeNodeList) {
			headList = removeNodeList.next;
			if (headList != null) {
				headList.last = null;// 新头桶左边指向空
			}
		} else {
			removeNodeList.last.next = removeNodeList.next;
			if (removeNodeList.next != null) {
				removeNodeList.next.last = removeNodeList.last;
			}
		}
		return true;
	}
	return false;
}

// 放入一个节点，
// 首先查看是否一个桶都没有,先创建
// 找桶放值，找不到创建
// 创建保证左右桶相连
// 找到桶，值满要删tail，遵循FIFO原则
public void put(int key, int value) {
	if (capacity == 0) {
		return;
	}
	if (records.containsKey(key)) {// 修改
		Node node = records.get(key);
		node.value = value;
		node.times++;// 修改词频
		NodeList curNodeList = heads.get(node);
		move(node, curNodeList);
	} else {
		if (size == capacity) {// 桶满的情况
			Node node = headList.tail;
			// 删除节点并对桶判空
			headList.deleteNode(node);
			modifyHeadList(headList);
			// 总map要删，heads标记桶的map也要删
			records.remove(node.key);
			heads.remove(node);
			size--;
		}
		// 放节点
		Node node = new Node(key, value, 1);
		if (headList == null) {// 没有桶，新建一个放节点就行
			headList = new NodeList(node);
		} else {// 寻找旧桶
			if (headList.head.times.equals(node.times)) {
				headList.addNodeFromHead(node);// 替换旧头部
			} else {// 找不到旧桶新建一个，左右连接一下，比如词频1的是空的，原来的都到别的桶上去了
				NodeList newList = new NodeList(node);
				newList.next = headList;
				headList.last = newList;
				headList = newList;// 新建并作为头桶
			}
		}
		// 总map和桶标记map都放入节点，容量++
		records.put(key, node);
		heads.put(node, headList);
		size++;
	}
}

public int get(int key) {
	if (!records.containsKey(key)) {
		return -1;
	}
	Node node = records.get(key);
	node.times++;
	NodeList curNodeList = heads.get(node);
	move(node, curNodeList);
	return node.value;
}

// 词频变化，换桶
// 把这个节点从原来的同移除
// 过程要保证任然是双向链表
private void move(Node node, NodeList oldNodeList) {
	oldNodeList.deleteNode(node);
	// oldNodeList原来的可能拿走这个节点后是个空桶
	// oldNodeList可能是中间的桶，所以还要保证空桶后要连接前后连个同
	// preList表示+1的桶的前一个桶是谁
	// 没有节点就用前一个桶
	NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList;
	// nextList表示次数+1的桶的后一个桶是谁
	NodeList nextList = oldNodeList.next;
	if (nextList == null) {// 后面没有桶
		NodeList newList = new NodeList(node);
		if (preList != null) {
			preList.next = newList;
		}
		newList.last = preList;
		if (headList == null) {
			headList = newList;
		}
		heads.put(node, newList);
	} else { // +1后有桶
		if (nextList.head.times.equals(node.times)) {// 找到同词频
			nextList.addNodeFromHead(node);
			heads.put(node, nextList);
		} else {// 找不到同词频，就新建
			NodeList newList = new NodeList(node);
			if (preList != null) {
				preList.next = newList;
			}
			newList.last = preList;
			newList.next = nextList;
			nextList.last = newList;
			if (headList == nextList) {
				headList = newList;
			}
			heads.put(node, newList);//重新标记桶
		}
	}
}

}