資訊專欄INFORMATION COLUMN
摘要：雙向鏈表雙向鏈表作為在日常開發(fā)中最常用的數(shù)據(jù)結(jié)構(gòu)之一，應(yīng)用十分廣泛，在諸多著名開源項(xiàng)目中如的結(jié)構(gòu)，的中均是核心實(shí)現(xiàn)。
雙向鏈表
雙向鏈表作為在日常開發(fā)中最常用的數(shù)據(jù)結(jié)構(gòu)之一，應(yīng)用十分廣泛，在諸多著名開源項(xiàng)目中如redis的list結(jié)構(gòu)， groupcache的lru中均是核心實(shí)現(xiàn)。在設(shè)計(jì)此類數(shù)據(jù)集合的時(shí)候，外面看上去鏈表似乎與數(shù)組相似，但鏈表是一個(gè)非連續(xù)性內(nèi)存的存儲方案，提供了高效的節(jié)點(diǎn)重排能力與順序訪問方式，對比與操作數(shù)組，只需知道給定項(xiàng)的地址和位置的鏈接就能在內(nèi)存中找到它，并且可以通過增減節(jié)點(diǎn)的方式來靈活的調(diào)整長度。反而數(shù)組，比如插入一個(gè)新的元素，那么該位置后的元素都要往后移動一位。
標(biāo)準(zhǔn)的雙向鏈表實(shí)現(xiàn)redis 中的雙向鏈表
golang 中的雙向鏈表
其結(jié)構(gòu)如圖
在雙向鏈表中頭結(jié)點(diǎn)的前指針為空，尾節(jié)點(diǎn)的后指針為空, 對頭尾的操作十分簡單, 插入頭節(jié)點(diǎn)只需要將新節(jié)點(diǎn)的next設(shè)置為當(dāng)前鏈表的頭節(jié)點(diǎn)， 當(dāng)前列表的prev為新節(jié)點(diǎn)， 并與之交換位置即可， 插入尾部反之
在節(jié)點(diǎn)中間按游標(biāo)插入的話則需要考慮正向反向的問題, 下圖當(dāng)i 為正數(shù)表示正向插入，負(fù)數(shù)反向插入, 其實(shí)不管是只操作頭尾節(jié)點(diǎn)還是中間節(jié)點(diǎn)，其核心就是交換當(dāng)前節(jié)點(diǎn)與前一個(gè)和后一個(gè)節(jié)點(diǎn)之間的鏈接
將某個(gè)節(jié)點(diǎn)移動至頭部跟插入頭部動作多了一步交換當(dāng)前節(jié)點(diǎn)前后節(jié)點(diǎn)鏈接的操作
而刪除某個(gè)節(jié)點(diǎn)就只需要將其前后節(jié)點(diǎn)的鏈接互相相連，使其不被引用，它會自動被回收掉
LRU全稱Least Recently Used, 直譯為“最近最少使用”, 其對于內(nèi)存管理方面十分有效，比如容量只有十的一個(gè)集合，當(dāng)寫入第十一條數(shù)據(jù)時(shí)候，最少使用的那個(gè)數(shù)據(jù)將會被淘汰，故此方法很適用于對有給定容量限制的熱數(shù)據(jù)做緩存管理
在開源項(xiàng)目groupcache中, 緩存的過期沒有設(shè)置過期時(shí)間而是依賴于LRU淘汰機(jī)制，那么其用來實(shí)現(xiàn)LRU的核心就是一個(gè)雙向鏈表, 為了保證效率， 緩存數(shù)據(jù)被保存在一個(gè)Map中使每次緩存的存取時(shí)間復(fù)雜度為O(1), 而雙向鏈表則負(fù)責(zé)管理內(nèi)存的容量以及實(shí)現(xiàn)淘汰機(jī)制
在寫入新的緩存項(xiàng)時(shí)，會把其插入至鏈表的頭部， 并且判斷如果當(dāng)前鏈表長度大于給定長度時(shí)，刪除鏈表尾部的元素，同時(shí)刪除其在map中的key
每當(dāng)有訪問命中緩存時(shí), 會將命中的緩存移至鏈表頭部
上述插入和命中時(shí)將其放到鏈表頭部的策略，使得鏈表尾部的元素永遠(yuǎn)是使用得最少的那個(gè)緩存，故新緩存進(jìn)來時(shí)就將其淘汰。
本文說明了雙向鏈表的實(shí)現(xiàn)以及其實(shí)際應(yīng)用，但是在真實(shí)應(yīng)用中，golang 的雙向鏈表是非線程安全的，如遇到并發(fā)情況操作鏈表則會因?yàn)檎也坏降刂范鴪?bào)錯， 所以groupcache項(xiàng)目在從LRU策略中獲取緩存的時(shí)候，在外部包了一個(gè)帶讀寫鎖的結(jié)構(gòu)體來保證其并發(fā)安全
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/62056.html
摘要：雙向鏈表用于管理緩存數(shù)據(jù)結(jié)點(diǎn)的順序，新增數(shù)據(jù)和緩存命中最近被訪問的數(shù)據(jù)被放置在結(jié)點(diǎn)，尾部的結(jié)點(diǎn)根據(jù)內(nèi)存大小進(jìn)行淘汰。 了解 LRU 之前，我們應(yīng)該了解一下緩存，大家都知道計(jì)算機(jī)具有緩存內(nèi)存，可以臨時(shí)存儲最常用的數(shù)據(jù)，當(dāng)緩存數(shù)據(jù)超過一定大小時(shí)，系統(tǒng)會進(jìn)行回收，以便釋放出空間來緩存新的數(shù)據(jù)，但從系統(tǒng)中檢索數(shù)據(jù)的成本...
摘要：散列表其實(shí)是基于數(shù)組實(shí)現(xiàn)的，可以說，沒有數(shù)組就沒有散列表。根據(jù)下圖你更能理解散列表哈希函數(shù)結(jié)合上面的理解，你應(yīng)該可以想到，其實(shí)散列表的關(guān)鍵就在于哈希函數(shù)的實(shí)現(xiàn)。 1. 什么是散列表？ 散列表（Hash Table）又叫做哈希表，是一種很常用的數(shù)據(jù)結(jié)構(gòu)。散列表其實(shí)是基于數(shù)組實(shí)現(xiàn)的，可以說，沒有數(shù)組就沒有散列表。先來舉一個(gè)簡單的例子，來認(rèn)識一下什么是散列表。 假如在學(xué)校的運(yùn)動會上，每個(gè)運(yùn)動...
摘要：劍指緩存實(shí)現(xiàn)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處解題思路緩存兩種功能獲取的對應(yīng)，不存在返回版本版本設(shè)置緩存已滿，刪除最近最久未被使用的節(jié)點(diǎn)，添加新節(jié)點(diǎn)進(jìn)緩存緩存未滿，節(jié)點(diǎn)存在，修改節(jié)點(diǎn)不存在，添加新節(jié)點(diǎn)進(jìn)緩存解題思路由于緩存插入和刪除 劍指offer/LeetCode146/LintCode134_LRU緩存實(shí)現(xiàn) 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處[1] https://s...
閱讀 3015·2021-11-24 10:22
閱讀 3061·2021-11-23 10:10
閱讀 1370·2021-09-28 09:35
閱讀 1763·2019-08-29 13:16
閱讀 1405·2019-08-26 13:29
閱讀 2801·2019-08-26 10:27
閱讀 692·2019-08-26 10:09
閱讀 1456·2019-08-23 18:05
