Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to write code to achieve LRU algorithm", the content of the article is simple and clear, easy to learn and understand, now please follow the editor's ideas slowly in depth, together to study and learn "how to write code to achieve LRU algorithm" bar!

Use the data structures you know to design and implement a LRU (least recently used) caching mechanism.

Implement the LRUCache class:

LRUCache (int capacity) initializes the LRU cache with a positive integer as the capacity capacity

Int get (int key) returns the value of the keyword if the keyword key exists in the cache, otherwise it returns-1.

Void put (int key, int value) if the keyword already exists, change its data value; if the keyword does not exist, insert the set of keyword-values. When the cache capacity reaches the limit, it should delete the longest unused data values before writing new data, leaving room for new data values.

Requirements: complete these two operations within O (1) time complexity.

Thinking

1 the so-called cache, there must be read + write two operations, according to the hit rate of thinking, write + read operation time complexity needs to be O (1)

2 characteristic requirement analysis

2.1 there must be an order to distinguish between recently used and long-unused data sorting.

2.2 write and read operations are done at once.

2.3 if the capacity (pit) is full to delete the least long-lasting data, the new data should be inserted into the head of the line for each new access (which side is the head of the line according to the business you set)

Find quickly, insert quickly, delete quickly, and need to sort first-> what kind of data structure satisfies this problem?

Can you do these two operations within O (1) time complexity?

If you can find it at once, what data structure do you think is the most appropriate?

Reference LinkedHashMap

Option 1 relies on JDKpackage com.lau.lrualgorithm.way;import java.util.LinkedHashMap;import java.util.Map;/** * to reuse HashMap * / public class ReuseLinkedHashMap extends LinkedHashMap {/ / maximum allowed caches in existing api private int cacheSize; / / reload constructor public ReuseLinkedHashMap (int cacheSize) {super (cacheSize, 0.75f, true); this.cacheSize = cacheSize } @ Override protected boolean removeEldestEntry (Map.Entry eldest) {return super.size () > cacheSize;} public V put (K key, V value) {/ / if (super.size () = = this.cachesize) {/ / super.removeEldestEntry (); / /} return super.put (key, value);} public V get (Object key) {return super.get (key) } public static void main (String [] args) {ReuseLinkedHashMap map = new ReuseLinkedHashMap (3); map.put (1,1); map.put (2,2); map.put (3,3); System.out.println (map.keySet ()); map.put (4,1); System.out.println (map.keySet ()); map.put (3,1) System.out.println (map.keySet ()); map.put (3,1); System.out.println (map.keySet ()); map.put (3,1); System.out.println (map.keySet ()); map.put (5,1); System.out.println (map.keySet ()) }} / * true * [1,2,3] * [2,3,4] * [2,4,3] * [2,4,3] * [2,4,3] * [4,3,5] * / * false [1,2,3] [2,3,4] [2,3,4] [2,3,4] [2,3,4] [3,4,5] * /

Key points:

1. Override the removeEldestEntry () method

2. AccessOrder-the ordering mode-true for access-order, false for insertion-order

3. The latest node storage order: from right to left

The second scheme does not rely on JDKpackage com.lau.lrualgorithm.way;import java.util.HashMap;import java.util.Map;//map to find and build a virtual two-way linked list, in which Node nodes are installed as data carriers. Public class LruCacheDemo {/ / 1. Construct a node node as the data carrier class Node {K key; V value; Node prev; Node next; public Node () {this.prev = this.next = null;} public Node (K key, V value) {this.key = key; this.value = value; this.prev = this.next = null }} / / 2 build a virtual bi-directional linked list, in which is our Node class DoubleLinkedList {Node head; Node tail; public DoubleLinkedList () {head = new Node (); tail = new Node (); head.next = tail; tail.prev = head;} / / 3. Add to the header public void addHead (Node node) {node.next = head.next; node.prev = head; head.next.prev = node; head.next = node;} / / 4. Delete node public void removeNode (Node node) {node.next.prev = node.prev; node.prev.next = node.next; node.prev = null; node.next = null;} / / 5. Get the last node public Node getLast () {return tail.prev;}} private int cacheSize; Map map; DoubleLinkedList doubleLinkedList; public LruCacheDemo (int cacheSize) {this.cacheSize = cacheSize;// pit map = new HashMap (); / / find doubleLinkedList = new DoubleLinkedList () } public int get (int key) {if (! map.containsKey (key)) {return-1;} Node node = map.get (key); doubleLinkedList.removeNode (node); doubleLinkedList.addHead (node); return node.value } public void put (int key, int value) {if (map.containsKey (key)) {/ / update Node node = map.get (key); node.value = value;// map.put (key, node); doubleLinkedList.removeNode (node); doubleLinkedList.addHead (node) } else {if (map.size () = = cacheSize) / / the pit is full of {Node lastNode = doubleLinkedList.getLast (); map.remove (lastNode.key); doubleLinkedList.removeNode (lastNode);} / / add a Node newNode = newNode (key, value) Map.put (key, newNode); doubleLinkedList.addHead (newNode);}} public static void main (String [] args) {LruCacheDemo lruCacheDemo = new LruCacheDemo (3); lruCacheDemo.put (1,1); lruCacheDemo.put (2,2); lruCacheDemo.put (3,3); / / you cannot print map directly because this map is unordered! / / System.out.println (lruCacheDemo.map.keySet ()); printKeys (lruCacheDemo); lruCacheDemo.put (4,1); / / System.out.println (lruCacheDemo.map.keySet ()); printKeys (lruCacheDemo); lruCacheDemo.put (3,1); / / System.out.println (lruCacheDemo.map.keySet ()); printKeys (lruCacheDemo); lruCacheDemo.put (3,1) / / System.out.println (lruCacheDemo.map.keySet ()); printKeys (lruCacheDemo); lruCacheDemo.put (3,1); / / System.out.println (lruCacheDemo.map.keySet ()); printKeys (lruCacheDemo); lruCacheDemo.put (5,1); / / System.out.println (lruCacheDemo.map.keySet ()); printKeys (lruCacheDemo) } private static void printKeys (LruCacheDemo lruCacheDemo) {Node node = lruCacheDemo.doubleLinkedList.head.next; while (node! = null & & node.key! = null) {System.out.print (node.key + "); node = node.next;} System.out.println () }} / * * true * [1,2,3] * [2,3,4] * [2,4,3] * [2,4,3] * [2,4,3] * [4,3,5] * / * false [1,2,3] [2,3,4] [2,3,4] [2,3,4] [2,3] 4] [3,4,5] * /

Note:

Latest node storage order: from left to right

Handwritten data structure

Thank you for your reading, the above is the content of "how to write code to achieve LRU algorithm". After the study of this article, I believe you have a deeper understanding of how to write code to achieve LRU algorithm, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.