设计可以变更的缓存结构

待我称王封你为后i 2022-05-28 12:24 99阅读 0赞

![20180405161640137][]一、采用java库带的双向链表

import java.util.*;
    //设计可以变更的缓存结构
    public class CacheTest{
    	
        public static class Cache<K,V>{
    
               private K key;
               private V value;
        	   
        	   public Cache(K k, V v)
        	   {
        	   	   this.key=k;
        	   	   this.value=v;
        	   }
        }
        public static class CacheManu<K,V>{
        	
        	 private int size;
        	
        	public CacheManu(int n)
        	{
        		 this.size=n;
        	}
        	//生成一个队列当做可变的缓存结构
        	 @SuppressWarnings("rawtypes")
    		Queue<Cache>queue=new LinkedList<>();
    
        	  //设置set的功能
        	  @SuppressWarnings({ "rawtypes", "unchecked" })
    		public  void set(K k,V v)
        	{
        	  	  if(queue.size()<size)
        	  	  {
        	  		 queue.offer(new Cache(k,v));
        	  	  }else{
        	  		 queue.poll();
        	  		 queue.offer(new Cache(k,v));
        	  	  }
        		  
        	}
        	  //设置get的功能
        	  @SuppressWarnings("unchecked")
    		public  V get(K k)
        	 {
                   V v=null;
                    for(Cache<K, V> cache:queue)
                    {
                      if(cache.key==k)
                      {
                        v=(V) cache.value;
                        queue.offer(cache);
                        queue.poll();
                        break;
                      }
                   }
                   
                  return v;
        	}
    //        //交换两个节点的值
    //    	public  void swap(Cache<K, V> cache1,Cache<K, V> cache2)
    //    	{
    //    		 K k=null;
    //    		 V v=null;
    //    		 k=cache1.key;
    //    		 v=cache1.value;
    //    		 
    //    		 cache1.key=cache2.key;
    //    		 cache1.value=cache2.value;
    //    		 
    //    		 cache2.key=k;
    //    		 cache2.value=v;	  
    //    	}
        	 
        	//获得所有的值
        	public  void getAll()
        	{
        		  for(Cache<K, V> cache:queue)
                  {
        			  System.out.println(cache.key+" "+cache.value);
                  }
        		   
        	}
    
        }
    
    	public static void main(String[]args)
    	{
    		int size=3; //设置缓存的大小
    		CacheManu<String,Integer>cache=new CacheManu<>(size);
    		cache.set("a", 1);
    		cache.set("b", 2);
    		cache.set("c",3);
    		cache.getAll();
    		System.out.println("原始缓存大小:");
    		System.out.println(cache.get("a"));
    		cache.getAll();
    		cache.set("d", 4);
    		System.out.println("超出缓存大小后:");
    		cache.getAll();
    		
    	}
    }

![20180405161848215][]

二、自己写一个双向链表

import java.util.HashMap;
     //最近最少使用算法
    public class LeastRecentlyUsedCache {
    
    	public static class Node<V> {
    		public V value;
    		public Node<V> last;
    		public Node<V> next;
    
    		public Node(V value) {
    			this.value = value;
    		}
    	}
      
    	 //手写的双向链表
    	public static class NodeDoubleLinkedList<V> {
    		private Node<V> head;
    		private Node<V> tail;
    
    		public NodeDoubleLinkedList() {
    			this.head = null;
    			this.tail = null;
    		}
    
    		public void addNode(Node<V> newNode) {
    			if (newNode == null) {
    				return;
    			}
    			if (this.head == null) {
    				this.head = newNode;
    				this.tail = newNode;
    			} else {
    				this.tail.next = newNode;
    				newNode.last = this.tail;
    				this.tail = newNode;
    			}
    		}
    
    		public void moveNodeToTail(Node<V> node) {
    			if (this.tail == node) {
    				return;
    			}
    			if (this.head == node) {
    				this.head = node.next;
    				this.head.last = null;
    			} else {
    				node.last.next = node.next;
    				node.next.last = node.last;
    			}
    			node.last = this.tail;
    			node.next = null;
    			this.tail.next = node;
    			this.tail = node;
    		}
    
    		public Node<V> removeHead() {
    			if (this.head == null) {
    				return null;
    			}
    			Node<V> res = this.head;
    			if (this.head == this.tail) {
    				this.head = null;
    				this.tail = null;
    			} else {
    				this.head = res.next;
    				res.next = null;
    				this.head.last = null;
    			}
    			return res;
    		}
    
    	}
        //缓存的具体实现
    	public static class MyCache<K, V> {
    		private HashMap<K, Node<V>> keyNodeMap;
    		private HashMap<Node<V>, K> nodeKeyMap;
    		private NodeDoubleLinkedList<V> nodeList;
    		private int capacity;
    
    		public MyCache(int capacity) {
    			if (capacity < 1) {
    				throw new RuntimeException("should be more than 0.");
    			}
    			this.keyNodeMap = new HashMap<K, Node<V>>();
    			this.nodeKeyMap = new HashMap<Node<V>, K>();
    			this.nodeList = new NodeDoubleLinkedList<V>();
    			this.capacity = capacity;
    		}
    
    		public V get(K key) {
    			if (this.keyNodeMap.containsKey(key)) {
    				Node<V> res = this.keyNodeMap.get(key);
    				this.nodeList.moveNodeToTail(res);
    				return res.value;
    			}
    			return null;
    		}
    
    		public void set(K key, V value) {
    			if (this.keyNodeMap.containsKey(key)) {
    				Node<V> node = this.keyNodeMap.get(key);
    				node.value = value;
    				this.nodeList.moveNodeToTail(node);
    			} else {
    				Node<V> newNode = new Node<V>(value);
    				this.keyNodeMap.put(key, newNode);
    				this.nodeKeyMap.put(newNode, key);
    				this.nodeList.addNode(newNode);
    				if (this.keyNodeMap.size() == this.capacity + 1) {
    					this.removeMostUnusedCache();
    				}
    			}
    		}
    
    		private void removeMostUnusedCache() {
    			Node<V> removeNode = this.nodeList.removeHead();
    			K removeKey = this.nodeKeyMap.get(removeNode);
    			this.nodeKeyMap.remove(removeNode);
    			this.keyNodeMap.remove(removeKey);
    		}
    
    	}
    
    	public static void main(String[] args) {
    		MyCache<String, Integer> testCache = new MyCache<String, Integer>(3);
    		testCache.set("A", 1);
    		testCache.set("B", 2);
    		testCache.set("C", 3);
    		System.out.println(testCache.get("B"));
    		System.out.println(testCache.get("A"));
    		testCache.set("D", 4);
    		System.out.println(testCache.get("D"));
    		System.out.println(testCache.get("C"));
    
    	}
    
    }

![2018040516305116][]

[20180405161640137]: /images/20220528/d0b724fe9960418882031504502e456f.png
[20180405161848215]: /images/20220528/e1fa306b03254b85b7b82a7068f55646.png
[2018040516305116]: /images/20220528/6b7b0999a1c7492d85889342a8608b0b.png