JAVA有序表（双向链表）实现LRU缓存算法，用哈希表（HashMap）降低时间复杂度

上一篇我们用链表简单的实现了LRU的算法思维以及算法，我们最后分析的时间复杂度为0(n)，n为链表中的长度，我们用的是单链表，单链表实现的，所有删除需要查找到对应的节点，利用哨兵的思维，监控查找的前一个节点。就能轻松实现删除。上一篇的LRU分析和简单实现

有没有更好的办法来降低时间的复杂度呢？答案是利用哈希表，哈希表的key就是链表中的data，哈希表的value，存储的是每一个节点node。我们在查找和删除的时候，只需要在HashMap中找到node，然后从链表中删除node，而我们利用哈希表删除，查找，添加的时间复杂度接近O（1），

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

public class Chain {
	public class Node{
		public int data;
		public Node next;
		public Node pre;
	}
	
	private Map map=new HashMap();
	
	private Node head=null;
	
	private Node tail=null;
	
	public void LUR(int data) {
		
		if(map.containsKey(data)) {
			Node node=map.get(data);
			
			 if(node.data==tail.data) {
				//tail=tail.pre;
				//tail.next=null;
				 delNode(data);
				 
				node.next=head;
				head.pre=node;
				head=node;
			}
			 
			if(node.data!=head.data) {		
				node.next.pre=node.pre;
				node.pre.next=node.next;
				node.next=head;
				node.pre=node;
				head=node;//头指针永远指向头
			}		
		}
		
		else {
			
			if(head==null) {
				addNode(data);	
			}
			else {
				
				Node node=new Node();
				node.data=data;
				node.next=head;
				head.pre=node;
				head=node;
				map.put(data, node);
			}
		}
	}
	
	public void delNode(int data) {
		Node node=map.get(data);
		map.remove(data);//把值从map中删除
		if(node.data==head.data) {
			
			head=head.next;
			head.pre=null;//头节点的下一个节点赋值给头节点。此时的头节点的pre是有值的，所以需要置为null；	
		}
		else if(node.data==tail.data) {
			tail=tail.pre;
			tail.next=null;	
		}
		else {
			
			node.next.pre=node.pre;
			
			node.pre.next=node.next;
		}	
	}
	
	public void addNode(int data) {
		Node node=new Node();
		node.data=data;
		map.put(data, node);
		if(head==null) {
			head=node;
			tail=node;
		}
		else {
			node.pre=tail;
			tail.next=node;
			tail=node;	
		}	
	}
	
	public boolean searchNode(int data) {
		return map.containsKey(data);
	}
	
	
	
	public void testMap(int data) {
		Node node=map.get(data);
		System.out.println("******************test:"+node.pre.data);
	}
	
	
	public void printlNode() {
		
		Node target=head;
		while(target!=null) {
			System.out.println(target.data);
			target=target.next;
		}
		
	}
}

public class testMain {
	public static void main(String[] args) {
		Chain chain=new Chain();
		chain.addNode(1);
		chain.addNode(2);
		chain.addNode(3);
		chain.addNode(4);
		chain.addNode(5);
		
		chain.LUR(5);
		chain.LUR(6);
		chain.LUR(6);
		chain.LUR(7);
		chain.LUR(7);
		
		
		
		chain.delNode(7);
		
	//System.out.println(chain.searchNode(6));
		
		//chain.testMap(2);
		chain.printlNode();
	}

}

本次代码没有完成一个小小的功能，缓存系统的大小。如果有需要可以自己实现，需要引入一个哨兵来监控缓存系统的剩余容量，如果满则删除链表的尾节点，只需要挪动哨兵tail指针即可删除。