php实现国密算法_使用PHP实现LRU缓存淘汰算法

LRU(cache)

LRU 介绍

缓存是一种提高数据读取性能的技术。但是对于计算机来说&＃xff0c;并不可能缓存所有的数据&＃xff0c;在达到它的临界空间时&＃xff0c;我们需要通过一些规则用新的数据取代掉一部分的缓存数据。这时候你会如果选择替换呢&＃xff1f;

替换的策略有很多种&＃xff0c;常用的有以下几种:

● FIFO (先进先出策略)

● LFU (最少使用策略)

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

● NMRU (在最近没有使用的缓存中随机选择一个替换)

介于我这篇主要实现 LRU&＃xff0c;所以就不去介绍其他的了&＃xff0c;可以自行去了解。

假设你已经有 5 个女朋友了&＃xff0c;此时你成功勾搭上一个新女朋友&＃xff0c;在你沉迷女色的同时&＃xff0c;你惊奇的发现&＃xff0c;你已经不能像年轻时一样以一敌六了&＃xff0c;你必须舍弃若干个女朋友&＃xff0c;这时候&＃xff0c;身拥六个女朋友的渣男你&＃xff0c;彻底展示出你的渣男本色&＃xff0c;和最近最少秀恩爱的小姐姐说再见&＃xff1a;“对不起&＃xff0c;国篮此时需要我挺身发边线球&＃xff0c;我楠辞琦咎&＃xff0c;再见。”&＃xff0c;就这样在你成功勾搭一个新小姐姐&＃xff0c;你的身体临界点的同时&＃xff0c;你就必须舍弃其他的小姐姐。

下面来张实际点的图搞清楚他的原理。

基于上述图片&＃xff0c;我们知道&＃xff0c;对于 LRU 的操作&＃xff0c;无非在于插入 (insert), 删除 (delete)&＃xff0c;以及替换&＃xff0c;针对替换来说&＃xff0c;如果缓存空间满了&＃xff0c;那么就是 insert to head and delete for tail。如果未满&＃xff0c;也分为两种&＃xff0c;一种是缓存命中的话&＃xff0c;只需要把缓存的值 move to head。如果之前不存在&＃xff0c;那么就是 insert to head。

实现过程

接下来就是数据结构的选择了。数组的存储是连续的内存空间&＃xff0c;虽然查询的时间复杂度是 O (1), 但是删除和插入为了保存内存空间的连续性&＃xff0c;需要进行搬移&＃xff0c;那么时间复杂度就是 O (n), 为了实现能快速删除&＃xff0c;故而采用双向链表。但是链表的查询时间复杂度是 O (n), 那么就需要 hash table。屁话说了这么多&＃xff0c;代码实现。其实之前刷过这道题目。特地拿出来讲一下。

class LRUCache {

private $capacity;

private $list;

/**

* &＃64;param Integer $capacity

*/

function __construct($capacity) {

$this->capacity&＃61;$capacity;

$this->list&＃61;new HashList();

}

/**

* &＃64;param Integer $key

* &＃64;return Integer

*/

function get($key) {

if($key<0) return -1;

return $this->list->get($key);

}

/**

* &＃64;param Integer $key

* &＃64;param Integer $value

* &＃64;return NULL

*/

function put($key, $value) {

$size&＃61;$this->list->size;

$isHas&＃61;$this->list->checkIndex($key);

if($isHas || $size&＃43;1 > $this->capacity){

$this->list->removeNode($key);

}

$this->list->addAsHead($key,$value);

}

}

class HashList{

public $head;

public $tail;

public $size;

public $buckets&＃61;[];

public function __construct(Node $head&＃61;null,Node $tail&＃61;null){

$this->head&＃61;$head;

$this->tail&＃61;$tail;

$this->size&＃61;0;

}

//检查键是否存在

public function checkIndex($key){

$res&＃61;$this->buckets[$key];

if($res){

return true;

}

return false;

}

public function get($key){

$res&＃61;$this->buckets[$key];

if(!$res) return -1;

$this->moveToHead($res);

return $res->val;

}

//新加入的节点

public function addAsHead($key,$val)

{

$node&＃61;new Node($val);

if($this->tail&＃61;&＃61;null && $this->head !&＃61;null){

$this->tail&＃61;$this->head;

$this->tail->next&＃61;null;

$this->tail->pre&＃61;$node;

}

$node->pre&＃61;null;

$node->next&＃61;$this->head;

$this->head->pre&＃61;$node;

$this->head&＃61;$node;

$node->key&＃61;$key;

$this->buckets[$key]&＃61;$node;

$this->size&＃43;&＃43;;

}

//移除指针(已存在的键值对或者删除最近最少使用原则)

public function removeNode($key)

{

$current&＃61;$this->head;

for($i&＃61;1;$isize;$i&＃43;&＃43;){

if($current->key&＃61;&＃61;$key) break;

$current&＃61;$current->next;

}

unset($this->buckets[$current->key]);

//调整指针

if($current->pre&＃61;&＃61;null){

$current->next->pre&＃61;null;

$this->head&＃61;$current->next;

}else if($current->next &＃61;&＃61;null){

$current->pre->next&＃61;null;

$current&＃61;$current->pre;

$this->tail&＃61;$current;

}else{

$current->pre->next&＃61;$current->next;

$current->next->pre&＃61;$current->pre;

$current&＃61;null;

}

$this->size--;

}

//把对应的节点应到链表头部(最近get或者刚刚put进去的node节点)

public function moveToHead(Node $node)

{

if($node&＃61;&＃61;$this->head) return ;

//调整前后指针指向

$node->pre->next&＃61;$node->next;

$node->next->pre&＃61;$node->pre;

$node->next&＃61;$this->head;

$this->head->pre&＃61;$node;

$this->head&＃61;$node;

$node->pre&＃61;null;

}

}

class Node{

public $key;

public $val;

public $next;

public $pre;

public function __construct($val)

{

$this->val&＃61;$val;

}

}

/**

* Your LRUCache object will be instantiated and called as such:

* $obj &＃61; LRUCache($capacity);

* $ret_1 &＃61; $obj->get($key);

* $obj->put($key, $value);

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

更多PHP知识&＃xff0c;请访问&＃xff01;