java面試LruCache?和?LinkedHashMap及算法實(shí)現(xiàn)

更新時(shí)間：2023年02月15日 14:16:13 作者：自動(dòng)化BUG制造器

這篇文章主要為大家介紹了java面試LruCache?和?LinkedHashMap及算法實(shí)現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

LruCache

保存對(duì)有限數(shù)量值的強(qiáng)引用的緩存。每次訪問一個(gè)值時(shí)，它都會(huì)移動(dòng)到隊(duì)列的頭部。當(dāng)一個(gè)值被添加到一個(gè)完整的緩存中時(shí)，該隊(duì)列末尾的值將被逐出并且可能有資格進(jìn)行垃圾回收。

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

LRUCache 是具有一定數(shù)量限制的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)采用 LRU 算法，維護(hù)一定數(shù)量的緩存數(shù)據(jù)。如果數(shù)據(jù)結(jié)構(gòu)已經(jīng)達(dá)到了最大數(shù)量限制時(shí)，有新的數(shù)據(jù)插入，則就需要根據(jù) LRU 算法，刪除最久未使用的數(shù)據(jù)。

根據(jù)它的功能描述，對(duì)數(shù)據(jù)結(jié)構(gòu)的選擇就有了偏向性：

定義中提到了隊(duì)列，實(shí)現(xiàn)隊(duì)列的兩種底層數(shù)據(jù)結(jié)構(gòu)是鏈表和數(shù)組。
根據(jù)每次刪除最后一個(gè)元素的特性，可以優(yōu)先考慮鏈表結(jié)構(gòu)。
如果集合中已存在要添加的元素，優(yōu)先將其移動(dòng)到隊(duì)頭，優(yōu)先考慮鏈表結(jié)構(gòu)，因?yàn)閿?shù)組的移動(dòng)開銷更大。
每次添加新元素都要查詢一遍集合中是否存在該元素，鏈表結(jié)構(gòu)相比數(shù)組的查詢時(shí)間復(fù)雜度更高，所以優(yōu)先考慮數(shù)組和用來輔助查詢時(shí)間復(fù)雜度低的 Map 。

綜合前兩點(diǎn)考慮，LinkedList 配合 HashMap 是一個(gè)不錯(cuò)的選擇，前者不光可以是鏈表結(jié)構(gòu)、還實(shí)現(xiàn)了 Deque ，也可以視為隊(duì)列、棧結(jié)構(gòu)，后者提供了更低時(shí)間復(fù)雜度的檢索。

而在 JDK 中，提供了 LinkedHashMap 用來實(shí)現(xiàn) LRU 緩存的功能。

LinkedHashMap

LinkedHashMap 繼承自 HashMap ，并實(shí)現(xiàn)了 Map 接口。構(gòu)造方法包含了一個(gè) accessOrder 參數(shù)，該參數(shù)會(huì)將元素按照訪問順序進(jìn)行排序，非常適合構(gòu)建 LRUCache 。

LinkedHashMap 與 HashMap 不同之處在于維護(hù)了一個(gè)**雙向鏈表，該列表串聯(lián)起了所有元素。**這個(gè)鏈表定義了迭代順序，通常是鍵插入映射的順序（插入順序）。

請(qǐng)注意，如果將鍵重新插入到 Map 中，則插入順序不會(huì)受到影響。（如果在調(diào)用 m.containsKey(k) 時(shí)調(diào)用 m.put(k, v) 將在調(diào)用之前立即返回 true，則將鍵 k 重新插入到映射 m 中。）

內(nèi)部的雙向鏈表結(jié)構(gòu)：

    /**
     * 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)，會(huì)更新鏈表中的元素順序：

    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 方法中，將最新訪問的元素移動(dòng)到了鏈表尾部：

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 雙向鏈表尾部節(jié)點(diǎn) last
    if (accessOrder && (last = tail) != e) {
        // 訪問的節(jié)點(diǎn)標(biāo)記為 p ，p 的前后節(jié)點(diǎn)保存到 b 、a 中
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 訪問節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)設(shè)置為 null ，因?yàn)槭亲詈笠粋€(gè)節(jié)點(diǎn)，所以后續(xù)節(jié)點(diǎn)為 null
        p.after = null; 
        // 處理刪除 e 節(jié)點(diǎn)的邏輯
        if (b == null)
             // p 的前面不存在節(jié)點(diǎn)，頭節(jié)點(diǎn)設(shè)置為 a 
            head = a;
        else 
            // p 的前面存在節(jié)點(diǎn)，將 p 的后續(xù)節(jié)點(diǎn)設(shè)置為 p 前一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)  b -> p -> a 更新為 b -> a （刪除 p）
            b.after = a;
        if (a != null)
            // p 存在后續(xù)節(jié)點(diǎn) a , 將 a 的 before 指針更新為 b
            a.before = b;
        else
            // p 不存在后續(xù)節(jié)點(diǎn) a , last 指針更新為 b
            last = b;
        // 處理尾部節(jié)點(diǎn)的邏輯
        if (last == null)
            // last 指針為空，更新頭節(jié)點(diǎn)
            head = p;
        else {
            // last 指針不為空，更新鏈表順序?yàn)?last 
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

所以這是一種十分適合 LRUCache 的數(shù)據(jù)結(jié)構(gòu)，Android 中的 LRUCache 類就是通過 LinkedHashMap 來實(shí)現(xiàn)的。

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

Android 的 LruCache 源碼分析

LruCache 是 Android SDK 中提供一個(gè)類，來自于 android.util 。

LruCache 中有兩個(gè)核心方法，get 和 put ，再加上容量變化處理方法，構(gòu)成了完善的 LRU 機(jī)制。它的內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是 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

當(dāng)重新設(shè)置 LruCache 的容量時(shí)，可以通過 resize 分發(fā)重新設(shè)置容量：

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

容量處理伴隨著刪除最久未使用的元素：

    // 刪除最老的元素，直到剩余元素的總數(shù)等于或低于請(qǐng)求的大小。
    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);
        }
    }

在這個(gè)方法中，通過 map.eldest() 獲取到了存活最久的元素，它的實(shí)現(xiàn)是：

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

最后的 entryRemoved 方法的作用是，通過調(diào)用 remove 移除或通過調(diào)用 put 替換時(shí)，將一個(gè)值被移除以騰出空間，將調(diào)用此方法。默認(rèn)實(shí)現(xiàn)什么也不做。

get

get 方法根據(jù) key 檢索 LinkedHashMap 中是否存在對(duì)應(yīng)的元素，或者是否可以根據(jù) create 方法創(chuàng)建元素。如果存在或可根據(jù) create 方法創(chuàng)建，則將這個(gè)元素移動(dòng)到隊(duì)列頭部，否則返回 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++; 
        }
				// 緩存中不存在對(duì)應(yīng) key 的元素，創(chuàng)建一個(gè)新元素
        V createdValue = create(key); 
        if (createdValue == null) { // 未緩存且無法創(chuàng)建，返回 null
            return null;
        }
				// 創(chuàng)建成功，存入到 map ，如果 key 已存在對(duì)應(yīng)值，優(yōu)先更新為之前的值
        synchronized (this) {
            createCount++;	
            mapValue = map.put(key, createdValue); // 存入新的元素，并獲取前一個(gè) key 對(duì)應(yīng)的值 mapValue。
            if (mapValue != null) {
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue); // 新元素導(dǎo)致當(dāng)前容量 + 1
            }
        }
        if (mapValue != null) { // key 對(duì)應(yīng)的元素已存在
          	// 當(dāng)一個(gè)值被逐出以騰出空間、通過調(diào)用 remove 移除或通過調(diào)用 put 替換時(shí)，將調(diào)用此方法。 默認(rèn)實(shí)現(xiàn)什么也不做。
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue; 
        } else { // key 對(duì)應(yīng)的元素不存在
            trimToSize(maxSize); // 擴(kuò)容
            return createdValue; //返回最新插入的元素
        }
    }

這里的 create 方法默認(rèn)返回 null , 供子類實(shí)現(xiàn):

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

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

方法中的兩個(gè)參數(shù)的含義：

evicted – 如果條目被刪除以騰出空間，則為 true，如果刪除是由 put 或 remove 引起的，則為 false。
newValue – 鍵的新值（如果存在）。如果非 null，則此移除是由 put 或 get 引起的。否則，它是由驅(qū)逐或移除引起的。

get 方法中通過操作 LinkedHashMap ，調(diào)用 LinkedHashMap 的 get 和 put 方法，會(huì)在 LinkedHashMap 內(nèi)部完成排序邏輯。

put

LRUCache 的 put 方法用來更新數(shù)據(jù)：

    public final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }
        V previous;
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value); // 當(dāng)前容量 + 1
            previous = map.put(key, value); // 取出先前的值
            if (previous != null) {
                size -= safeSizeOf(key, previous); // map 中已存在 key 的情況下，保證 size 不變
            }
        }
				// 先前存在元素，執(zhí)行元素移除后的自定義操作
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
				// 容量處理
        trimToSize(maxSize);
        return previous;
    }

這里也有一個(gè)問題，如果 map 中已存在 key ，僅是更新數(shù)據(jù)，這里沒有涉及到排序的問題。

為什么這么說呢？是因?yàn)?LinkedHashMap 并沒有定義 put 方法，需要查看 HashMap 中的 put 方法：

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

HashMap 中的 put 方法中真正邏輯是 putVal 方法，在 putVal 方法中調(diào)用了訪問元素后的處理方法 afterNodeAccess 方法，而這個(gè)方法的

    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 中是空實(shí)現(xiàn)，通過備注可以理解，這些方法專門為 LinkedHashMap 預(yù)留的：

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

而 afterNodeAccess 在 LinkedHashMap 中的實(shí)現(xiàn)，和 LinkedHashMap 的 get 方法中調(diào)用的排序方法是同一個(gè)。所以 put 方法也會(huì)對(duì)元素進(jìn)行排序。

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 中進(jìn)行移除操作，并調(diào)用了 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,V> 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 方法的實(shí)現(xiàn)在 LinkedHashMap 中，操作雙向鏈表刪除當(dāng)前元素：

    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;
    }

容量計(jì)算

在使用 LruCache 類時(shí)，可以自行定義最大緩存容量，并自行計(jì)算對(duì)象的緩存。例如，初始化一個(gè)最大容量為 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 ，對(duì)于每一個(gè)新對(duì)象，通過 sizeOf 方法來計(jì)算這個(gè)對(duì)象的大小。

總結(jié)

android.util.LruCache 類是 Android SDK 中的一個(gè) LRU 緩存實(shí)現(xiàn)，它的內(nèi)部數(shù)據(jù)結(jié)構(gòu)采用的是 LinkedHashMap 。
LinkedHashMap 實(shí)現(xiàn)了 HashMap ，并且維護(hù)了一個(gè)雙端鏈表來處理元素的排序。
LinkedHashMap 通過構(gòu)造方法中的參數(shù) accessOrder = true ，來啟用訪問順序記錄邏輯。
核心的排序邏輯在 afterNodeAccess 方法中，當(dāng)超過容量限制時(shí)，會(huì)刪除鏈表中 head 節(jié)點(diǎn)。每次訪問數(shù)據(jù)，會(huì)將節(jié)點(diǎn)移動(dòng)到隊(duì)尾。
可以創(chuàng)建android.util.LruCache 時(shí)，通過 cacheSize 參數(shù)配合重寫 sizeOf 方法實(shí)現(xiàn)自定義容量計(jì)算邏輯的 LruCache 。

常見算法題

最后再來聊一下字節(jié)面試頻率比較高的一道算法題，實(shí)現(xiàn)一個(gè) LruCache ，通過上面的了解我們也知道最優(yōu)解就是通過一個(gè) 哈希表 + 一個(gè) 雙向鏈表來實(shí)現(xiàn)。

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 不存在，創(chuàng)建一個(gè)新的節(jié)點(diǎn)
            val newNode = DLinkedNode(key, value)
            // 添加進(jìn)哈希表
            cache[key] = newNode
            // 添加至雙向鏈表的頭部
            addToHead(newNode)
            ++size;
            if (size > capacity) {
                // 如果超出容量，刪除雙向鏈表的尾部節(jié)點(diǎn)
                val tail = removeTail()
                // 刪除哈希表中對(duì)應(yīng)的項(xiàng)
                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
    }
}

時(shí)間復(fù)雜度：對(duì)于 put 和 get 都是 O(1) 。

空間復(fù)雜度：O(capacity)，因?yàn)楣１砗碗p向鏈表最多存儲(chǔ) capacity + 1 個(gè)元素。

另一種利用 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 ，并設(shè)置好初始容量、啟用訪問順序排序，然后實(shí)現(xiàn) removeEldestEntry ，這個(gè)方法在 put 調(diào)用時(shí)，會(huì)檢查刪除最老的元素，返回值為判斷條件的結(jié)果。

以上就是java面試LruCache 和 LinkedHashMap及算法實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于java面試LruCache LinkedHashMap算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: