赞
踩
用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。
利用一个链表来实现,每次新插入数据的时候将新数据插到链表的头部;每次缓存命中(即数据被访问),则将数据移到链表头部;那么当链表满的时候,就将链表尾部的数据丢弃。
对于第一种方法, 需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是O(n)。对于第二种方法,链表在定位数据的时候时间复杂度为O(n)。因此,一般使用第三种方式来实现LRU算法。
import java.util.HashMap; import java.util.Map; /** * @ program: leet-code * @ description: LRU算法(Least Recently Used (最近最久未使用)) * @ author: zhihua li * @ create: 2021-08-18 20:04 **/ public class LRUCache { // 定义双向链表结点结构 class ListNode { int key; int value; ListNode prev; ListNode next; public ListNode(int key, int value) { this.key = key; this.value = value; } } // 定义缓存 Map 的容量,大小固定 private int capacity; // 当前缓存中节点个数 private int count; // 设置虚节点用来保存数组,并保证在删除首节点时操作简单 private ListNode dummy; // 定义尾指针,记录当前链表最后一个元素位置 private ListNode tail; // 缓存 Map private Map<Integer, ListNode> map; // 对缓存结构进行初始化,包括双向链表初始化及缓存Map初始化 public LRUCache(int capacity) { this.capacity = capacity; count = 0; dummy = new ListNode(0, 0); tail = dummy; map = new HashMap<>(); } // 移除首节点的辅助方法,在缓存溢出时使用 private void removeHead() { map.remove(dummy.next.key); dummy.next = dummy.next.next; if (dummy.next != null) { dummy.next.prev = dummy; } } // 添加节点的辅助方法,在查找和添加中使用 private void appendTail(ListNode node) { tail.next = node; node.prev = tail; tail = node; } // 真实实现的get方法 public int get(int key) { // 缓存中不存在该k if (!map.containsKey(key)) { return -1; } else { // 缓存中存在该 k ListNode node = map.get(key); // 如果 k 对应的节点不是最后一个节点,需要将这个节点放在链表尾部代表最近被使用过 if (node != tail) { ListNode prev = node.prev; prev.next = node.next; prev.next.prev = prev; appendTail(node); } return node.value; } } // 真实实现的 put方法 // 若缓存中存在该节点,就删除原来的节点并添加到尾部 // 若缓存中不存在,则新增节点到尾部,同时需要将count进行自增,保证缓存不溢出 // 也就是说,不管缓存中有没有这个k,最后都要将节点放到链表尾部 public void put(int key, int value) { // 首先先将待插入节点进行初始化 ListNode node = new ListNode(key, value); // 若map中存在该 k if (map.containsKey(key)) { // 首先获取Map中的该节点,进行删除 ListNode temp = map.get(key); if (temp != tail) { // 若不是链表中的最后一个节点,就需要修改prev指针 ListNode prev = temp.prev; prev.next = temp.next; prev.next.prev = prev; } else { // 直接删除 tail = tail.prev; } } else { // 如果map中不存在该 K,就需要将count进行自增保证缓存大小固定 if (count < capacity) { count++; } else { // 若当前缓存溢出,就删除最近最久未使用的节点 removeHead(); } } // 不管原来的缓存中是否存在该节点,都添加到链表尾部,并重新设置到缓存中(有就覆盖,没有就新增) appendTail(node); map.put(key, node); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。