什麼是LRU算法
LRU是Least Recently Used的縮寫，即最近最少使用。最早接觸這個算法是在大學學習計算機操作系統課程中，它是操作系統中的一種頁面置換算法，是為虛擬頁式存儲管理服務的。它是以以最近的過去作為不久將來的近似，把過去最長一段時間裡不曾被使用的頁面置換掉。
LRU算法實現簡單，當存在熱點數據時，效率很好，但偶發性的、週期性的批量操作會導致LRU命中率急劇下降，緩存汙染情況比較嚴重。
算法實現
最常見的實現是使用一個鏈表保存緩存數據。
C++版本實現
採用List和Map的兩種數據結構，Map可以解決查詢效率，List可以解決插入刪除的效率。
分享到:
閱讀更多 半杯茶的小酒杯 的文章
