本文共 3607 字，大约阅读时间需要 12 分钟。

思路

维护两个数据结构，1个用于“淘汰最远未使用的缓存”，另一个用于“缓存数据查询”

代码实现

import java.util.*;/** lru */class LruCache
   
     {
       private final int capacity;    private final KeyHolder
    
      keyHolder; // keyHolder也可以直接使用linkedHashMap。    private final HashMap
     
       data;    public LruCache(int capacity) {
           if (capacity < 1) {
               throw new RuntimeException("capacity can not less than 1");        }        this.capacity = capacity;        this.keyHolder = new KeyHolder<>();        this.data = new HashMap<>(capacity);    }    public boolean add(K key, V value) {
           if (data.size() < capacity || data.containsKey(key)) {
               this.keyHolder.remove(key);            this.keyHolder.add(key);            this.data.put(key, value);            return true;        } else {
               K key1 = this.keyHolder.poll();            if (key1 != null) {
                   System.out.println("缓存满，删除：" + key1);                this.data.remove(key1);            }            this.keyHolder.add(key);            this.data.put(key, value);            return true;        }    }    public V get(K key) {
           V value = this.data.get(key);        if (value != null) {
               this.keyHolder.remove(key);            this.keyHolder.add(key);        }        return value;    }    public Collection
      
        getAll() {
           return this.data.values();    }    public void remove(K key) {
           this.data.remove(key);        this.keyHolder.remove(key);    }        public static void main(String[] args) {
           LruCache
       
         cache = new LruCache<>(5);        cache.add("1", 1);        cache.add("2", 2);        cache.add("3", 3);        cache.add("4", 4);        cache.add("5", 5);        cache.add("2", 2);        cache.add("3", 3);        cache.add("1", 1);        cache.add("6", 6);        cache.add("7", 7);        cache.add("8", 8);        cache.add("9", 9);        cache.add("6", 6);        cache.add("7", 7);        cache.add("10", 10);        cache.add("11", 11);        cache.add("12", 12);        cache.add("13", 13);        cache.add("14", 14);        cache.add("1", 1);        System.out.println(cache.get("4"));        Collection
        
          values = cache.getAll(); for (Integer value : values) { System.out.println(value); } } static class Point
         
           { Point
          
            prev; Point
           
             next; K data; } static class KeyHolder
            
              { // 双向链表 private Point
             
               head; private Point
              
                tail; // hash表 private final HashMap
               
                > keyHash = new HashMap<>(); /** * 添加一个key * @param key */ void add(K key) { if (keyHash.containsKey(key)) { // key重复，删除后添加 this.remove(key); this.add(key); return; } Point
                
                  point = new Point
                 
                  (); point.data = key; if (this.tail == null) { // 队列中无数据，初始化 this.head = point; this.tail = point; } else { // 将key添加到尾部 this.tail.next = point; point.prev = this.tail; this.tail = point; } keyHash.put(key, point); } /** * 删除一个key * @param key */ void remove(K key) { Point
                  
                    keyPoint = this.keyHash.get(key); if (keyPoint == null) { // 无key，不删 return; } this.keyHash.remove(key); if (keyPoint.prev == null && keyPoint.next == null) { // 只有这一个节点，将队列设置为空 this.head = null; this.tail = null; } else if (keyPoint.prev == null) { // 这个key是头结点 this.head = keyPoint.next; this.head.prev = null; } else if (keyPoint.next == null) { // 这个key是尾结点 this.tail = keyPoint.prev; this.tail.next = null; } else { keyPoint.prev.next = keyPoint.next; keyPoint.next.prev = keyPoint.prev; } } /** * 从头出一个节点 * @return head */ K poll() { Point
                   
                     keyPoint = this.head; this.keyHash.remove(keyPoint.data); this.head = keyPoint.next; this.head.prev = null; return keyPoint.data; } }}
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/xxxxssss12/article/details/107662144 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！