题解 | #设计LRU缓存结构#

思路

• 采用Java集合中的LinkedHashMap数据结构，在HashMap的基础上，使用了前后指针完成双向链表，从而可以实现快速查找，并且可以顺序遍历访问元素。

import java.util.*;


public class Solution {

    private int capacity;
    private LinkedHashMap<Integer, Integer> cache;

    public Solution(int capacity) {
         // write code here
        this.capacity = capacity;
        cache = new LinkedHashMap<>();
    }

    public int get(int key) {
         // write code here
        if(!cache.containsKey(key)){
            return -1;
        }
        // 返回前，将其提示为最近使用的
        makeRecently(key);
        return cache.get(key);
    }

    public void set(int key, int value) {
         // write code here
        if(cache.containsKey(key)){  // 已经存在
            cache.put(key, value);  // 更新数据
            makeRecently(key);
            return;
        }
        if(cache.size() == capacity){
            // keySet()获取键的集合,iterator()获取键集合的迭代器
            Iterator<Integer> iter = cache.keySet().iterator();
            int oldKey = iter.next();  // 获取键集合中的第一个元素
            cache.remove(oldKey);  // 删除第一个键值对
        }
        cache.put(key, value);
    }

    private void makeRecently(int key){
        int value = cache.get(key);
        cache.remove(key);  // 删除键值对
        cache.put(key, value);  // 重新插入到尾部
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */