LinkedHashMap内部维护一个一个双向链表和一个hash表，所以在O(1)的时间复杂度下实现LRU。
/** • 使用jdk库类实现LRU */ class LRUCacheByLinkedHashMap { private LinkedHashMap nodes; private int size; public LRUCacheByLinkedHashMap(int capacity) { //实现LRU的linkedHashMap的构造方法 nodes = new LinkedHashMap<>(capacity, 0.75f, true); this.size = capacity; } public int get(int key) { Integer ret = nodes.get(key); return ret == null ? -1 : ret; } public void put(int key, int value) { nodes.put(key, value); if (nodes.size() > size) { //使用迭代器删除第一个数据 Iterator> iterator = nodes.entrySet().iterator(); if (iterator.hasNext()) { iterator.next(); iterator.remove(); } } } }
自己实现LRU
我们通过看LinkedHashMap的源代码，知道其所以然后就可以自己实现它。
class LRUCache { static class Node { int key; int val; Node prev; Node next; private Node(){} public Node(int key, int val) { this.key = key; this.val = val; } } private int size; private HashMap map; private int capacity; private Node head; private Node tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; map = new HashMap<>(); head = new Node(); tail = new Node(); head.next = tail; tail.prev = head; } public int get(int key) { Node node = map.get(key); if (node == null) { //没有这个节点 return -1; } //需要移动到最前面 moveHead(node);
