“This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

The author in addition to college elective “algorithm design and analysis” and “data structure” is muddle through (doesn’t matter much thought and programming), other time is less on contact algorithm, but with the development time of some underlying code/contact processing mechanism increasingly feel algorithm, the importance of So I decided to start systematic study (mainly brush force buckle on the topic) and sorting, also hope that those who have not started to learn as soon as possible.

A series of articles is included in the algorithm column.

LRU algorithms are common, such as Redis, which automatically cleans up the least recently used data due to limited memory space, and Mybatis, which also has LruCaches implemented in local caches.

Problem description

Design and implement a data structure that satisfies the LRU (least recently used) cache constraints. Implement the LRUCache class:

  • LRUCache(int capacity) The LRU cache is initialized using a positive integer as capacity
  • Int get(int key) Returns the value of the key if it exists in the cache, otherwise -1 is returned.
  • Void put(int key, int value) If the key already exists, change its value. If not, the group key-value is inserted into the cache. If the number of keywords exceeds capacity due to an insert operation, you need to export the unused keywords.

The functions get and PUT must run in O(1) average time complexity.

Example:

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] LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); / / return 4Copy the code

Tip:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • Get and put are called up to 2 * 10^5 times

Define learning objectives

The algorithm process of LRU Cache Algorithm is analyzed.

Analyze the

We try to solve our problems one by one:

  1. Capacity is used to control the capacity when the LRUCache object is created. LRUCache configures capacity(to set the capacity) and size(to record the number of stored elements). During put, you need to compare capacity and size.
  2. Int get(int key) returns the value of the key if the key exists in the cache, otherwise -1: this is not difficult, but the average time complexity of get needs to be O(1), we can easily use HashMap to store, even if the hash collision is just a list traversal and red black.
  3. Void put(int key, int value) If the key already exists, change its value. If not, the group key-value is inserted into the cache. If the number of keywords exceeds capacity as a result of an insert operation, the oldest unused keyword should be expelled: the first half of HashMap is already implemented, and the second half is described with GET in point 4.
  4. After get, the corresponding element becomes the most recently used; after PUT, the corresponding element becomes the most recently used; after PUT exceeds capacity, the longest unused keyword needs to be discarded: It is also easy to think of a two-way queue, with just get or put elements at the head of the queue, and the last element at the end of the queue when capacity exceeds.

So let’s go straight to the code

code

package com.study.algorithm.lru; import java.util.HashMap; import java.util.Map; Public class LRUCache {/** * class DLinkedNode {private int key; private int value; /** * private DLinkedNode prev; /** * private DLinkedNode next; public DLinkedNode() { } public DLinkedNode(int key, int value) { this.key = key; this.value = value; }} /** * use hashmap as cache, key as key, Value is DLinkedNode */ private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>(); /** * Private int size; /** * Private int capacity; Private DLinkedNode head; private DLinkedNode head; Private DLinkedNode tail; private DLinkedNode tail; public LRUCache(int capacity) { this.capacity = capacity; this.size = 0; this.head = new DLinkedNode(); this.tail = new DLinkedNode(); this.head.next = this.tail; this.tail.prev = this.head; } /** * return value; * * @param key * @return */ public int get(int key) {DLinkedNode node = cache.get(key); if (node == null) { return -1; } // Remove the node from the list and move it to the head moveToHead(node); return node.value; } /** * reassign value and move it to the header if it does, add if it does not. * Check whether size is greater than or equal to capacity. If true, remove it from cache and list. * * @param key * @param value */ public void put(int key, int value) { DLinkedNode node = cache.get(key); If (node == null) {// If (size >= capacity) {cache.remove(tail.prev.key); removeNode(tail.prev); --size; } DLinkedNode newNode = new DLinkedNode(key, value); addToHead(newNode); cache.put(key, newNode); ++size; } else { node.value = value; moveToHead(node); ** @param node */ public void removeNode(DLinkedNode node) {node.prev.next = node.next; node.next.prev = node.prev; } @param node */ public void addToHead(DLinkedNode node) {node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } @param node */ public void moveToHead(DLinkedNode node) {// Remove removeNode(node); AddToHead (node); } public static void main(String[] args) { LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); // Return 4}}Copy the code