算法詳解

LRU 緩存機(jī)制可以通過哈希表輔以雙向鏈表實(shí)現(xiàn)，我們用一個(gè)哈希表和一個(gè)雙向鏈表維護(hù)所有在緩存中的鍵值對(duì)。

雙向鏈表按照被使用的順序存儲(chǔ)了這些鍵值對(duì)，靠近頭部的鍵值對(duì)是最近使用的，而靠近尾部的鍵值對(duì)是最久未使用的。

哈希表即為普通的哈希映射(HashMap)，通過緩存數(shù)據(jù)的鍵映射到其在雙向鏈表中的位置。

這樣以來，我們首先使用哈希表進(jìn)行定位，找出緩存項(xiàng)在雙向鏈表中的位置，隨后將其移動(dòng)到雙向鏈表的頭部，即可在 O(1) 的時(shí)間內(nèi)完成 get 或者 put 操作。具體的方法如下：

對(duì)于 get 操作，首先判斷 key 是否存在：

如果 key 不存在，則返回 ?1；

如果 key 存在，則 key 對(duì)應(yīng)的節(jié)點(diǎn)是最近被使用的節(jié)點(diǎn)。通過哈希表定位到該節(jié)點(diǎn)在雙向鏈表中的位置，并將其移動(dòng)到雙向鏈表的頭部，最后返回該節(jié)點(diǎn)的值。

對(duì)于 put 操作，首先判斷 key 是否存在：

如果 key 不存在，使用 key 和 value 創(chuàng)建一個(gè)新的節(jié)點(diǎn)，在雙向鏈表的頭部添加該節(jié)點(diǎn)，并將 key

總結(jié)

以上是生活随笔為你收集整理的LRU 缓存机制实现：哈希表 + 双向链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。