开发者

java面试LruCache 和 LinkedHashMap及算法实现

目录
  • LruCache
  • LinkedHashMap
  • android 的 LruCache 源码分析
    • resize
    • get
    • put
    • remove
  • 容量计算
    • 总结
      • 常见算法题

        LruCache

        保存对有限数量值的强引用的缓存。 每次访问一个值时,它都会移动到队列的头部。 当一个值被添加到一个完整的缓存中时,该队列末尾的值将被逐出并且可能有资格进行垃圾回收。

        Least Recently Used , 最近最少使用,是一种常用的算法。

        LRUCache 是具有一定数量限制的数据结构,该数据结构采用 LRU 算法,维护一定数量的缓存数据。如果数据结构已经达到了最大数量限制时,有新的数据插入,则就需要根据 LRU 算法,删除最久未使用的数据。

        根据它的功能描述,对数据结构的选择就有了偏向性:

        • 定义中提到了队列,实现队列的两种底层数据结构是链表和数组。
        • 根据每次删除最后一个元素的特性,可以优先考虑链表结构。
        • 如果集合中已存在要添加的元素,优先将其移动到队头,优先考虑链表结构,因为数组的移动开销更大。
        • 每次添加新元素都要查询一遍集合中是否存在该元素,链表结构相比数组的查询时间复杂度更高,所以优先考虑数组和用来辅助查询时间复杂度低的 Map 。

        综合前两点考虑,LinkedList 配合 HashMap 是一个不错的选择,前者不光可以是链表结构、还实现了 Deque ,也可以视为队列、栈结构, 后者提供了更低时间复杂度的检索。

        而在 JDK 中,提供了 LinkedHashMap 用来实现 LRU 缓存的功能。

        LinkedHashMap

        LinkedHashMap 继承自 HashMap ,并实现了 Map 接口。构造方法包含了一个 AccessOrder 参数,该参数会将元素按照访问顺序进行排序,非常适合构建 LRUCache 。

        LinkedHashMap 与 HashMap 不同之处在于维护了一个**双向链表,该列表串联起了所有元素。**这个链表定义了迭代顺序,通常是键插入映射的顺序(插入顺序)。

        请注意,如果将键重新插入到 Map 中,则插入顺序不会受到影响。 (如果在调用 m.containsKey(k) 时调用 m.put(k, v) 将在调用之前立即返回 true,则将键 k 重新插入到映射 mphp 中。)

        内部的双向链表结构:

            /**
             * The head (eldest) of the doubly linked list.
             */
            transient LinkedHashMap.Entry<K,V> head;
            /**
             * The tail (youngest) of the doubly linked list.
             */
            transient LinkedHashMap.Entry<K,V> tail;
        

        每次访问元素后,如果启用访问排序(accessOrder = true),会更新链表中的元素顺序:

            public V get(Object key) {
                Node&lt;K,V&gt; e;
                if ((e = getNode(key)) == null)
                    return null;
                if (accessOrder)
                    afterNodeAccess(e);
                return e.value;
            }
        

        核心的排序逻辑在 afterNodeAccess 方法中,将最新访问的元素移动到了链表尾部:

        void afterNodeAccess(Node<K,V> e) { // move node to last
            LinkedHashMap.Entry<K,V> last;
            // 双向链表尾部节点 last
            编程客栈if (accessOrder && (last = tail) != e) {
                // 访问的节点标记为 p ,p 的前后节点保存到 b 、a 中
                LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
                // 访问节点的后续节点设置为 null ,因为是最后一个节点,所以后续节点为 null
                p.after = null; 
                // 处理删除 e 节点的逻辑
                if (b == null)
                     // p 的前面不存在节点,头节点设置为 a 
                    head = a;
                else 
                    // p 的前面存在节点,将 p 的后续节点设置为 p 前一个节点的下一个节点  b -> p -> a 更新为 b -> a (删除 p)
                    b.after = a;
                if (a != null)
                    // p 存在后续节点 a , 将 a 的 before 指针更新为 b
                    a.before = b;
                else
                    // p 不存在后续节点 a , last 指针更新为 b
                    last = b;
                // 处理尾部节点的逻辑
                if (last == null)
                    // last 指针为空,更新头节点
                    head = p;
                else {
                    // last 指针不为空,更新链表顺序为 last 
                    p.before = last;
                    last.after = p;
                }
                tail = p;
                ++modCount;
            }
        }
        

        所以这是一种十分适合 LRUCache 的数据结构,Android 中的 LRUCache 类就是通过 LinkedHashMap 来实现的。

        public class LruCache<K, V> {
            private final LinkedHashMap<K, V> map;
        		//...
        }
        

        Android 的 LruCache 源码分析

        LruCache 是 Android SDK 中提供一个类,来自于 android.util

        LruCache 中有两个核心方法,get 和 put ,再加上容量变化处理方法,构成了完善的 LRU 机制。它的内部的数据结构是 LinkedHashMap ,通过属性控制容量:

        public class LruCache<K, V> {
            private final LinkedHashMap<K, V> map;
            private int size;
            private int maxSize;
            private int putCount;
            private int createCount;
            private int evictionCount;
            private int hitCount;
            private int missCount;
            public LruCache(int maxSize) {
                if (maxSize <= 0) {
                 开发者_自学开发   throw new IllegalArgumentException("maxSize <= 0");
                }
                this.maxSize = maxSize;
              	// 启用了 访问排序 accessOrder = true
                this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 
            }
        		//...
        }
        

        resize

        当重新设置 LruCache 的容量时,可以通过 resize 分发重新设置容量:

            public void resize(int maxSize) {
                if (maxSize <= 0) {
                    throw new IllegalArgumentException("maxSize <= 0");
                }
                synchronized (this) {
                    this.maxSize = maxSize;
                }
                trimToSize(maxSize);
            }
        

        容量处理伴随着删除最久未使用的元素:

            // 删除最老的元素,直到剩余元素的总数等于或低于请求的大小。
            public void trimToSize(int maxSize) {
                while (true) {
                    K key;
                    V value;
                    synchronized (this) {
                        if (size < 0 || (map.isEmpty() && size != 0)) {
                            throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!");
                        }
                        if (size <= maxSize) {
                            break;
                        }
                        Map.Entry<K, V> toEvict = map.eldest();
                        if (toEvict == null) {
                            break;
                        }
                        key = toEvict.getKey();
                        value = toEvict.getValue();
                        map.remove(key);
                        size -= safeSizeOf(key, value);
                        evictionCount++;
                    }
                    entryRemoved(true, key, value, null);
                }
            }
        

        在这个方法中,通过 map.eldest() 获取到了存活最久的元素,它的实现是:

        		// in LinkedHashMap
        		public Map.Entry<K, V> eldest() {
                return head;
            }
        

        最后的 entryRemoved 方法的作用是,通过调用 remove 移除或通过调用 put 替换时,将一个值被移除以腾出空间,将调用此方法。 默认实现什么也不做。

        get

        get 方法根据 key 检索 LinkedHashMap 中是否存在对应的元素,或者是否可以根据 create 方法创建元素。如果存在或可根据 create 方法创建,则将这个元素移动到队列头部,否则返回 null。

            public final V get(K key) {
              	// key 空检查
                if (key == null) {
                    throw new NullPointerException("key == null");
                }
                V mapValue;
                synchronized (this) {
                    mapValue = map.get(key); // 从 map 中读取元素
                    if (mapValue != null) { // 缓存中存在元素,直接返回
                        hitCount++; 
                        return mapValue; 
                    }
                    missCount++; 
                }
        				// 缓存中不存在对应 key 的元素,创建一个新元素
                V createdValue = create(key); 
                if (createdValue == null) { // 未缓存且无法创建,返回 null
                    return null;
                }
        				// 创建成功,存入到 map ,如果 key 已存在对应值,优先更新为之前的值
                synchronized (this) {
                    createCount++;	
                    mapValue = map.put(key, createdValue); // 存入新的元素,并获取前一个 key 对应的值 mapValue。
                    if (mapValue != null) {
                        map.put(key, eOYkbJmapValue);
                    } else {
                        size += safeSizeOf(key, createdValue); // 新元素导致当前容量 + 1
                    }
                }
                if (mapValue != null) { // key 对应的元素已存在
                  	// 当一个值被逐出以腾出空间、通过调用 remove 移除或通过调用 put 替换时,将调用此方法。 默认实现什么也不做。
                    entryRemoved(false, key, createdValue, mapValue);
                    return mapValue; 
                } else { // key 对应的元素不存在
                    trimToSize(maxSize); // 扩容
                    return createdValue; //返回最新插入的元素
                }
            }
        

        这里的 create 方法默认返回 null , 供子类实现:

            protected V create(K key) {
                return null;
            }
        

        最后的 entryRemoved 方法的作用是,通过调用 remove 移除或通过调用 put 替换时,将一个值被移除以腾出空间,将调用此方法。 默认实现什么也不做。

        protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
        

        方法中的两个参数的含义:

        • evicted – 如果条目被删除以腾出空间,则为 true,如果删除是由 put 或 remove 引起的,则为 false。
        • newValue – 键的新值(如果存在)。 如果非 null,则此移除是由 put 或 get 引起的。 否则,它是由驱逐或移除引起的。

        get 方法中通过操作 LinkedHashMap ,调用 LinkedHashMap 的 get 和 put 方法,会在 LinkedHashMap 内部完成排序逻辑。

        put

        LRUCache 的 put 方法用来更新数据:

            public final V put(K key, V value) {
                if (key == null || value == null) {
                  android  throw new NullPointerException("key == null || value == null");
                }
                V previous;
                synchronized (this) {
                    putCount++;
                    size += safeSizeOf(key, value); // 当前容量 + 1
                    previous = map.put(key, value); // 取出先前的值
                    if (previous != null) {
                        size -= safeSizeOf(key, previous); // map 中已存在 key 的情况下,保证 size 不变
                    }
                }
        				// 先前存在元素,执行元素移除后的自定义操作
                if (previous != null) {
                    entryRemoved(false, key, previous, value);
                }
        				// 容量处理
                trimToSize(maxSize);
                return previous;
            }
        

        这里也有一个问题,如果 map 中已存在 key ,仅是更新数据,这里没有涉及到排序的问题。

        为什么这么说呢?是因为 LinkedHashMap 并没有定义 put 方法,需要查看 HashMap 中的 put 方法:

            public V put(K key, V value) {
                return putVal(hash(key), key, value, false, true);
            }
        

        HashMap 中的 put 方法中真正逻辑是 putVal 方法,在 putVal 方法中调用了访问元素后的处理方法 afterNodeAccess 方法,而这个方法的

            final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
                    // ...
        						if (e != null) { // existing mapping for key
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e); // 【*】
                        return oldValue;
                    }
                    // ...
        		}
        

        afterNodeAccess 方法在 HashMap 中是空实现,通过备注可以理解,这些方法专门为 LinkedHashMap 预留的:

            // Callbacks to allow LinkedHashMap post-actions
            void afterNodeAccess(Node<K,V> p) { }
            void afterNodeInsertion(boolean evict) { }
            void afterNodeRemoval(Node<K,V> p) { }
        

        而 afterNodeAccess 在 LinkedHashMap 中的实现,和 LinkedHashMap 的 get 方法中调用的排序方法是同一个。所以 put 方法也会对元素进行排序。

        remove

        与 put 方法相同,remove 方法也是来自于父类 HashMap:

            public V remove(Object key) {
                Node<K,V> e;
                return (e = removeNode(hash(key), key, null, false, true)) == null ?
                    null : e.value;
            }
        

        removeNode 中进行移除操作,并调用了 afterNodeRemoval 方法:

            final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
                Node<K,V>[] tab; Node<K,V> p; int n, index;
                if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
                    Node<K,jsV> node = null, e; K k; V v;
                  	// ...
                    if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
                        if (node instanceof TreeNode)
                            ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                        else if (node == p)
                            tab[index] = node.next;
                        else
                            p.next = node.next;
                        ++modCount;
                        --size;
                        afterNodeRemoval(node); // 【*】
                        return node;
                    }
                }
                return null;
            }
        

        afterNodeRemoval 方法的实现在 LinkedHashMap 中,操作双向链表删除当前元素:

            void afterNodeRemoval(Node<K,V> e) { // unlink
                LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
                p.before = p.after = null;
                if (b == null)
                    head = a;
                else
                    b.after = a;
                if (a == null)
                    tail = b;
                else
                    a.before = b;
            }
        

        容量计算

        在使用 LruCache 类时,可以自行定义最大缓存容量,并自行计算对象的缓存。例如,初始化一个最大容量为 4M ,用来保存 Bitmap 的 LruCache :

        int cacheSize = 4 * 1024 * 1024; // 4MiB   
        LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {       
          	protected int sizeOf(String key, Bitmap value) {           
              	return value.getByteCount();       
            }   
        }
        

        最大容量为 cacheSize ,对于每一个新对象,通过 sizeOf 方法来计算这个对象的大小。

        总结

        • android.util.LruCache 类是 Android SDK 中的一个 LRU 缓存实现,它的内部数据结构采用的是 LinkedHashMap 。
        • LinkedHashMap 实现了 HashMap ,并且维护了一个双端链表来处理元素的排序。
        • LinkedHashMap 通过构造方法中的参数 accessOrder = true ,来启用访问顺序记录逻辑。
        • 核心的排序逻辑在 afterNodeAccess 方法中,当超过容量限制时,会删除链表中 head 节点。每次访问数据,会将节点移动到队尾。
        • 可以创建android.util.LruCache 时,通过 cacheSize 参数配合重写 sizeOf 方法实现自定义容量计算逻辑的 LruCache 。

        常见算法题

        最后再来聊一下字节面试频率比较高的一道算法题,实现一个 LruCache ,通过上面的了解我们也知道最优解就是通过一个 哈希表 + 一个 双向链表 来实现。

        class LruCache(private val capacity: Int) {
            data class DLinkedNode(
                var key: Int? = null,
                var value: Int? = null,
                var prev: DLinkedNode? = null,
                var next: DLinkedNode? = null
            )
            private val cache = HashMap<Int, DLinkedNode>()
            private var size = 0
            private var head = DLinkedNode()
            private var tail = DLinkedNode()
            fun get(key: Int): Int {
                val node = cache[key] ?: return -1
                // 如果 key 存在,先通过哈希表定位,再移到头部
                moveToHead(node)
                return node.value ?: -1
            }
            fun put(key: Int, value: Int) {
                val node = cache[key]
                if (node == null) {
                    // 如果 key 不存在,创建一个新的节点
                    val newNode = DLinkedNode(key, value)
                    // 添加进哈希表
                    cache[key] = newNode
                    // 添加至双向链表的头部
                    addToHead(newNode)
                    ++size;
                    if (size > capacity) {
                        // 如果超出容量,删除双向链表的尾部节点
                        val tail = removeTail()
                        // 删除哈希表中对应的项
                        cache.remove(tail?.key)
                        --size;
                    }
                }
                else {
                    // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
                    node.value = value;
                    moveToHead(node);
                }
            }
            private fun addToHead(node: DLinkedNode?) {
                node?.prev = head
                node?.next = head.next
                head.next?.prev = node
                head.next = node
            }
            private fun removeNode(node: DLinkedNode?) {
                node?.prev?.next = node?.next
                node?.next?.prev = node?.prev
            }
            private fun moveToHead(node: DLinkedNode?) {
                removeNode(node)
                addToHead(node)
            }
            private fun removeTail(): DLinkedNode? {
                val res = tail.prev 
                removeNode(res)
                return res
            }
        }
        

        时间复杂度:对于 put 和 get 都是 O(1) 。

        空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity + 1 个元素。

        另一种利用 LinkedHashMap 的解法就比较简单了:

        class LruCacheByLinkedHashMap(val capacity: Int): LinkedHashMap<Int, Int>(capacity, 0.75f, true) {
            override fun get(key: Int): Int {
                return getOrDefault(key, -1)
            }
            override fun put(key: Int, value: Int): Int? {
                return super.put(key, value)
            }
            override fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {
                return size > capacity
            }
        }
        

        只需要继承 LinkedHashMap ,并设置好初始容量、启用访问顺序排序,然后实现 removeEldestEntry ,这个方法在 put 调用时,会检查删除最老的元素,返回值为判断条件的结果。

        以上就是Java面试LruCache 和 LinkedHashMap及算法实现的详细内容,更多关于java面试LruCache LinkedHashMap算法的资料请关注我们其它相关文章!

        0

        上一篇:

        下一篇:

        精彩评论

        暂无评论...
        验证码 换一张
        取 消

        最新开发

        开发排行榜