av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁技術(shù)文章
文章詳情頁

詳解Java實(shí)現(xiàn)LRU緩存

瀏覽:69日期:2022-08-27 15:50:20

LRU是Least Recently Used 的縮寫,翻譯過來就是“最近最少使用”,LRU緩存就是使用這種原理實(shí)現(xià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)簡單的擴(kuò)展,擴(kuò)展方式有兩種,一種是inheritance,一種是delegation,具體使用什么方式看個(gè)人喜好

//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)比較簡單,而且實(shí)現(xiàn)了Map接口,在多線程環(huán)境使用時(shí)可以使用Collections.synchronizedMap()方法實(shí)現(xiàn)線程安全操作

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è)類的麻煩

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接口,所以線程同步就需要自己搞定了

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)線程安全操作

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緩存,簡化版的實(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; }};

調(diào)用示例

測(cè)試代碼

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é)果

'C:Program Files (x86)Javajdk1.6.0_10binjava' -Didea.launcher.port=7535 '-Didea.launcher.bin.path=C:Program Files (x86)JetBrainsIntelliJ IDEA 13.0.2bin' -Dfile.encoding=UTF-8 -classpath 'C:Program Files (x86)Javajdk1.6.0_10jrelibcharsets.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibdeploy.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibjavaws.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibjce.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibjsse.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibmanagement-agent.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibplugin.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibresources.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibrt.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextdnsns.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextlocaledata.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextsunjce_provider.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextsunmscapi.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextsunpkcs11.jar;D:SVNprojectsJavaJava.Algorithmtargettest-classes;D:SVNprojectsJavaJava.Algorithmtargetclasses;C:Program Files (x86)JetBrainsIntelliJ IDEA 13.0.2libidea_rt.jar' com.intellij.rt.execution.application.AppMain Mainstart...===========================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

到此這篇關(guān)于詳解Java實(shí)現(xiàn)LRU緩存的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)LRU緩存內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)!

標(biāo)簽: Java
相關(guān)文章:
主站蜘蛛池模板: 亚洲高清在线视频 | 亚洲一区中文字幕在线观看 | 亚洲一区二区三区乱码aⅴ 四虎在线视频 | 伊人久久在线 | 成人黄视频在线观看 | 国产乱码一二三区精品 | 日本久久精品视频 | 中文字幕日韩一区 | 国产欧美在线视频 | 中文字字幕在线中文乱码范文 | 日韩黄a| 久久精品国产亚洲 | 免费麻豆视频 | 美女视频黄的免费 | 久草网站 | 天天色官网 | 亚洲精品久久久久中文字幕欢迎你 | 亚洲精品视频一区二区三区 | 久久国产美女视频 | 在线亚洲电影 | 中文字幕在线观看国产 | 亚洲一区二区 | 日韩视频精品在线 | 亚洲视频一区二区三区 | 日韩在线精品视频 | 久久99精品久久久久久琪琪 | 久久精品免费一区二区 | 美女久久久久久久 | 久久久久久久一区二区三区 | 极品国产视频 | 亚洲免费久久久 | 久久极品 | 日本精品一区二区三区在线观看视频 | 91在线网站 | 成人a在线 | 国产精品久久久久久久久久尿 | 国产成人亚洲精品自产在线 | 91在线视频在线观看 | 色婷婷影院 | 久久久久久久久久久福利观看 | 精品一二三区 |