LRU—–最近最少使用 缓存机制 实现LRUCache类
LRUCache(int capacity )以正整数作为容量capacity初始化LRU缓存 int get( int key)如果关键字key存在缓存中,则返回关键字的值,否则返回-1 void put(int key,int value)如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组。 当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新数据值流出空间。
使用现成双向链表—–LinkedHashMap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class LRUCache extends LinkedHashMap<Integer, Integer>{ private int capacity; public LRUCache(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; } }
使用哈希表+双向链表 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的。 哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。 首先使用哈希表进行定位,找出缓存在双向链表中的位置,随后将其移动到双向链表的头部,即可在O(1)的时间内完成get put
get操作如果key不存在 返回-1 如果key存在 则key对应的节点是最近被使用的节点。通过哈希表定位该节点在双向链表中的位置,并将其移动到双向链表的头部,最后返回该节点的值。 put操作如果key不存在,使用key和value创建一个新的节点,在双向链表的头部添加该节点,并将key和该节点添加进哈希表,然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项 如果key存在 ,则与get操作类似,通过哈希表定位 再将对应的节点更新,并将该节点移到双向链表的头部 时间复杂度 O(1)
空间复杂度 O(capacity)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) {key = _key; value = _value;} } private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } // 如果 key 存在,先通过哈希表定位,再移到头部 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { // 如果 key 不存在,创建一个新的节点 DLinkedNode newNode = new DLinkedNode(key, value); // 添加进哈希表 cache.put(key, newNode); // 添加至双向链表的头部 addToHead(newNode); ++size; if (size > capacity) { // 如果超出容量,删除双向链表的尾部节点 DLinkedNode tail = removeTail(); // 删除哈希表中对应的项 cache.remove(tail.key); --size; } } else { // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部 node.value = value; moveToHead(node); } } private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res; } }