組件設計系列：實作一個LRU快取類
- 1、簡介
- 2、實作LRU快取
- 3、測驗
1、簡介
在我負責的專案中，有很多公共的組件，實作的思路很值得我們學習，比如LRU快取，這種策略在作業系統中也有應用，本次是基于C++實作的一個支持泛型的LRU快取工具類，實作思路供大家參考，
LRU演算法（Least Recently Used,最近最少使用），是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰，
2、實作LRU快取
首先看一下LRUCache類的定義如下：
思路主要是借助map和list來實作一個LRU快取的實作，其中map用于快速查找，list用于順序存盤，map的key為資料的key，Value為list的元素指標，List中也存放具體的元素key-Value值，其中分別實作的函式主要包括有參建構式，解構式，put和get方法，以及回傳整個LRU快取的資料get_list方法，
先看看建構式和解構式的實作，其中建構式為有引數構造，引數cap代表了LRU快取的容量，當存放的資料多于cap，則會剔除最老的資料，
接下來看看存放資料的put方法，實作原始碼如下，
put方法存放資料的時候，首先查找一下是否存在該Key，如果存在則先洗掉該元素，然后再重新加入list中頭部，這樣當前元素就是最熱的資料了，如果不存在該key-Value，首先存放新的key-Value到list頭部，然后需要看看LRU中是否滿了，如果滿了則需要釋放list最后一個資料，比如存放第一個資料，鍵值對為《 2,“DOG”》時候，當再次放入一個新的資料，《3,“CAT”》的時候，LRU快取是這樣的，
我們來看看get方法是如何獲取元素的，原始碼如下，
get方法的思路比較簡單，就是先在map中查找是否存在當前Key，如果不存在，則直接回傳，如果存在，則需要更新當前資料的熱度，也就是需要將當前元素移動到list頭部位置，這里還是先從list中洗掉該Key-Value，然后再存放到list頭部即可，
3、測驗
最后來看一下測驗案例，測驗案例比較簡單，
總的來說，LRU還是比較容易實作的，在面試中也會遇到，雖然比較簡單，但是也需要提高動手能力，保證面試的時候能夠一次性寫出來，不出錯，
喜歡本文的朋友，也可以關注本人微信公眾號“碼農的修煉之道”，更多精彩文章等你來閱讀！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/212181.html
標籤：其他