*Clock in algorithm *leetcode 146 Analysis of LRU cache algorithm

Recommended reading

• CSDN Home page
• GitHub Open source address
• Unity3D Plug in sharing
• Jane book address
• My personal blog
• QQ Group ：1040082875

Hello everyone , I'm the little magic dragon ,Unity3D Software engineer ,VR、AR, Virtual simulation direction , Update software development skills from time to time , Life experience , I think it's useful. Remember to press one button three times .

One 、 subject

1、 Algorithm title

“ Design and implement a system that meets   LRU ( Recently at least use ) cache   Constrained data structure .”

Topic link ：

source ： Power button （LeetCode）

link ： 146. LRU cache - Power button （LeetCode）

2、 Title Description

Please design and implement a meeting   LRU ( Recently at least use ) cache Constrained data structure .
Realization LRUCache class ：

• LRUCache(int capacity) With Positive integer As capacity  capacity initialization LRU cache
• int get(int key) If the keyword key In the cache , The value of the keyword is returned , Otherwise return to -1 .
• void put(int key, int value)  If the keyword  key Already exist , Change its data value  value ; If it doesn't exist , Then insert the group into the cache  key-value . If the insert operation causes the number of keywords to exceed  capacity , Should be Eviction The longest unused keyword .

function get and put Must be O(1) The average time complexity of running .

 Example  1： Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4] explain LRUCache lRUCache = new LRUCache(2);lRUCache.put(1, 1); //  The cache is  {1=1}lRUCache.put(2, 2); //  The cache is  {1=1, 2=2}lRUCache.get(1);    //  return  1lRUCache.put(3, 3); //  This operation causes the keyword to  2  To void , The cache is  {1=1, 3=3}lRUCache.get(2);    //  return  -1 ( Not found )lRUCache.put(4, 4); //  This operation causes the keyword to  1  To void , The cache is  {4=4, 3=3}lRUCache.get(1);    //  return  -1 ( Not found )lRUCache.get(3);    //  return  3lRUCache.get(4);    //  return  4

 Example  2：

Two 、 Problem solving

1、 Thought analysis

The main solution to this problem is to use a hash table plus a two-way linked list to achieve .

stay Python The language has a data structure that combines a hash table and a two-way linked list OrderedDict
stay Java Language has the same data structure LinkedHashMap.

Next, we will implement hash table and bidirectional linked list LRU Caching mechanisms .

2、 Code implementation

Code reference ：

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;        //  Using pseudo head and pseudo tail nodes         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;        }        //  If  key  There is , First, locate through the hash table , And then to the head         moveToHead(node);        return node.value;    }    public void put(int key, int value) {        DLinkedNode node = cache.get(key);        if (node == null) {            //  If  key  non-existent , Create a new node             DLinkedNode newNode = new DLinkedNode(key, value);            //  Add to hash table             cache.put(key, newNode);            //  Add to the head of the bidirectional list             addToHead(newNode);            ++size;            if (size > capacity) {                //  If the capacity is exceeded , Delete the tail node of the bidirectional linked list                 DLinkedNode tail = removeTail();                //  Delete the corresponding entry in the hash table                 cache.remove(tail.key);                --size;            }        }        else {            //  If  key  There is , First, locate through the hash table , Revise  value, And move to the head             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;    }}

3、 Time complexity

Time complexity ：O(1)

about put and get The time complexity of O(1).

Spatial complexity ：O(capacity)

Because hash tables and bidirectional linked lists store the most capacity+1 Elements .

3、 ... and 、 summary

Use hash table and bidirectional linked list to realize LRU Caching mechanisms ：

• A two-way linked list stores key value pairs in the order they are used , The key value pair near the head is the most recently used
• The hash table maps the key value pairs of cached data to their positions in the bidirectional linked list .