目录

面试题

ding jing 收录于面试题

2022-05-25 约 425 字预计阅读 1 分钟次阅读

目录

LRU 缓存机制实现

要求

实现一个 LRU(最近最少使用)缓存机制
获取/写入数据时间复杂度是O(1)
获取数据 – 如果数据存在缓存中，则获取到数据的值，否则返回 -1
写入数据 – 如果密钥不存在则写入数据值，当缓存容量达到上限时候，它应该在写入之前删除最近最少使用的数据值，从而为新的数据值留出空间。

实现思路

要想O(1)一定要用hash了
有容量大小限制，构造函数需要传入容量限制值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


构造函数:
    1. 传入容量大小限制的值
    2. 再定义属性 size 表示当前使用的容量
    3. 定义一个hashmap + 一个双向链表; hashmap存放键+双向链表节点、 双向链表保存键对应的值 + 引用次数

get函数:
    判断“键”是否存在于 hashmap，存在则获取对应的值，根据值获取到 hashmap 对应的值，然后更新引用计数，更新后与后一个节点比较，看看是否调整链表位置。

set函数:
    判断"键"是否存在于 hashmap，存在则直接退出，不存在则创建新节点，插入 hashmap，并把节点放入 双向链表头部