【创作赢红包】字节面试遇到的算法题目（LRU缓存机制自我实现题目）

刺骨的言语ヽ痛彻心扉 2024-03-24 12:48 45阅读 0赞

> 最近在字节的面试过程中，遇到了这样一道算法题目，其实很简单，就是我们经常用到的缓存机制-LRU（最近最少使用），今天有空，总结一下这次的这道面试题目。

## 1.题目 ##

题目其实很简单，就是请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。  
要求有：

*  不管是 get 还是 put ，必须以 O(1) 的平均时间复杂度运行
 *  其他特性满足LRU算法的特性即可  
    1）get时，如果存在，则返回key对应的value，同时调整这组数据（key-value）到头，如果不存在，则返回-1。  
    2）put时，如果存在，则覆盖key对应的value，同时调整这组数据（key-value）到头，如果不存在，则需要看，是否插入这组数据会导致容量超出，如果会导致容量超出，则需要最久未使用的数据，然后再插入

## 2.思考 ##

在日常编码中，相信大家经常用到的数据结构就是Arraylist、LinkedList、数组。我们之前对于Arraylist、LinkedList的底层原理，以及各种操作的时间复杂度、空间复杂度都进行过总结。

<table> 
 <thead> 
  <tr> 
   <th align="center"></th> 
   <th align="center">ArrayList</th> 
   <th align="center">LinkedList</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">数据结构</td> 
   <td align="center">Object数组</td> 
   <td align="center">双向链表</td> 
  </tr> 
  <tr> 
   <td align="center">线程安全</td> 
   <td align="center">否</td> 
   <td align="center">否</td> 
  </tr> 
  <tr> 
   <td align="center">add时间复杂度</td> 
   <td align="center">O（n）</td> 
   <td align="center">O（1）</td> 
  </tr> 
  <tr> 
   <td align="center">delete时间复杂度</td> 
   <td align="center">O（n）</td> 
   <td align="center">O（1）</td> 
  </tr> 
  <tr> 
   <td align="center">get时间复杂度</td> 
   <td align="center">O（1）</td> 
   <td align="center">O（n）</td> 
  </tr> 
  <tr> 
   <td align="center">快速访问</td> 
   <td align="center">支持</td> 
   <td align="center">不支持</td> 
  </tr> 
  <tr> 
   <td align="center">存储空间</td> 
   <td align="center">默认空余一些空间</td> 
   <td align="center">保存数据&amp;前后指针</td> 
  </tr> 
 </tbody> 
</table>

其实就是数组与链表的区别。

*  数组有位置与值的对应关系，知道index就可以拿到value，所以get的世界复杂度必然为O（1），而add、delete由于要找到相应的位置，才可以进行操作，所以时间复杂度也就是O（n）
 *  链表是一个一个的Node节点，连接在一起的，所以对于get来说，需要从NodeHead一直找到相应的节点才可以，所以时间复杂度为O（n），而add、delete相应的Node节点时，只需改变前面、后面的`指针`连接即可。

有了这两个数据结构的基础知识概念，那么我们现在设计的LRU cache数据结构，使用LinkedList无疑是最好的，因为最近最少机制里面，每次get、put元素，那么必定涉及到要将元素移动到`头`，而链表的移动元素来说，时间复杂度基本是O（1）。

但是我们知道有一个关键点，需要解决，目前要存储的是key-value形式的数据，那么我们想到数据结构为HashMap，但是我们知道单纯的HashMap存在key-value数据，但是我们知道Hashmap是基于数据+链表的结构去实现的，明显不具备上面我们所说的实现最近最少使用算法的前提。

这时我们想到了LinkedHashMap，基于LinkedHashMap去实现最近最少使用的数据结构封装。

## 3.实现 ##

有了实现思路，实现起来就简单很多了。

public class LruMap<K, V> extends LinkedHashMap<K, V> {
        
        // 初始容量
        private static final int INITIAL_CAPACITY = 16;
    
        // 加载因子，一般是0.75F
        private static final float LOAD_FACTOR = 0.75F;
    
        private int mCacheSize;
    
        private K mFirstKey;
    
        /**
         * 构造方法
         *
         * @param cacheSize 缓存大小
         */
        public LruMap(int cacheSize) {
        
            // 参数accessOrder -> false 基于插入顺序, true 基于访问顺序, get一个元素后，这个元素被自动加到最后
            super(INITIAL_CAPACITY, LOAD_FACTOR, true);
            mCacheSize = cacheSize;
        }
    
        @Override
        protected boolean removeEldestEntry(Entry<K, V> eldest) {
        
            // 当size大于缓存大小时，返回true会自动删除最少使用的数据
            boolean isNeedRemove = size() > mCacheSize;
            mFirstKey = isNeedRemove ? eldest.getKey() : null;
            return isNeedRemove;
        }
    
        /**
         * 获取自动删除的元素
         *
         * @return 自动删除的元素
         */
        public K getFirstKey() {
        
            return mFirstKey;
        }
    
        /**
         * 重置key
         */
        public void resetFirstKey() {
        
            mFirstKey = null;
        }
    }