當散列表遇上鏈表會擦除什麼火花？

• 2021 年 7 月 23 日
• 筆記
• LRU, 數據結構與演算法

      在數據結構中，散列表和鏈表經常會組合在一塊使用，如果你對java很熟悉，你會發現LinkedHashMap這樣一個常用的容器，也把散列表和鏈表組合起來使用。那散列表和鏈表是如何組合使用的，他們組合在一起能碰撞出什麼火花，請跟隨我的腳步，一起一探究竟。

     我們先思考這麼一個問題，如何使用鏈表來實現LRU快取呢？如果對LRU不熟，可以看這篇文章。頁面置換演算法你學會了嗎？

     我們可以維護一個有序的單鏈表，越靠近鏈表尾部的結點是越早訪問的。當有一個新的數據被訪問時，我們從鏈表頭開始順序遍歷。遍歷的結果有兩種情況。

1. 如果此數據之前就已經被快取在鏈表中，我們遍歷得到這個數據對應的結點，然後將其從這個位置移動到鏈表的頭部。

2. 如果此數據不在鏈表中，又會分為兩種情況。如果此時快取鏈表沒有滿，我們直接將該結點插入鏈表頭部。如果此時快取鏈表已經滿了，我們從鏈表尾部刪除一個結點，然後將新的數據結點插入到鏈表頭部。

      這樣我們就用鏈表實現了一個LRU快取，我們接下來分析一下快取訪問的時間複雜度。因為不管快取有沒有滿，我們都需要遍歷一遍鏈表，所以基於鏈表實現的LRU快取，快取訪問的時間複雜度是O(n)。

        那有沒有什麼方法可以減低時間複雜度呢？我們先來分析一下快取的常用操作。對於一個快取來說，主要涉及以下三種操作：

1. 往快取添加一個元素。

2. 從快取中刪除一個元素。

3. 在快取中查找一個元素。

      這三個操作都會涉及到查找的操作，如果單純的使用鏈表，時間複雜度只能是O(n)。大家都知道散列表的查找操作是O(1)，那我們能不能把散列表和鏈表結合起來使用，將快取的這三個常用操作的時間複雜度減低到O(1)呢？答案是肯定的，我們來看一下他們是如何組合在一起的。

       如圖所示，我們使用雙向鏈表來存儲數據，鏈表中的每個結點除了數據（data）、前驅指針（pre）、後繼指針（next）之外，還新增了一個特殊的欄位 hnext。這個hnext有什麼作用呢？因為我們的散列表是通過鏈表法解決散列衝突的，所以每個結點會在兩條鏈中。一個鏈是剛剛我們提到的雙向鏈表，另一個鏈是散列表中的拉鏈。前驅和後繼指針是為了將結點串在雙向鏈表中，hnext 指針是為了將結點串在散列表的拉鏈中。

      了解了這個散列表和雙向鏈表的組合存儲結構之後，我們再來看，前面講到的快取的三個操作，是如何做到時間複雜度是 O(1) 的？

       首先，我們來看如何查找一個數據。我們前面講過，散列表中查找數據的時間複雜度接近 O(1)，所以通過散列表，我們可以很快地在快取中找到一個數據。當找到數據之後，我們還需要將它移動到雙向鏈表的尾部。

       其次，我們來看如何刪除一個數據。我們需要找到數據所在的結點，然後將結點刪除。藉助散列表，我們可以在 O(1) 時間複雜度里找到要刪除的結點。因為我們的鏈表是雙向鏈表，雙向鏈表可以通過前驅指針 O(1) 時間複雜度獲取前驅結點，所以在雙向鏈表中，刪除結點只需要 O(1) 的時間複雜度。

      最後，我們來看如何添加一個數據。添加數據到快取稍微有點麻煩，我們需要先看這個數據是否已經在快取中。如果已經在其中，需要將其移動到雙向鏈表的頭部；如果不在其中，還要看快取有沒有滿。如果滿了，則將雙向鏈表尾部的結點刪除，然後再將數據放到鏈表的頭部；如果沒有滿，就直接將數據放到鏈表的頭部。這整個過程涉及的查找操作都可以通過散列表來完成。

       其他的操作，比如刪除頭結點、鏈表尾部插入數據等，都可以在 O(1) 的時間複雜度內完成。所以，這三個操作的時間複雜度都是 O(1)。至此，我們就通過散列表和雙向鏈表的組合使用，實現了一個高效的、支援 LRU 快取淘汰演算法的快取系統原型。

       所以，可以通過散列表和鏈表結合的方式，實現一個時間複雜度為O(1)的LRU快取。

       更多硬核知識，請關注公眾號」程式設計師學長“。