背景

一般來說快取是將會常被取用的資料暫存起來，避免重複的 I/O 以加快速度，而你的空間是有限的，勢必會需要淘汰一些既有資料才能放新的，而快取檔案置換機制就是決定哪些資料會優先淘汰，以最大保持你的快取命中率。

LRU(Least Recently Used) Cache

最近最少使用算法，顧名思義就是會優先清除掉沒被使用的資料。

規則：

  1. 最先進入快取的 key 會最先被刪除。
  2. 若某一 key 被取用或更新值，則該 key 會視為新寫入，因為要將其被刪除的順序降到最低。
  3. (額外) 由於會使用快取就是為了提高速度，所以實作上必須要求放值和取值都必須達到時間複雜度O(1)

範例：

當你依序放入 a, b, c 三個資料時，他們的優先刪除順序就是 1, 2, 3，所以當空間不夠需要刪除資料時會先刪掉 a，因為他最先加入而且從來沒被取用過。

讓我們時光倒流回到刪除前，現在有 a, b, c 三個資料時，他們的優先刪除順序就是 1, 2, 3，而這時有人取用了 a，因為 a 被取用了， 他的刪除優先順序會從 1 降成 3，而 b, c 的刪除優先順序則會被提升，所以 a, b, c 他們的優先刪除順序就會變成 3, 1, 2，當空間不夠需要刪除資料時會先刪掉 b。

題目：

LRU Cache - LeetCode

PHP 實作思路 :

首先需要思考要用什麼資料結構來存，根據前面提到的 LRU 的概念可以很自然的想到 php array，而必須注意的是 php array 跟一般學資料結構時定義的陣列不一樣，他是實作更高階的關聯陣列，簡單來說就是有序的 HashMap。
參考我的另一篇文章 - PHP Array

既然已經想到了 php array，再來實作上會發現的關鍵點是你的操作一定會需要用到頭尾，而由於鍵值對都拿去存資料了，你沒辦法用鍵當作順序，那麼應該如何在 O(1) 的情況下取得頭尾呢？

如果你已經想到要用另外一個空間去儲存順序，那麼恭喜你這道題已經解完了，一般來說這道題最常用的解法就是用 HashMap ＋ 雙向鏈結串列，用 HashMap 存 key 並指向雙向鏈結串列的節點，並用節點屬性來保存值，所以能保證查找的時間複雜度是 O(1)，而由於雙向鏈結串列能在時間複雜度 O(1) 找到所在節點的上下兩個節點，所以你的增刪也是時間複雜度 O(1)

補充一下，如果你是用 php 的話，你還是有辦法只用一個 php array 就做完的，這是因為 php array 實際上是有序的 HashMap，他會多花空間來記錄順序，也有多花空間來記錄起終點，所以剛好可以滿足 LRU 需要的條件，這個方法就是 array_key_first() 或 array_key_last() 。
參考官方說明，已明確指出時間複雜度 O(1)，

如果還是有疑慮或好奇，可以參考 php7.3.10 官方開源

這做法要考量的就是 php array 在有序這件事上到底花了多少成本，有興趣的話可以自己產生一些測試案例來實驗跟紀錄，不過就算比較慢你也沒得挑，因為目前還沒看到 php 能提供無序的方法給你選。

補充：java 的話可以採用 LinkedHashMap，這是基於 HashMap 的拓展，為有序 HashMap， 但尚未確認取得和插入頭尾的時間複雜度。
图解 LinkedHashMap 原理

PHP 實作程式碼 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
<?php

declare(strict_types=1);

namespace App;

use Exception;

class LRUCache
{
    private $capacity = 0;
    private $lruArr;

    /**
     * @param Integer $capacity
     */
    function __construct(int $capacity)
    {
        if ($capacity <= 0) {
            throw new Exception('input capacity must great than 0');
        }

        # 設定最大容量
        $this->capacity = $capacity;

        # 設定資料存放處，最尾端的優先度最高
        $this->lruArr = [];
    }

    /**
     *  取得值
     * 
     * @param Integer $key
     * @return Integer
     */
    public function get($key)
    {
        # 檢查是否已有鍵，若無則回傳 -1
        if (!isset($this->lruArr[$key])) {
            return -1;
        }

        # 找出目標值
        $targetValue = $this->lruArr[$key];

        # 將目標鍵值刪除再寫入，以將其優先度提至最高
        unset($this->lruArr[$key]);
        $this->lruArr[$key] = $targetValue;

        return $targetValue;
    }

    /**
     *  寫入值
     * 
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    public function put($key, $value)
    {
        # 未有鍵
        if (!isset($this->lruArr[$key])) {
            # 容量已滿，刪除優先度最低的
            if (count($this->lruArr) == $this->capacity) {
                unset($this->lruArr[array_key_first($this->lruArr)]);
            }
        } else {
            # 已有鍵，刪除舊值
            unset($this->lruArr[$key]);
        }

        # 寫入新值
        $this->lruArr[$key] = $value;
    }

    /**
     *  遍歷全部
     * 
     * @return Array
     */
    public function all(): array
    {
        return $this->lruArr;
    }
}