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

This article focuses on "how to add new information to HashMap and LinkedList". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to add new information to HashMap and LinkedList.

What is LRU CacheLRU?

LRU = Least Recently Used is the least recently used

It is a cache eviction strategy cache eviction policies

The LRU algorithm assumes that the information that is least used recently is not likely to be used in the future, so in the case of limited capacity, it can kick out the information that is not commonly used and make room.

For example, when there is hot news, everyone is searching for this information, and the information that has just been searched by one person is also more likely to be searched by others, which is more likely than an outdated news from the previous two days, so we kick out the information that has not been used for a long time, that is, the Least Recently Used information is kicked out.

For example: we have a memory capacity of 5, and now we have five numbers from 1 to 5.

Now we want to add a new number: 6.

But the capacity is full, so one needs to be kicked out.

Then according to what rules to kick out, there will be this cache eviction strategy. For example:

FIFO (First In First Out) this is the ordinary first-in-first-out.

LFU (Least Frequently Used) this is to count the number of visits to each information and kick out the one with the least number of visits; if the visits are the same, kick out the one that has not been used for a long time. This algorithm is actually very efficient, but it consumes resources, so it is generally not used.

LRU (Least Recently Used) this is the most commonly used at present.

LRU's rule is to kick out things that haven't been used for a long time, so its implicit assumption is that the most recently used information will be more likely to be used later.

So in our example, we kick out the oldest 1 and turn it into:

Keep iterating.

What is Cache?

The simple understanding is: store some reusable information so that you can get it quickly when you need it later.

As for where it is stored, it is not certain. The most common thing is to store it in memory, that is, memory cache, but it may not exist in memory.

There are even more usage scenarios, such as @ Cacheable and a series of annotations that support Cache in Spring. I used this annotation in my work last month, which of course was packaged by our company, which greatly reduced the number of call servers and solved a performance problem.

For example, when querying the database, we do not want to go to the call database every time we request it, so we will store some commonly used data in memory to improve access performance.

This kind of design idea actually follows the famous "28 laws". When reading and writing to the database, each request O process consumes a lot, but in fact, 80% of the data is using those 20% of the data, so putting these 20% of the data in memory can greatly improve the overall efficiency.

In short, the purpose of Cache is to store some reusable information to facilitate quick access to future requests.

LRU Cache

So we know LRU, we know Cache, and together it's LRU Cache:

When the Cache storage is full, use the LRU algorithm to clean up the old guy.

Detailed explanation of the train of thought

After all I've said, Let's get to the meat of the problem!

Everyone knows that this classic problem is to use HashMap + Doubly Linked List, or the ready-made LinkedHashMap in Java, but why? How did you come up with these two data structures? If you don't explain this clearly during the interview, if you don't talk about the thinking process, it's no use writing the right code.

Similar to the design idea at work, no one will tell us what data structure to use, the general idea is to first want to have which operations, and then according to these operations, and then to see which data structure is appropriate.

Analyze Operations

Let's analyze what needs to be done for this LRU Cache:

First of all, the most basic operation is to be able to read information from it, otherwise how to get it quickly after that.

Then you have to be able to add new information, and the new information comes in most recently used.

Before adding new information, we have to see if there are any seats available. If there is no room, you have to kick the old one out first, then you need to be able to find the old guy and delete it.

Well, if the new information is already in the cache, it means that key already exists. If you want to update value, you only need to adjust the priority of this message. It has been promoted to imperial concubine from that time.

Looking for data structures

It is obvious that the first operation is that we need a data structure that can be found quickly, which must be HashMap. If we do not understand the principles and design rules of HashMap, we will send you a message "HashMap" in the official account to send you a popular style article.

But the latter operation HashMap is not very useful.

Come on, let's count the basic data structures:

Array, LinkedList, Stack, Queue, Tree, BST, Heap, HashMap

When doing the problem of this kind of data structure, all the data structures are listed and analyzed one by one, sometimes not because this data structure is bad, but because other data structures are better.

What do you call it better? Forget our yardstick! Time and space complexity, quickly review the recursive article, the official account reply "recursive" can be obtained.

Then our analysis is as follows:

Array, Stack, and Queue are all essentially implemented by Array (of course, Stack and Queue can also be implemented with LinkedList. ), insert the new one, delete the old one, and adjust the order. Either array can't do it, or you can get O (n), and you can't afford it.

BST similarly, the time complexity is O (logn).

Heap is O (logn) even if it can.

LinkedList, a little bit OK, according to the order from the old to the new, ranking stations, delete, insert, move, can be O (1) ah! But I still need a previous pointer to delete it, so I need a Doubly LinkedList.

So our data structure is as follows:

HashMap + Doubly LinkedList

Define clearly the contents of the data structure

After you have selected the data structure, you also need to define exactly what each data structure stores and how the two data structures are related, which is the core issue.

Let's think of a scenario. In a search engine, you type the question Questions and Google returns the answer Answer to you.

Let's first assume that both data structures are stored, and then let's take a look at these operations. If both go well, that's fine. If there's a problem, we'll adjust it.

So now our HashMap and LinkedList look like this:

Then let's look back at these four operations:

Operation 1, no problem, read Answer directly from HashMap, O (1)

Operation 2, add a new group of QSecretA, and both data structures have to be added. First, we need to determine whether this Q is in the current cache. Then we use HashMap to determine whether this Q is in the current cache.

If you don't have this Q, add it in, it's all right.

If you already have the QMagol HashMap here to update the Answer, then we have to move the LinkedList node to the last or the front, because it has become the latest used one.

However, how to find this node of LinkedList? Looking for traverse one by one is not what we want, because we want O (n) time, we want to use O (1) time operation.

That is to say, it is not possible to record in this way, and you also need to record the location of each ListNode in the LinkedList, which is the crux of the problem.

Of course, it is to record the location of the ListNode in the HashMap, that is, to save the reference of each ListNode.

Come to think of it, there is no need to record Answer,Answer in HashMap, just record it in LinkedList.

After that, when we update and move each node, its reference does not need to change, so the HashMap does not need to change, only previous, next pointer.

On second thought, in fact, there is no need to record Question in LinkedList, anyway, it is in HashMap.

The two data structures cooperate with each other and do not need to record the same information.

The updated data structure is as follows:

In this way, we analyze what data structure is used, what is stored in each data structure, and what is the physical meaning.

In fact, LinkedHashMap in Java has been well implemented. However, even if you can use it in the interview, it is deduced step by step, instead of knowing to use it as soon as you see the question, it is to memorize the answer.

A classmate asked me, if the interviewer asks me if I have done this question, how to answer it?

A: tell the truth.

Sincerity is very important in interviews and jobs, so just tell the truth. But if the interviewer doesn't ask, you don't have to say.

In fact, the interviewer does not care whether you have done this question or not, because everyone has done the exercises and basically everyone has done it, so there is no point in asking this question. As long as you can analyze the problem clearly and explain the logic clearly, what if you have done it? Many people who have overdone the problem can't explain it clearly.

Summary

Let's summarize those four operations again:

The first operation, that is, get () API, has nothing to say

Two, three, four, it's put () API, there's a little trouble:

Speaking and writing while drawing, every step from high level to detail to code, modularizing the code.

For example, "Welcome" is to add this new information to HashMap and LinkedList, then I will use a separate add () method to write this content, then I named it appendHead () in the following code, which is more accurate.

"kick off the old" here I also use a separate remove () method to write.

When I drew this picture, the interviewer didn't ask me to write the code, so I went straight to the next question.

Then if the interviewer still asks you to write, write it.

Class LRUCache {/ / HashMap: / / LinkedList: public static class Node {int key; int val; Node next; Node prev; public Node (int key, int val) {this.key = key; this.val = val;}} Map map = new HashMap (); private Node head; private Node tail; private int cap; public LRUCache (int capacity) {cap = capacity } public int get (int key) {Node node = map.get (key); if (node = = null) {return-1;} else {int res = node.val; remove (node); appendHead (node); return res }} public void put (int key, int value) {/ / first check has this key Node node = map.get (key); if (node! = null) {node.val = value; / / put this node first to remove (node); appendHead (node);} else {node = new Node (key, value) If (map.size () < cap) {appendHead (node); map.put (key, node);} else {/ / kick away the old map.remove (tail.key); remove (tail); appendHead (node); map.put (key, node) } private void appendHead (Node node) {if (head = = null) {head = tail = node;} else {node.next = head; head.prev = node; head = node }} private void remove (Node node) {/ / what I wrote here may not be the most elegant, but very readable if (head = = tail) {head = tail = null;} else {if (head = = node) {head = head.next; node.next = null } else if (tail = = node) {tail = tail.prev; tail.next = null; node.prev = null;} else {node.prev.next = node.next; node.next.prev = node.prev; node.prev = null; node.next = null } / * Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache (capacity); * int param_1 = obj.get (key); * obj.put (key,value); * / so far, I believe you have a better understanding of "how to add new information to HashMap and LinkedList". Let's do it in practice! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.