LFU实现

 public static class Node{ //HashMap 
  
    records,key是用来查找 public Integer key; public Integer value; //HashMap 
   
     heads是根据times来排序的 public Integer times; public Node up; public Node down; //初始化 public Node(int key,int value,int times) { this.key=key; this.value=value; this.times=times; } } public static class LFUCache{ //head双向链表的每个节点都会有一个子双向链表 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() { //head==null为真，反之为假，查看当前双向列表是否为空 return head ==null; } public void deleteNode(Node node) { if(head==tail) { //链表中只有一个节点 head=null; tail=null; } //列表中不止一个节点 else { if(node==head) { //要删除的节点是头节点就进行换头操作（headList） 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; } } private int capacity;//容量 private int size;//现有节点数 private HashMap 
    
      records; private HashMap 
     
       heads; private NodeList headList; //每个频率次数的双向链表 public LFUCache(int capacity) { this.capacity=capacity; this.size=0; this.records=new HashMap<>(); this.heads=new HashMap<>(); headList=null; } public void set(int key,int value) { //如果records中包含此值 if (records.containsKey(key)) { //获得该节点 Node node=records.get(key); node.value=value; node.times++; //获得times++后的子双向链表 NodeList curNodeList=heads.get(node); //将set的节点从老链表移到新链表 move(node,curNodeList); } //如果records中不包含此值 else { //如果已经超出内存就要先移除一个，再添加 if(size==capacity) { //定位到head的尾部（那是访问频率最少处） Node node=headList.tail; //调用已经定义的删除节点函数 headList.deleteNode(node); modifyHeadList(headList); //移除node在records的记录 records.remove(node.key); //移除node在heads中的记录 heads.remove(node); size--; } Node node=new Node(key,value,1); if(headList==null) { //频率链表如果为空，Node为第一个值 headList=new NodeList(node); } //Node不是第一个值 else { //如果1频率的头节点存在，我就接着放 if(headList.head.equals(node.times)) { headList.addNodeFromHead(node); } //如果没有1频率的头节点，我就得新建一个 else{ NodeList newList=new NodeList(node); newList.next=headList; headList.last=newList; headList=newList; } } records.put(key, node); heads.put(node, headList); size++; } } //将访问过的节点从老链表移入新链表中 private void move(Node node,NodeList oldNodeList) { //老链表中先将要移除的节点移除 oldNodeList.deleteNode(node); //modifyHeadList(oldNodeList) //判断//删除节点后是否要将链表也删掉(发生在你把节点删除后) //如果删除了旧链表preList就是旧链表的前一个 //如果没有删除旧链表preList就是旧链表 NodeList preList=modifyHeadList(oldNodeList)?oldNodeList.last:oldNodeList; 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; } //将node换到newList中 heads.put(node, newList); } //如果旧链表后面接的不是空 else{ //如果节点的频率和旧链表后的频率相同 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; } //将node放到新链表中 heads.put(node, newList); } } } //删除节点后是否要将链表也删掉(发生在你把节点删除后) private boolean modifyHeadList(NodeList nodeList) { //如果删除节点后链表空了 if(nodeList.isEmpty()) { //如果频率链表和要删除的子链表相同 if(headList==nodeList) //新头部就是下一个 headList=nodeList.next; //如果新头部也是空就不用管 //如果新头部不为空 if(headList!=null) { //让它的前指向为空 headList.last=null; } } //如果删除节点后链表后没有空 else { nodeList.last.next=nodeList.next; //如果nodelist下一个节点不是空，让它的下个节点的前指向为上一个 if(nodeList.next!=null) { nodeList.next.last=nodeList.last; } return true; } return false; } }