LRU(cache)
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。屁话说了这么多,代码实现。其实之前刷过这道题目。特地拿出来讲一下。
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 缓存淘汰算法的详细内容。更多信息请关注PHP中文网其他相关文章!

要保护应用免受与会话相关的XSS攻击,需采取以下措施:1.设置HttpOnly和Secure标志保护会话cookie。2.对所有用户输入进行输出编码。3.实施内容安全策略(CSP)限制脚本来源。通过这些策略,可以有效防护会话相关的XSS攻击,确保用户数据安全。

优化PHP会话性能的方法包括:1.延迟会话启动,2.使用数据库存储会话,3.压缩会话数据,4.管理会话生命周期,5.实现会话共享。这些策略能显着提升应用在高并发环境下的效率。

thesession.gc_maxlifetimesettinginphpdeterminesthelifespanofsessiondata,setInSeconds.1)它'sconfiguredinphp.iniorviaini_set().2)abalanceIsiseededeedeedeedeedeedeedto to to avoidperformance andununununununexpectedLogOgouts.3)

在PHP中,可以使用session_name()函数配置会话名称。具体步骤如下:1.使用session_name()函数设置会话名称,例如session_name("my_session")。2.在设置会话名称后,调用session_start()启动会话。配置会话名称可以避免多应用间的会话数据冲突,并增强安全性,但需注意会话名称的唯一性、安全性、长度和设置时机。

会话ID应在登录时、敏感操作前和每30分钟定期重新生成。1.登录时重新生成会话ID可防会话固定攻击。2.敏感操作前重新生成提高安全性。3.定期重新生成降低长期利用风险,但需权衡用户体验。

在PHP中设置会话cookie参数可以通过session_set_cookie_params()函数实现。1)使用该函数设置参数,如过期时间、路径、域名、安全标志等;2)调用session_start()使参数生效;3)根据需求动态调整参数,如用户登录状态;4)注意设置secure和httponly标志以提升安全性。

在PHP中使用会话的主要目的是维护用户在不同页面之间的状态。1)会话通过session_start()函数启动,创建唯一会话ID并存储在用户cookie中。2)会话数据保存在服务器上,允许在不同请求间传递数据,如登录状态和购物车内容。

如何在子域名间共享会话?通过设置通用域名的会话cookie实现。1.在服务器端设置会话cookie的域为.example.com。2.选择合适的会话存储方式,如内存、数据库或分布式缓存。3.通过cookie传递会话ID,服务器根据ID检索和更新会话数据。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

适用于 Eclipse 的 SAP NetWeaver 服务器适配器
将Eclipse与SAP NetWeaver应用服务器集成。

VSCode Windows 64位 下载
微软推出的免费、功能强大的一款IDE编辑器

SecLists
SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

记事本++7.3.1
好用且免费的代码编辑器

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。