LRU #
- 要用哈希表 + 双向链表
- 哈希表:快速查找节点
- 双向链表
- 队头:最近访问的,或新加入的
- 队尾:最久未被访问
题目要求两个方法:
- get()
- 如果不存在,返回-1
- 如果存在:
- 通过key找哈希表,得到节点
- moveToHead 将该节点移到队头
- 返回节点的值
- put()
- cache.count(key)不存在的话
- new新链表节点
- 加到哈希表
- addToHead 添加到头部
- size++判断是否超出容量,如果超出:
- removeTail 删除尾部
- 删除哈希表cache.erase
- size–
- delete链表节点
- 否则就是已经存在:
- cache[key] 拿到节点
- 更新node->value为新的值
- moveToHead 将该节点移到队头
- cache.count(key)不存在的话
主要方法:
- 查找由哈希表负责
- 插入:要插哈希表,要插链表头,size++
- 删除:要删哈希表,要删链表尾,size–
- 变更:链表先删再插
注意:
- 用双向链表,且带伪头节点和伪尾节点
- 每次要注意是不是要同时操作链表和哈希表