一区二区三区在线-一区二区三区亚洲视频-一区二区三区亚洲-一区二区三区午夜-一区二区三区四区在线视频-一区二区三区四区在线免费观看

服務(wù)器之家：專注于服務(wù)器技術(shù)及軟件下載分享
分類導(dǎo)航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|編程技術(shù)|正則表達(dá)式|

服務(wù)器之家 - 編程語言 - JAVA教程 - java LRU(Least Recently Used )詳解及實(shí)例代碼

java LRU(Least Recently Used )詳解及實(shí)例代碼

2020-07-08 13:47懶惰的肥兔 JAVA教程

這篇文章主要介紹了java LRU(Least Recently Used )詳解及實(shí)例代碼的相關(guān)資料,Java里面實(shí)現(xiàn)LRU緩存通常有兩種選擇，一種是使用LinkedHashMap，一種是自己設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，使用鏈表+HashMap，需要的朋友可以參考下

java LRU(Least Recently Used )詳解

LRU是Least Recently Used 的縮寫，翻譯過來就是“最近最少使用”，LRU緩存就是使用這種原理實(shí)現(xiàn)，簡(jiǎn)單的說就是緩存一定量的數(shù)據(jù)，當(dāng)超過設(shè)定的閾值時(shí)就把一些過期的數(shù)據(jù)刪除掉，比如我們緩存10000條數(shù)據(jù)，當(dāng)數(shù)據(jù)小于10000時(shí)可以隨意添加，當(dāng)超過10000時(shí)就需要把新的數(shù)據(jù)添加進(jìn)來，同時(shí)要把過期數(shù)據(jù)刪除，以確保我們最大緩存10000條，那怎么確定刪除哪條過期數(shù)據(jù)呢，采用LRU算法實(shí)現(xiàn)的話就是將最老的數(shù)據(jù)刪掉，廢話不多說，下面來說下Java版的LRU緩存實(shí)現(xiàn)

Java里面實(shí)現(xiàn)LRU緩存通常有兩種選擇，一種是使用LinkedHashMap，一種是自己設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，使用鏈表+HashMap

LRU Cache的LinkedHashMap實(shí)現(xiàn)

LinkedHashMap自身已經(jīng)實(shí)現(xiàn)了順序存儲(chǔ)，默認(rèn)情況下是按照元素的添加順序存儲(chǔ)，也可以啟用按照訪問順序存儲(chǔ)，即最近讀取的數(shù)據(jù)放在最前面，最早讀取的數(shù)據(jù)放在最后面，然后它還有一個(gè)判斷是否刪除最老數(shù)據(jù)的方法，默認(rèn)是返回false，即不刪除數(shù)據(jù)，我們使用LinkedHashMap實(shí)現(xiàn)LRU緩存的方法就是對(duì)LinkedHashMap實(shí)現(xiàn)簡(jiǎn)單的擴(kuò)展，擴(kuò)展方式有兩種，一種是inheritance，一種是delegation，具體使用什么方式看個(gè)人喜好

?
1
2
3
4
5
6
7
8
9
10
11
//LinkedHashMap的一個(gè)構(gòu)造函數(shù)，當(dāng)參數(shù)accessOrder為true時(shí)，即會(huì)按照訪問順序排序，最近訪問的放在最前，最早訪問的放在后面
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
 
//LinkedHashMap自帶的判斷是否刪除最老的元素方法，默認(rèn)返回false，即不刪除老數(shù)據(jù)
//我們要做的就是重寫這個(gè)方法，當(dāng)滿足一定條件時(shí)刪除老數(shù)據(jù)
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

LRU緩存LinkedHashMap(inheritance)實(shí)現(xiàn)

采用inheritance方式實(shí)現(xiàn)比較簡(jiǎn)單，而且實(shí)現(xiàn)了Map接口，在多線程環(huán)境使用時(shí)可以使用 Collections.synchronizedMap()方法實(shí)現(xiàn)線程安全操作

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package cn.lzrabbit.structure.lru;
 
import java.util.LinkedHashMap;
import java.util.Map;
 
/**
 * Created by liuzhao on 14-5-15.
 */
public class LRUCache2<K, V> extends LinkedHashMap<K, V> {
  private final int MAX_CACHE_SIZE;
 
  public LRUCache2(int cacheSize) {
    super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
    MAX_CACHE_SIZE = cacheSize;
  }
 
  @Override
  protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_CACHE_SIZE;
  }
 
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    for (Map.Entry<K, V> entry : entrySet()) {
      sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
    }
    return sb.toString();
  }
}

 這樣算是比較標(biāo)準(zhǔn)的實(shí)現(xiàn)吧，實(shí)際使用中這樣寫還是有些繁瑣，更實(shí)用的方法時(shí)像下面這樣寫，省去了單獨(dú)見一個(gè)類的麻煩

?
1
2
3
4
5
6
7
final int cacheSize = 100;
Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {
  @Override
  protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
  return size() > cacheSize;
  }
};

 LRU緩存LinkedHashMap(delegation)實(shí)現(xiàn)

delegation方式實(shí)現(xiàn)更加優(yōu)雅一些，但是由于沒有實(shí)現(xiàn)Map接口，所以線程同步就需要自己搞定了

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package cn.lzrabbit.structure.lru;
 
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
 
/**
 * Created by liuzhao on 14-5-13.
 */
public class LRUCache3<K, V> {
 
  private final int MAX_CACHE_SIZE;
  private final float DEFAULT_LOAD_FACTOR = 0.75f;
  LinkedHashMap<K, V> map;
 
  public LRUCache3(int cacheSize) {
    MAX_CACHE_SIZE = cacheSize;
    //根據(jù)cacheSize和加載因子計(jì)算hashmap的capactiy，+1確保當(dāng)達(dá)到cacheSize上限時(shí)不會(huì)觸發(fā)hashmap的擴(kuò)容，
    int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;
    map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, true) {
      @Override
      protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_CACHE_SIZE;
      }
    };
  }
 
  public synchronized void put(K key, V value) {
    map.put(key, value);
  }
 
  public synchronized V get(K key) {
    return map.get(key);
  }
 
  public synchronized void remove(K key) {
    map.remove(key);
  }
 
  public synchronized Set<Map.Entry<K, V>> getAll() {
    return map.entrySet();
  }
 
  public synchronized int size() {
    return map.size();
  }
 
  public synchronized void clear() {
    map.clear();
  }
 
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    for (Map.Entry entry : map.entrySet()) {
      sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
    }
    return sb.toString();
  }
}

 LRU Cache的鏈表+HashMap實(shí)現(xiàn)

 注：此實(shí)現(xiàn)為非線程安全，若在多線程環(huán)境下使用需要在相關(guān)方法上添加synchronized以實(shí)現(xiàn)線程安全操作

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
package cn.lzrabbit.structure.lru;
 
 
import java.util.HashMap;
 
/**
 * Created by liuzhao on 14-5-12.
 */
public class LRUCache1<K, V> {
 
  private final int MAX_CACHE_SIZE;
  private Entry first;
  private Entry last;
 
  private HashMap<K, Entry<K, V>> hashMap;
 
  public LRUCache1(int cacheSize) {
    MAX_CACHE_SIZE = cacheSize;
    hashMap = new HashMap<K, Entry<K, V>>();
  }
 
  public void put(K key, V value) {
    Entry entry = getEntry(key);
    if (entry == null) {
      if (hashMap.size() >= MAX_CACHE_SIZE) {
        hashMap.remove(last.key);
        removeLast();
      }
      entry = new Entry();
      entry.key = key;
    }
    entry.value = value;
    moveToFirst(entry);
    hashMap.put(key, entry);
  }
 
  public V get(K key) {
    Entry<K, V> entry = getEntry(key);
    if (entry == null) return null;
    moveToFirst(entry);
    return entry.value;
  }
 
  public void remove(K key) {
    Entry entry = getEntry(key);
    if (entry != null) {
      if (entry.pre != null) entry.pre.next = entry.next;
      if (entry.next != null) entry.next.pre = entry.pre;
      if (entry == first) first = entry.next;
      if (entry == last) last = entry.pre;
    }
    hashMap.remove(key);
  }
 
  private void moveToFirst(Entry entry) {
    if (entry == first) return;
    if (entry.pre != null) entry.pre.next = entry.next;
    if (entry.next != null) entry.next.pre = entry.pre;
    if (entry == last) last = last.pre;
 
    if (first == null || last == null) {
      first = last = entry;
      return;
    }
 
    entry.next = first;
    first.pre = entry;
    first = entry;
    entry.pre = null;
  }
 
  private void removeLast() {
    if (last != null) {
      last = last.pre;
      if (last == null) first = null;
      else last.next = null;
    }
  }
 
 
  private Entry<K, V> getEntry(K key) {
    return hashMap.get(key);
  }
 
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    Entry entry = first;
    while (entry != null) {
      sb.append(String.format("%s:%s ", entry.key, entry.value));
      entry = entry.next;
    }
    return sb.toString();
  }
 
  class Entry<K, V> {
    public Entry pre;
    public Entry next;
    public K key;
    public V value;
  }
}

LinkedHashMap的FIFO實(shí)現(xiàn)

FIFO是First Input First Output的縮寫，也就是常說的先入先出，默認(rèn)情況下LinkedHashMap就是按照添加順序保存，我們只需重寫下removeEldestEntry方法即可輕松實(shí)現(xiàn)一個(gè)FIFO緩存，簡(jiǎn)化版的實(shí)現(xiàn)代碼如下

?
1
2
3
4
5
6
7
final int cacheSize = 5;
LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {
  @Override
  protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
  return size() > cacheSize;
  }
};

調(diào)用示例

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package cn.lzrabbit.structure.lru;
 
import cn.lzrabbit.ITest;
 
import java.util.LinkedHashMap;
import java.util.Map;
 
/**
 * Created by liuzhao on 14-5-15.
 */
public class LRUCacheTest {
 
  public static void main(String[] args) throws Exception {
    System.out.println("start...");
 
    lruCache1();
    lruCache2();
    lruCache3();
    lruCache4();
   
    System.out.println("over...");
  }
 
 
 static  void lruCache1() {
    System.out.println();
    System.out.println("===========================LRU 鏈表實(shí)現(xiàn)===========================");
    LRUCache1<Integer, String> lru = new LRUCache1(5);
    lru.put(1, "11");
    lru.put(2, "11");
    lru.put(3, "11");
    lru.put(4, "11");
    lru.put(5, "11");
    System.out.println(lru.toString());
    lru.put(6, "66");
    lru.get(2);
    lru.put(7, "77");
    lru.get(4);
    System.out.println(lru.toString());
    System.out.println();
  }
 
 
static  <T> void lruCache2() {
    System.out.println();
    System.out.println("===========================LRU LinkedHashMap(inheritance)實(shí)現(xiàn)===========================");
    LRUCache2<Integer, String> lru = new LRUCache2(5);
    lru.put(1, "11");
    lru.put(2, "11");
    lru.put(3, "11");
    lru.put(4, "11");
    lru.put(5, "11");
    System.out.println(lru.toString());
    lru.put(6, "66");
    lru.get(2);
    lru.put(7, "77");
    lru.get(4);
    System.out.println(lru.toString());
    System.out.println();
  }
 
 static void lruCache3() {
    System.out.println();
    System.out.println("===========================LRU LinkedHashMap(delegation)實(shí)現(xiàn)===========================");
    LRUCache3<Integer, String> lru = new LRUCache3(5);
    lru.put(1, "11");
    lru.put(2, "11");
    lru.put(3, "11");
    lru.put(4, "11");
    lru.put(5, "11");
    System.out.println(lru.toString());
    lru.put(6, "66");
    lru.get(2);
    lru.put(7, "77");
    lru.get(4);
    System.out.println(lru.toString());
    System.out.println();
  }
 
 static void lruCache4() {
    System.out.println();
    System.out.println("===========================FIFO LinkedHashMap默認(rèn)實(shí)現(xiàn)===========================");
    final int cacheSize = 5;
    LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() {
      @Override
      protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > cacheSize;
      }
    };
    lru.put(1, "11");
    lru.put(2, "11");
    lru.put(3, "11");
    lru.put(4, "11");
    lru.put(5, "11");
    System.out.println(lru.toString());
    lru.put(6, "66");
    lru.get(2);
    lru.put(7, "77");
    lru.get(4);
    System.out.println(lru.toString());
    System.out.println();
  }
 
}

運(yùn)行結(jié)果

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"C:\Program Files (x86)\Java\jdk1.6.0_10\bin\java" -Didea.launcher.port=7535 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\charsets.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\deploy.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\javaws.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jce.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jsse.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\management-agent.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\plugin.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\resources.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\rt.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\dnsns.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\localedata.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunjce_provider.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunmscapi.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunpkcs11.jar;D:\SVN\projects\Java\Java.Algorithm\target\test-classes;D:\SVN\projects\Java\Java.Algorithm\target\classes;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain Main
start...
 
===========================LRU 鏈表實(shí)現(xiàn)===========================
5:11 4:11 3:11 2:11 1:11
4:11 7:77 2:11 6:66 5:11
 
 
===========================LRU LinkedHashMap(inheritance)實(shí)現(xiàn)===========================
1:11 2:11 3:11 4:11 5:11
5:11 6:66 2:11 7:77 4:11
 
 
===========================LRU LinkedHashMap(delegation)實(shí)現(xiàn)===========================
1:11 2:11 3:11 4:11 5:11
5:11 6:66 2:11 7:77 4:11
 
 
===========================FIFO LinkedHashMap默認(rèn)實(shí)現(xiàn)===========================
{1=11, 2=11, 3=11, 4=11, 5=11}
{3=11, 4=11, 5=11, 6=66, 7=77}
 
over...
 
Process finished with exit code 0

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

原文鏈接：http://www.cnblogs.com/lzrabbit/p/3734850.html

延伸 · 閱讀

精彩推薦
主站蜘蛛池模板： 无限国产资源 | xxoo做爰猛烈动态 | 国产理论片在线观看 | 91视在线国内在线播放酒店 | 精品suv一区二区三区 | 国产情侣偷国语对白 | 交换朋友夫妇3中文字幕 | 亚洲天堂中文 | 国产91在线免费 | 精品欧美一区二区在线观看欧美熟 | 国产精品一久久香蕉产线看 | 免费又爽又黄禁片视频在线播放 | 日韩在线视频免费观看 | 二区三区在线观看 | 美女和男人免费网站视频 | 日本艳鉧动漫1～6在线观看 | 国产剧情一区 | 91混血大战上海双胞胎 | 特黄特色一级aa毛片免费观看 | 日日射视频 | 亚洲午夜久久久久国产 | 欧美贵妇vs高跟办公室 | 日本视频观看 | 高跟丝袜麻麻求我调教 | 午夜影视在线观看 | 韩国黄色网址 | 蘑菇香蕉茄子绿巨人丝瓜草莓 | 男人操女人免费视频 | 九九精品视频在线观看 | 久久精品美女 | 日本三级做a全过程在线观看 | 国模娜娜a4u1546全套 | 呜嗯啊野战h呻吟男男双性 污小说在线阅读 | 国产成人亚洲综合网站不卡 | 四虎影视入口 | 小寡妇好紧进去了好大看视频 | 日韩欧美中文在线 | 国产美女久久精品香蕉69 | 免费观看大片毛片 | 日本精品vide·ssex日本 | 美女模特被c免费视频 |