[LeetCode146] LRU 缓存机制（LinkedHashMap 实现）

package com.wangxiaohu;

import java.util.linkedHashMap;

public class LeetCode146 {

    
    class LRUCache {

        private int size;
        linkedHashMap cache = new linkedHashMap<>();

        public LRUCache(int capacity) {
            this.size = capacity;
        }

        public int get(int key) {
            if (!cache.containsKey(key)) {
                return -1;
            }
            // 将 key 变为最近使用
            makeKeyRecently(key);
            return cache.get(key);
        }

        public void put(int key, int value) {
            if (cache.containsKey(key)) {
                // 修改 key 的值
                cache.put(key, value);
                // 将 key 变为最近使用
                makeKeyRecently(key);
                return;
            }
            // 如果不存在
            // 缓存满了
            if (cache.size() >= this.size) {
                // 链表头部就是最久未使用的 key
                int oldestKey = cache.keySet().iterator().next();
                cache.remove(oldestKey);
            }

            // 将新的 key 添加链表尾部
            cache.put(key, value);
        }

        private void makeKeyRecently(int key) {
            int val = cache.get(key);
            // 删除 key，重新插入到队尾
            cache.remove(key);
            cache.put(key, val);
        }
    }
}