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

The main content of this article is to explain "what is the LRU implementation of Java with expiration time", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what is the LRU implementation of Java with expiration time"?

What is LRU

The full name of LRU is Least Recently Used, which means that it has not been used for the longest time recently. In other words: if a data has not been used recently, it is less likely to be used in the future.

A common usage scenario is caching, such as the page replacement algorithm in the operating system. There are many plans to achieve, I read a lot of blogs, most of which are given four or five kinds. Here, for the sake of brevity, only one is given, with an expiration time. Other implementations are similar, leave it to the smart you!

Solution: using linked list plus HashMap

Every time you have a new data, first determine whether it is contained in the map. If so, move it to the head of the line. If not, create a new node, and then put it in. For the function with expiration time, you only need to put an expiration time for each node, and delete it as long as it arrives at this time.

There is another problem: locks should be added in a multithreaded environment. In order to ensure the flexibility of locks, we use ConcurrentHashMap.

OK, let's start to implement:

Second, code implementation

1. Define the node

/ / this Node pair uses each node in the HashMap class Node implements Comparable {private String key; private Object value; private long expireTime;// Note that the expiration time is a point in time, such as 11:11 public Node (String key, Object value, long expireTime) {this.value = value; this.key = key; this.expireTime = expireTime } / / sort by expiration time @ Override public int compareTo (Node o) {long r = this.expireTime-o.expireTime; if (r > 0) return 1; if (r

< 0) return -1; return 0; } } 2、LRU实现 public class LRU { // 变量1：用于设置清除过期数据的线程池 private static ScheduledExecutorService swapExpiredPool = new ScheduledThreadPoolExecutor(10); // 变量2：用户存储数据,为了保证线程安全，使用了ConcurrentHashMap private ConcurrentHashMap cache = new ConcurrentHashMap(1024); // 变量3：保存最新的过期数据，过期时间最小的数据排在队列前 private PriorityQueue expireQueue = new PriorityQueue(1024); // 构造方法：只要有缓存了，过期清除线程就开始工作 public LRU() { swapExpiredPool.scheduleWithFixedDelay(new ExpiredNode(), 3,3,TimeUnit.SECONDS); } //还有代码。。。。。。。 } 现在我们定义了几个变量，然后还有一个构造方法，意思是只要启动了这个LRU，就开始清除。清除的线程是ExpiredNode。我们来看一下： 3、过期清除线程方法 这个方法也就是ExpiredNode，当做一个内部类在LRU中。 public class ExpiredNode implements Runnable { @Override public void run() { // 第一步：获取当前的时间 long now = System.currentTimeMillis(); while (true) { // 第二步：从过期队列弹出队首元素，如果不存在，或者不过期就返回 Node node = expireQueue.peek(); if (node == null || node.expireTime >

Now) return; / / step 3: delete it from the cache when it expires, and pop up cache.remove (node.key); expireQueue.poll ();} / / this process is while (true), always judge and delete}}

Now that you know how to clear the expiration date, let's take a look at how to add data.

4. Set method

Public Object set (String key, Object value, long ttl) {/ / first step: get the expiration time point long expireTime = System.currentTimeMillis () + ttl; / / step 2: create a new node Node newNode = newNode (key, value, expireTime) / / step 3: overwrite if there is something in cache, add a new one if not, add Node old = cache.put (key, newNode); expireQueue.add (newNode); / / step 4: if data exists in the key, delete if (old! = null) {expireQueue.remove (old) from the expiration queue Return old.value;} return null;}

5. Get method

This method is relatively simple, just get it directly.

Public Object get (String key) {/ / first step: get directly from cache, note that the cache is a HashMap Node n = cache.get (key); / / step 2: return null if n is empty, and return the corresponding value return n = null if not empty? Null: n.value;}

Note that the code of the above 345 is stored in LRU.

We already know the expiration time, in fact, we add an expiration time queue and a thread to clear the expiration date, and use while (true) to determine whether the head of the queue expires each time, and then determine whether to return and clear. When setting the method, add the new node to the queue and remove the old one. And we use ConcurrentHashMap to ensure thread safety.

At this point, I believe you have a deeper understanding of "what is the implementation of LRU with expiration time in Java". You might as well 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.