醉丶春风的Blog

LRU原理

LRU(least recently used, 最近最少使用),LRU算法的设计原则是：

如果一个 数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。

实现

这里我们使用一个单链表来保存数据，越靠近链表尾部的结点是越早之前访问的, 越靠近链表头部的结点是最近插入或者访问的, 我们的目标:

• 新的数据插入到链表头部；
• 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
• 当链表满的时候，自动链表尾部的数据丢弃。

php代码实现

节点类

class Node {

    public $data;

    /**
     * @var self
     */
    public $next = null;

    /**
     * @var string 元素Key
     */
    public $key = '';

    public function __construct($key, $data = null, $next = null)
    {
        $this->data = $data;
        $this->next = $next;
        $this->key = $key;
    }
}

链表类

class LruSingieLinkedList {
    /**
     * @var Node 带头节点
     */
    public $head;

    /**
     * @var int 存储链表长度
     */
    public $length = 0;

    /**
     * @var int 假定缓存空间大小
     */
    public $maxLength = 5;

    public function __construct()
    {
        $this->head = new Node(null);
    }

    /**
     * 设置缓存, 当有key相同时, 删除原key节点
     * 当当前数量大于等于最大可用数量时, 删除最后一个元素
     * @param $key
     * @param $data
     * @return $this
     */
    public function set($key, $data)
    {
        // 保存倒数第二个元素节点, 如果大于缓存空间, 就删除最后一个元素
        $penultimateNode = null;
        $current = $this->head;
        while ($current->next !== null) {
            // 判断是否有同名key, 有就删除并结束循环
            if ($key == $current->next->key) {
                $current->next = $current->next->next;
                $this->length --;
                break;
            }
            if ($current->next->next === null) {
                // 保存倒数第二个元素节点
                $penultimateNode = $current;
            }
            $current = $current->next;
        }
        // 缓存数量大于等于最大数量
        if ($this->length >= $this->maxLength) {
            // 删除最后一个节点
            $penultimateNode->next = null;
            $this->length --;
        }
        // 插入元素, 遍历链表, 判断key是否存在, 存在就删除, 最后执行插入到头部的动作
        $this->head->next = new Node($key, $data, $this->head->next);
        $this->length ++;
        return $this;
    }

    /**
     * 获取缓存, 当命中key时, 将当前元素插入到链表头部
     * @param $key
     * @return bool|null
     */
    public function get($key)
    {
        $prev = $this->head;
        while ($prev->next !== null) {
            // 以head为起点, 查找下一个元素的key是否等于参数key
            // 如果等于, 说明查找到了数据, 此时, 需要将该元素从该位置删除, 并添加到表头
            if ($key == $prev->next->key) {
                $current = $prev->next;
                // 从该位置删除该元素
                $prev->next = $prev->next->next;
                // 将该元素添加到链表头部
                $current->next = $this->head->next;
                $this->head->next = $current;

                return $current->data;
            }
            $prev = $prev->next;
        }
        return false;
    }

    /**
     * 测试打印
     */
    public function print()
    {
        $current = $this->head->next;
        echo '<hr>';
        while ($current !== null) {
            echo sprintf('key= %s, value=', $current->key);
            print_r($current->data);
            echo '<br>';
            $current = $current->next;
        }
    }

}

测试使用

$lruCache = new LruSingieLinkedList();
$lruCache->set('item1', 1)
    ->set('item2', 2)
    ->set('item3', 3)
    ->set('item4', 4)
    ->set('item5', 5)
    ->set('item6', 6)
    ->set('item6', 666)
    ->set('item7', 7)
    ->print();

$lruCache->get('item3');

$lruCache->print();

$lruCache->set('item8', 8)
    ->print();

访问过程如下