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