[算法]链表+HashMap实现LRU算法

谁借莪１个温暖的怀抱￠ 2022-04-08 10:30 201阅读 0赞

/**
     * @author :dongshuo
     * @date : 2018/12/10 14:27
     * @desc : 链表+hashmap实现的
     */
    public class LRUCache1<K,V> {
        private final int MAX_CACHE_SIZE;//最大的缓存大小
        private Entry first; //头元素
        private Entry last;//尾元素
    
        private HashMap<K, Entry<K, V>> hashMap;//用来保存的hashmap
    
        /**
         * 初始化 缓存大小和对象
         * @param cacheSize
         */
        public LRUCache1(int cacheSize) {
            MAX_CACHE_SIZE = cacheSize;
            hashMap = new HashMap<K, Entry<K, V>>();
        }
    
        /**
         * 存入k,v
         * @param key
         * @param value
         */
        public void put(K key, V value) {
            //1首先判断是否存在该值
            Entry entry = getEntry(key);
            //如果为空
            if (entry == null) {
                if (hashMap.size() >= MAX_CACHE_SIZE) {
                    hashMap.remove(last.key);
                    removeLast();
                }
                entry = new Entry();
                entry.key = key;
            }
            entry.value = value;
            moveToFirst(entry);
            hashMap.put(key, entry);
        }
    
        public V get(K key) {
            Entry<K, V> entry = getEntry(key);
            if (entry == null) return null;
            moveToFirst(entry);
            return entry.value;
        }
    
        public void remove(K key) {
            Entry entry = getEntry(key);
            if (entry != null) {
                if (entry.pre != null) entry.pre.next = entry.next;
                if (entry.next != null) entry.next.pre = entry.pre;
                if (entry == first) first = entry.next;
                if (entry == last) last = entry.pre;
            }
            hashMap.remove(key);
        }
    
        /**
         * 将元素移到first
         * @param entry
         */
        private void moveToFirst(Entry entry) {
            if (entry == first) return;//元素已经在first位置了
            if (entry.pre != null) entry.pre.next = entry.next;
            if (entry.next != null) entry.next.pre = entry.pre;
            if (entry == last) last = last.pre;//元素在last位置
    
            if (first == null || last == null) {
                first = last = entry;
                return;
            }
    
            entry.next = first;//元素放到first
            first.pre = entry;
            first = entry;
            entry.pre = null;
        }
    
        /**
         * 删除最后一个元素
         */
        private void removeLast() {
            if (last != null) {
                last = last.pre;//last元素被删除,last前驱作为最后一个元素
                if (last == null) first = null;//如果 first=last情况时
                else last.next = null;//last后继为null
            }
        }
    
        /**
         * 判断map是否存在该key,value
         * @param key
         * @return
         */
        private Entry<K, V> getEntry(K key) {
            return hashMap.get(key);
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Entry entry = first;
            while (entry != null) {
                sb.append(String.format("%s:%s ", entry.key, entry.value));
                entry = entry.next;
            }
            return sb.toString();
        }
    
        /**
         * 内部类 链表
         * @param <K>
         * @param <V>
         */
        class Entry<K, V> {
            public Entry pre;
            public Entry next;
            public K key;
            public V value;
        }
    }