LRU 介紹

緩存是一種提高數據讀取性能的技術。但是對于計算機來說，并不可能緩存所有的數據，在達到它的臨界空間時，我們需要通過一些規則用新的數據取代掉一部分的緩存數據。這時候你會如果選擇替換呢？

替換的策略有很多種，常用的有以下幾種:

● FIFO (先進先出策略)

● LFU (最少使用策略)

● LRU (最近最少使用策略)

● NMRU (在最近沒有使用的緩存中隨機選擇一個替換)

介于我這篇主要實現 LRU，所以就不去介紹其他的了，可以自行去了解。

假設你已經有 5 個女朋友了，此時你成功勾搭上一個新女朋友，在你沉迷女色的同時，你驚奇的發現，你已經不能像年輕時一樣以一敵六了，你必須舍棄若干個女朋友，這時候，身擁六個女朋友的渣男你，徹底展示出你的渣男本色，和最近最少秀恩愛的小姐姐說再見：“對不起，國籃此時需要我挺身發邊線球，我楠辭琦咎，再見?！?，就這樣在你成功勾搭一個新小姐姐，你的身體臨界點的同時，你就必須舍棄其他的小姐姐。

下面來張實際點的圖搞清楚他的原理。

基于上述圖片，我們知道，對于 LRU 的操作，無非在于插入 (insert), 刪除 (delete)，以及替換，針對替換來說，如果緩存空間滿了，那么就是 insert to head and delete for tail。如果未滿，也分為兩種，一種是緩存命中的話，只需要把緩存的值 move to head。如果之前不存在，那么就是 insert to head。

實現過程

接下來就是數據結構的選擇了。數組的存儲是連續的內存空間，雖然查詢的時間復雜度是 O (1), 但是刪除和插入為了保存內存空間的連續性，需要進行搬移，那么時間復雜度就是 O (n), 為了實現能快速刪除，故而采用雙向鏈表。但是鏈表的查詢時間復雜度是 O (n), 那么就需要 hash table。屁話說了這么多，代碼實現。其實之前刷過這道題目。特地拿出來講一下。

html' target='_blank'>class LRUCache {    private $capacity;    private $list;    /**     * @param Integer $capacity     */    function __construct($capacity) {        $this->capacity=$capacity;        $this->list=new HashList();    }    /**     * @param Integer $key     * @return Integer     */    function get($key) {        if($key<0) return -1;        return $this->list->get($key);    }    /**     * @param Integer $key     * @param Integer $value     * @return NULL     */    function put($key, $value) {        $size=$this->list->size;        $isHas=$this->list->checkIndex($key);        if($isHas || $size+1 > $this->capacity){            $this->list->removeNode($key);        }        $this->list->addAsHead($key,$value);    }}class HashList{    public $head;    public $tail;    public $size;    public $buckets=[];    public function __construct(Node $head=null,Node $tail=null){        $this->head=$head;        $this->tail=$tail;        $this->size=0;    }    //檢查鍵是否存在    public function checkIndex($key){        $res=$this->buckets[$key];        if($res){            return true;        }        return false;    }    public function get($key){        $res=$this->buckets[$key];        if(!$res) return -1;        $this->moveToHead($res);        return $res->val;    }    //新加入的節點    public function addAsHead($key,$val){        $node=new Node($val);        if($this->tail==null && $this->head !=null){            $this->tail=$this->head;            $this->tail->next=null;            $this->tail->pre=$node;        }        $node->pre=null;        $node->next=$this->head;        $this->head->pre=$node;        $this->head=$node;        $node->key=$key;        $this->buckets[$key]=$node;        $this->size++;    }    //移除指針(已存在的鍵值對或者刪除最近最少使用原則)    public function removeNode($key){        $current=$this->head;        for($i=1;$i<$this->size;$i++){            if($current->key==$key) break;            $current=$current->next;        }        unset($this->buckets[$current->key]);        //調整指針        if($current->pre==null){            $current->next->pre=null;            $this->head=$current->next;        }else if($current->next ==null){            $current->pre->next=null;            $current=$current->pre;            $this->tail=$current;        }else{            $current->pre->next=$current->next;            $current->next->pre=$current->pre;            $current=null;        }        $this->size--;    }    //把對應的節點應到鏈表頭部(最近get或者剛剛put進去的node節點)    public function moveToHead(Node $node){        if($node==$this->head) return ;        //調整前后指針指向        $node->pre->next=$node->next;        $node->next->pre=$node->pre;        $node->next=$this->head;        $this->head->pre=$node;        $this->head=$node;        $node->pre=null;    }}class Node{    public $key;    public $val;    public $next;    public $pre;    public function __construct($val){        $this->val=$val;    }}/** * Your LRUCache object will be instantiated and called as such: * $obj = LRUCache($capacity); * $ret_1 = $obj->get($key); * $obj->put($key, $value);

Github 整理地址:https://github.com/wuqinqiang/leetcode-php

更多PHP知識，請訪問PHP中文網！

以上就是使用 PHP 實現 LRU 緩存淘汰算法的詳細內容，更多請關注 其它相關文章！

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。