日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
帶有過期時(shí)間的LRU實(shí)現(xiàn)（Java版）

在很早之前學(xué)操作系統(tǒng)的時(shí)候見過這個(gè)算法，后來見到的越來越多，以至于刷面經(jīng)的時(shí)候也看到了，總結(jié)一下：

創(chuàng)新互聯(lián)專注于北侖網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供北侖營(yíng)銷型網(wǎng)站建設(shè)，北侖網(wǎng)站制作、北侖網(wǎng)頁設(shè)計(jì)、北侖網(wǎng)站官網(wǎng)定制、微信平臺(tái)小程序開發(fā)服務(wù)，打造北侖網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供北侖網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。

一、什么是LRU

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

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

解決方案：利用鏈表加HashMap

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

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

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

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

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

 
 
 
 
    
  
  
  
  
  1. //這個(gè)Node對(duì)用HashMap中每一個(gè)節(jié)點(diǎn)
    2. 
  
  
  
  
  2. class Node implements Comparable {
    3. 
  
  
  
  
  3.     private String key;
    4. 
  
  
  
  
  4.     private Object value;
    5. 
  
  
  
  
  5.     private long expireTime;//注意這個(gè)過期時(shí)間是一個(gè)時(shí)間點(diǎn)，如11點(diǎn)11分
    6. 
  
  
  
  
  6.     public Node(String key, Object value, long expireTime) {
    7. 
  
  
  
  
  7.         this.value = value;
    8. 
  
  
  
  
  8.         this.key = key;
    9. 
  
  
  
  
  9.         this.expireTime = expireTime;
    10. 
  
  
  
  
  10.     }
    11. 
  
  
  
  
  11.     //按照過期時(shí)間進(jìn)行排序
    12. 
  
  
  
  
  12.     @Override
    13. 
  
  
  
  
  13.     public int compareTo(Node o) {
    14. 
  
  
  
  
  14.         long r = this.expireTime - o.expireTime;
    15. 
  
  
  
  
  15.         if (r > 0)  return 1;
    16. 
  
  
  
  
  16.         if (r < 0) return -1;
    17. 
  
  
  
  
  17.         return 0;
    18. 
  
  
  
  
  18.     }
    19. 
  
  
  
  
  19. }
    20.

2、LRU實(shí)現(xiàn)

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

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

3、過期清除線程方法

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

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

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

4、set方法

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

5、get方法

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

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

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

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

本文轉(zhuǎn)載自微信公眾號(hào)「 愚公要移山」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系 愚公要移山公眾號(hào)。

OK，今天的代碼就先寫到這。


文章名稱：帶有過期時(shí)間的LRU實(shí)現(xiàn)（Java版）
網(wǎng)站網(wǎng)址：http://m.5511xx.com/article/dpsggsc.html