Java帶有過(guò)期時(shí)間的LRU實(shí)現(xiàn)方法是什么

本篇內(nèi)容主要講解“Java帶有過(guò)期時(shí)間的LRU實(shí)現(xiàn)方法是什么”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Java帶有過(guò)期時(shí)間的LRU實(shí)現(xiàn)方法是什么”吧!

一、什么是LRU

LRU全稱是Least Recently  Used，即最近最久未使用的意思。也就是說(shuō)：如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒(méi)有被使用，將來(lái)被使用的機(jī)會(huì)也比較小。

通常的使用場(chǎng)景就是緩存，比如說(shuō)操作系統(tǒng)中的頁(yè)面置換算法。實(shí)現(xiàn)的方案有很多，我看了很多博客，大多是給了四五種。這里為了簡(jiǎn)潔，只給出一種，是帶有過(guò)期時(shí)間的。其他的實(shí)現(xiàn)類似，就交給聰明的你吧!!

解決方案：利用鏈表加HashMap

每次來(lái)一個(gè)新數(shù)據(jù)，首先判斷map中是否含有，有的話就移動(dòng)到隊(duì)頭，沒(méi)有的話就新建一個(gè)節(jié)點(diǎn)，然后放進(jìn)來(lái)就好，對(duì)于帶過(guò)期時(shí)間的功能，只需要為每一個(gè)節(jié)點(diǎn)放一個(gè)過(guò)期時(shí)間，只要到了這個(gè)時(shí)間就直接刪除即可。

還有一個(gè)問(wèn)題：多線程環(huán)境下應(yīng)該加鎖，為了保證鎖的靈活性，我們使用ConcurrentHashMap。

OK，下面我們就開(kāi)始實(shí)現(xiàn)：

二、代碼實(shí)現(xiàn)

1、定義節(jié)點(diǎn)

//這個(gè)Node對(duì)用HashMap中每一個(gè)節(jié)點(diǎn) class Node implements Comparable<Node> {     private String key;     private Object value;     private long expireTime;//注意這個(gè)過(guò)期時(shí)間是一個(gè)時(shí)間點(diǎn)，如11點(diǎn)11分     public Node(String key, Object value, long expireTime) {         this.value = value;         this.key = key;         this.expireTime = expireTime;     }     //按照過(guò)期時(shí)間進(jìn)行排序     @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實(shí)現(xiàn)

public class LRU {     // 變量1：用于設(shè)置清除過(guò)期數(shù)據(jù)的線程池     private static ScheduledExecutorService swapExpiredPool                    = new ScheduledThreadPoolExecutor(10);     // 變量2：用戶存儲(chǔ)數(shù)據(jù),為了保證線程安全，使用了ConcurrentHashMap     private ConcurrentHashMap<String, Node> cache = new ConcurrentHashMap<>(1024);     // 變量3：保存最新的過(guò)期數(shù)據(jù)，過(guò)期時(shí)間最小的數(shù)據(jù)排在隊(duì)列前     private PriorityQueue<Node> expireQueue = new PriorityQueue<>(1024);     // 構(gòu)造方法：只要有緩存了，過(guò)期清除線程就開(kāi)始工作     public LRU() {         swapExpiredPool.scheduleWithFixedDelay(new ExpiredNode(), 3,3,TimeUnit.SECONDS);     }     //還有代碼。。。。。。。 }

現(xiàn)在我們定義了幾個(gè)變量，然后還有一個(gè)構(gòu)造方法，意思是只要啟動(dòng)了這個(gè)LRU，就開(kāi)始清除。清除的線程是ExpiredNode。我們來(lái)看一下：

3、過(guò)期清除線程方法

這個(gè)方法也就是ExpiredNode，當(dāng)做一個(gè)內(nèi)部類在LRU中。

public class ExpiredNode implements Runnable {         @Override         public void run() {             // 第一步：獲取當(dāng)前的時(shí)間             long now = System.currentTimeMillis();             while (true) {                 // 第二步：從過(guò)期隊(duì)列彈出隊(duì)首元素，如果不存在，或者不過(guò)期就返回                 Node node = expireQueue.peek();                 if (node == null || node.expireTime > now)return;                 // 第三步：過(guò)期了那就從緩存中刪除，并且還要從隊(duì)列彈出                 cache.remove(node.key);                 expireQueue.poll();             }// 此過(guò)程為while(true)，一直進(jìn)行判斷和刪除操作         }     }

現(xiàn)在知道了過(guò)期清除方法，下面看看如何添加數(shù)據(jù)。

4、set方法

public Object set(String key, Object value, long ttl) {         // 第一步：獲取過(guò)期時(shí)間點(diǎn)         long expireTime = System.currentTimeMillis() + ttl;         // 第二步：新建一個(gè)節(jié)點(diǎn)         Node newNode = new Node(key, value, expireTime);         // 第三步：cache中有的話就覆蓋，沒(méi)有就添加新的，過(guò)期時(shí)間隊(duì)列也要添加         Node old = cache.put(key, newNode);         expireQueue.add(newNode);         // 第四步：如果該key存在數(shù)據(jù)，還要從過(guò)期時(shí)間隊(duì)列刪除         if (old != null) {             expireQueue.remove(old);             return old.value;         }         return null;     }

5、get方法

這個(gè)方法就比較簡(jiǎn)單了，直接獲取即可。

public Object get(String key) {     //第一步：從cache直接獲取，注意這個(gè)cache是一個(gè)HashMap     Node n = cache.get(key);     //第二步：如果n為空那就返回為null,不為空就返回相應(yīng)的值     return n == null ? null : n.value; }

注意以上345的代碼都存放在LRU中。

過(guò)期時(shí)間的我們已經(jīng)知道了，其實(shí)就是添加了一個(gè)過(guò)期時(shí)間隊(duì)列，和一個(gè)過(guò)期清除的線程，清除的時(shí)候使用while(true)每次判斷隊(duì)列隊(duì)首是否過(guò)期，然后判斷是否返回和清除。設(shè)置方法的時(shí)候還要把新的node添加到queue，把舊的移除掉。而且我們使用了ConcurrentHashMap保證了線程安全。

到此，相信大家對(duì)“Java帶有過(guò)期時(shí)間的LRU實(shí)現(xiàn)方法是什么”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！