java面試LruCache?和?LinkedHashMap及算法實現(xiàn)
LruCache
保存對有限數(shù)量值的強(qiáng)引用的緩存。 每次訪問一個值時，它都會移動到隊列的頭部。 當(dāng)一個值被添加到一個完整的緩存中時，該隊列末尾的值將被逐出并且可能有資格進(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ù)據(jù)插入，則就需要根據(jù) LRU 算法，刪除最久未使用的數(shù)據(jù)。
根據(jù)它的功能描述，對數(shù)據(jù)結(jié)構(gòu)的選擇就有了偏向性：
- 定義中提到了隊列，實現(xiàn)隊列的兩種底層數(shù)據(jù)結(jié)構(gòu)是鏈表和數(shù)組。
- 根據(jù)每次刪除最后一個元素的特性，可以優(yōu)先考慮鏈表結(jié)構(gòu)。
- 如果集合中已存在要添加的元素，優(yōu)先將其移動到隊頭，優(yōu)先考慮鏈表結(jié)構(gòu)，因為數(shù)組的移動開銷更大。
- 每次添加新元素都要查詢一遍集合中是否存在該元素，鏈表結(jié)構(gòu)相比數(shù)組的查詢時間復(fù)雜度更高，所以優(yōu)先考慮數(shù)組和用來輔助查詢時間復(fù)雜度低的 Map 。
綜合前兩點考慮，LinkedList 配合 HashMap 是一個不錯的選擇，前者不光可以是鏈表結(jié)構(gòu)、還實現(xiàn)了 Deque ，也可以視為隊列、棧結(jié)構(gòu)， 后者提供了更低時間復(fù)雜度的檢索。
而在 JDK 中，提供了 LinkedHashMap 用來實現(xiàn) LRU 緩存的功能。
LinkedHashMap
LinkedHashMap 繼承自 HashMap ，并實現(xiàn)了 Map 接口。構(gòu)造方法包含了一個 accessOrder 參數(shù)，該參數(shù)會將元素按照訪問順序進(jìn)行排序，非常適合構(gòu)建 LRUCache 。
LinkedHashMap 與 HashMap 不同之處在于維護(hù)了一個**雙向鏈表，該列表串聯(lián)起了所有元素。**這個鏈表定義了迭代順序，通常是鍵插入映射的順序（插入順序）。
請注意，如果將鍵重新插入到 Map 中，則插入順序不會受到影響。 （如果在調(diào)用 m.containsKey(k) 時調(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)，會更新鏈表中的元素順序：
public V get(Object key) {
Node<K,V> 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;
// 雙向鏈表尾部節(jié)點 last
if (accessOrder && (last = tail) != e) {
// 訪問的節(jié)點標(biāo)記為 p ，p 的前后節(jié)點保存到 b 、a 中
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 訪問節(jié)點的后續(xù)節(jié)點設(shè)置為 null ，因為是最后一個節(jié)點，所以后續(xù)節(jié)點為 null
p.after = null;
// 處理刪除 e 節(jié)點的邏輯
if (b == null)
// p 的前面不存在節(jié)點，頭節(jié)點設(shè)置為 a
head = a;
else
// p 的前面存在節(jié)點，將 p 的后續(xù)節(jié)點設(shè)置為 p 前一個節(jié)點的下一個節(jié)點 b -> p -> a 更新為 b -> a （刪除 p）
b.after = a;
if (a != null)
// p 存在后續(xù)節(jié)點 a , 將 a 的 before 指針更新為 b
a.before = b;
else
// p 不存在后續(xù)節(jié)點 a , last 指針更新為 b
last = b;
// 處理尾部節(jié)點的邏輯
if (last == null)
// last 指針為空，更新頭節(jié)點
head = p;
else {
// last 指針不為空，更新鏈表順序為 last
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
所以這是一種十分適合 LRUCache 的數(shù)據(jù)結(jié)構(gòu)，Android 中的 LRUCache 類就是通過 LinkedHashMap 來實現(xiàn)的。
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;
//...
}
Android 的 LruCache 源碼分析
LruCache 是 Android SDK 中提供一個類，來自于 android.util 。
LruCache 中有兩個核心方法，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 的容量時，可以通過 resize 分發(fā)重新設(shè)置容量：
public void resize(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
synchronized (this) {
this.maxSize = maxSize;
}
trimToSize(maxSize);
}
容量處理伴隨著刪除最久未使用的元素：
// 刪除最老的元素，直到剩余元素的總數(shù)等于或低于請求的大小。
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() 獲取到了存活最久的元素，它的實現(xiàn)是：
// in LinkedHashMap
public Map.Entry<K, V> eldest() {
return head;
}
最后的 entryRemoved 方法的作用是，通過調(diào)用 remove 移除或通過調(diào)用 put 替換時，將一個值被移除以騰出空間，將調(diào)用此方法。 默認(rèn)實現(xiàn)什么也不做。
get
get 方法根據(jù) key 檢索 LinkedHashMap 中是否存在對應(yīng)的元素，或者是否可以根據(jù) create 方法創(chuàng)建元素。如果存在或可根據(jù) create 方法創(chuàng)建，則將這個元素移動到隊列頭部，否則返回 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++;
}
// 緩存中不存在對應(yīng) key 的元素，創(chuàng)建一個新元素
V createdValue = create(key);
if (createdValue == null) { // 未緩存且無法創(chuàng)建，返回 null
return null;
}
// 創(chuàng)建成功，存入到 map ，如果 key 已存在對應(yīng)值，優(yōu)先更新為之前的值
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue); // 存入新的元素，并獲取前一個 key 對應(yīng)的值 mapValue。
if (mapValue != null) {
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue); // 新元素導(dǎo)致當(dāng)前容量 + 1
}
}
if (mapValue != null) { // key 對應(yīng)的元素已存在
// 當(dāng)一個值被逐出以騰出空間、通過調(diào)用 remove 移除或通過調(diào)用 put 替換時，將調(diào)用此方法。 默認(rèn)實現(xiàn)什么也不做。
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else { // key 對應(yīng)的元素不存在
trimToSize(maxSize); // 擴(kuò)容
return createdValue; //返回最新插入的元素
}
}
這里的 create 方法默認(rèn)返回 null , 供子類實現(xiàn):
protected V create(K key) {
return null;
}
最后的 entryRemoved 方法的作用是，通過調(diào)用 remove 移除或通過調(diào)用 put 替換時，將一個值被移除以騰出空間，將調(diào)用此方法。 默認(rèn)實現(xiàn)什么也不做。
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
方法中的兩個參數(shù)的含義：
- evicted – 如果條目被刪除以騰出空間，則為 true，如果刪除是由 put 或 remove 引起的，則為 false。
- newValue – 鍵的新值（如果存在）。 如果非 null，則此移除是由 put 或 get 引起的。 否則，它是由驅(qū)逐或移除引起的。
get 方法中通過操作 LinkedHashMap ，調(diào)用 LinkedHashMap 的 get 和 put 方法，會在 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;
}
這里也有一個問題，如果 map 中已存在 key ，僅是更新數(shù)據(jù)，這里沒有涉及到排序的問題。
為什么這么說呢？是因為 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 方法，而這個方法的
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 中是空實現(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 中的實現(xiàn)，和 LinkedHashMap 的 get 方法中調(diào)用的排序方法是同一個。所以 put 方法也會對元素進(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 方法的實現(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;
}
容量計算
在使用 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 方法來計算這個對象的大小。
總結(jié)
android.util.LruCache類是 Android SDK 中的一個 LRU 緩存實現(xiàn)，它的內(nèi)部數(shù)據(jù)結(jié)構(gòu)采用的是 LinkedHashMap 。- LinkedHashMap 實現(xiàn)了 HashMap ，并且維護(hù)了一個雙端鏈表來處理元素的排序。
- LinkedHashMap 通過構(gòu)造方法中的參數(shù)
accessOrder = true，來啟用訪問順序記錄邏輯。 - 核心的排序邏輯在
afterNodeAccess方法中，當(dāng)超過容量限制時，會刪除鏈表中 head 節(jié)點。每次訪問數(shù)據(jù)，會將節(jié)點移動到隊尾。 - 可以創(chuàng)建
android.util.LruCache時，通過 cacheSize 參數(shù)配合重寫 sizeOf 方法實現(xiàn)自定義容量計算邏輯的 LruCache 。
常見算法題
最后再來聊一下字節(jié)面試頻率比較高的一道算法題，實現(xiàn)一個 LruCache ，通過上面的了解我們也知道最優(yōu)解就是通過一個 哈希表 + 一個 雙向鏈表 來實現(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)建一個新的節(jié)點
val newNode = DLinkedNode(key, value)
// 添加進(jìn)哈希表
cache[key] = newNode
// 添加至雙向鏈表的頭部
addToHead(newNode)
++size;
if (size > capacity) {
// 如果超出容量，刪除雙向鏈表的尾部節(jié)點
val tail = removeTail()
// 刪除哈希表中對應(yī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
}
}
時間復(fù)雜度：對于 put 和 get 都是 O(1) 。
空間復(fù)雜度：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 ，并設(shè)置好初始容量、啟用訪問順序排序，然后實現(xiàn) removeEldestEntry ，這個方法在 put 調(diào)用時，會檢查刪除最老的元素，返回值為判斷條件的結(jié)果。
以上就是java面試LruCache 和 LinkedHashMap及算法實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于java面試LruCache LinkedHashMap算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了java?oshi如何查看cpu信息，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-01-01
這篇文章主要介紹了JNDI,JTA和JMS的相關(guān)內(nèi)容，包括中文釋義，概念解釋等，需要的朋友可以了解下。2017-09-09
這篇文章主要介紹了java計算時間差的方法,涉及java針對時間的轉(zhuǎn)換與計算相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
本文主要介紹了使用eclipse打包Maven項目的實現(xiàn)步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-03-03
MyBatisPlus+SpringBoot實現(xiàn)樂觀鎖功能詳細(xì)流程
樂觀鎖是針對一些特定問題的解決方案,主要解決丟失更新問題,下面這篇文章主要給大家介紹了關(guān)于MyBatisPlus+SpringBoot實現(xiàn)樂觀鎖功能的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
RocketMQ生產(chǎn)者一個應(yīng)用不能發(fā)送多個NameServer消息解決
這篇文章主要為大家介紹了RocketMQ生產(chǎn)者一個應(yīng)用不能發(fā)送多個NameServer消息原因及解決方法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
Spingboot?JPA?CriteriaBuilder?如何獲取指定字段
這篇文章?主要介紹了Spingboot?JPA?CriteriaBuilder?如何獲取指定字段，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
java使用bitmap實現(xiàn)可回收自增id的示例
本文主要介紹了java使用bitmap實現(xiàn)可回收自增id的示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-10-10
RestTemplate發(fā)送form-data請求上傳rul資源文件及對象參數(shù)方式
這篇文章主要介紹了RestTemplate發(fā)送form-data請求上傳rul資源文件及對象參數(shù)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
為什么Spring和IDEA都不推薦使用 @Autowired 注解
本文主要介紹了為什么Spring和IDEA都不推薦使用 @Autowired 注解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04