詳解Java實(shí)現(xiàn)緩存(LRU,FIFO)
現(xiàn)在軟件或者網(wǎng)頁的并發(fā)量越來越大了，大量請求直接操作數(shù)據(jù)庫會對數(shù)據(jù)庫造成很大的壓力，處理大量連接和請求就會需要很長時間，但是實(shí)際中百分之80的數(shù)據(jù)是很少更改的，這樣就可以引入緩存來進(jìn)行讀取，減少數(shù)據(jù)庫的壓力。
常用的緩存有Redis和memcached，但是有時候一些小場景就可以直接使用Java實(shí)現(xiàn)緩存，就可以滿足這部分服務(wù)的需求。
緩存主要有LRU和FIFO，LRU是Least Recently Used的縮寫，即最近最久未使用，F(xiàn)IFO就是先進(jìn)先出，下面就使用Java來實(shí)現(xiàn)這兩種緩存。
LRU
LRU緩存的思想
- 固定緩存大小，需要給緩存分配一個固定的大小。
- 每次讀取緩存都會改變緩存的使用時間，將緩存的存在時間重新刷新。
- 需要在緩存滿了后，將最近最久未使用的緩存刪除，再添加最新的緩存。
按照如上思想，可以使用LinkedHashMap來實(shí)現(xiàn)LRU緩存。
這是LinkedHashMap的一個構(gòu)造函數(shù)，傳入的第三個參數(shù)accessOrder為true的時候，就按訪問順序?qū)inkedHashMap排序，為false的時候就按插入順序，默認(rèn)是為false的。
當(dāng)把a(bǔ)ccessOrder設(shè)置為true后，就可以將最近訪問的元素置于最前面，這樣就可以滿足上述的第二點(diǎn)。
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
這是LinkedHashMap中另外一個方法，當(dāng)返回true的時候，就會remove其中最久的元素，可以通過重寫這個方法來控制緩存元素的刪除，當(dāng)緩存滿了后，就可以通過返回true刪除最久未被使用的元素，達(dá)到LRU的要求。這樣就可以滿足上述第三點(diǎn)要求。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
由于LinkedHashMap是為自動擴(kuò)容的，當(dāng)table數(shù)組中元素大于Capacity * loadFactor的時候，就會自動進(jìn)行兩倍擴(kuò)容。但是為了使緩存大小固定，就需要在初始化的時候傳入容量大小和負(fù)載因子。
為了使得到達(dá)設(shè)置緩存大小不會進(jìn)行自動擴(kuò)容，需要將初始化的大小進(jìn)行計(jì)算再傳入，可以將初始化大小設(shè)置為(緩存大小 / loadFactor) + 1，這樣就可以在元素?cái)?shù)目達(dá)到緩存大小時，也不會進(jìn)行擴(kuò)容了。這樣就解決了上述第一點(diǎn)問題。
通過上面分析，實(shí)現(xiàn)下面的代碼
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class LRU1<K, V> {
private final int MAX_CACHE_SIZE;
private final float DEFAULT_LOAD_FACTORY = 0.75f;
LinkedHashMap<K, V> map;
public LRU1(int cacheSize) {
MAX_CACHE_SIZE = cacheSize;
int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
/*
* 第三個參數(shù)設(shè)置為true，代表linkedlist按訪問順序排序，可作為LRU緩存
* 第三個參數(shù)設(shè)置為false，代表按插入順序排序，可作為FIFO緩存
*/
map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> 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();
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (Map.Entry<K, V> entry : map.entrySet()) {
stringBuilder.append(String.format("%s: %s ", entry.getKey(), entry.getValue()));
}
return stringBuilder.toString();
}
public static void main(String[] args) {
LRU1<Integer, Integer> lru1 = new LRU1<>(5);
lru1.put(1, 1);
lru1.put(2, 2);
lru1.put(3, 3);
System.out.println(lru1);
lru1.get(1);
System.out.println(lru1);
lru1.put(4, 4);
lru1.put(5, 5);
lru1.put(6, 6);
System.out.println(lru1);
}
}
運(yùn)行結(jié)果：
從運(yùn)行結(jié)果中可以看出，實(shí)現(xiàn)了LRU緩存的思想。
接著使用HashMap和鏈表來實(shí)現(xiàn)LRU緩存。
主要的思想和上述基本一致，每次添加元素或者讀取元素就將元素放置在鏈表的頭，當(dāng)緩存滿了之后，就可以將尾結(jié)點(diǎn)元素刪除，這樣就實(shí)現(xiàn)了LRU緩存。
這種方法中是通過自己編寫代碼移動結(jié)點(diǎn)和刪除結(jié)點(diǎn)，為了防止緩存大小超過限制，每次進(jìn)行put的時候都會進(jìn)行檢查，若緩存滿了則刪除尾部元素。
import java.util.HashMap;
/**
* 使用cache和鏈表實(shí)現(xiàn)緩存
*/
public class LRU2<K, V> {
private final int MAX_CACHE_SIZE;
private Entry<K, V> head;
private Entry<K, V> tail;
private HashMap<K, Entry<K, V>> cache;
public LRU2(int cacheSize) {
MAX_CACHE_SIZE = cacheSize;
cache = new HashMap<>();
}
public void put(K key, V value) {
Entry<K, V> entry = getEntry(key);
if (entry == null) {
if (cache.size() >= MAX_CACHE_SIZE) {
cache.remove(tail.key);
removeTail();
}
}
entry = new Entry<>();
entry.key = key;
entry.value = value;
moveToHead(entry);
cache.put(key, entry);
}
public V get(K key) {
Entry<K, V> entry = getEntry(key);
if (entry == null) {
return null;
}
moveToHead(entry);
return entry.value;
}
public void remove(K key) {
Entry<K, V> entry = getEntry(key);
if (entry != null) {
if (entry == head) {
Entry<K, V> next = head.next;
head.next = null;
head = next;
head.pre = null;
} else if (entry == tail) {
Entry<K, V> prev = tail.pre;
tail.pre = null;
tail = prev;
tail.next = null;
} else {
entry.pre.next = entry.next;
entry.next.pre = entry.pre;
}
cache.remove(key);
}
}
private void removeTail() {
if (tail != null) {
Entry<K, V> prev = tail.pre;
if (prev == null) {
head = null;
tail = null;
} else {
tail.pre = null;
tail = prev;
tail.next = null;
}
}
}
private void moveToHead(Entry<K, V> entry) {
if (entry == head) {
return;
}
if (entry.pre != null) {
entry.pre.next = entry.next;
}
if (entry.next != null) {
entry.next.pre = entry.pre;
}
if (entry == tail) {
Entry<K, V> prev = entry.pre;
if (prev != null) {
tail.pre = null;
tail = prev;
tail.next = null;
}
}
if (head == null || tail == null) {
head = tail = entry;
return;
}
entry.next = head;
head.pre = entry;
entry.pre = null;
head = entry;
}
private Entry<K, V> getEntry(K key) {
return cache.get(key);
}
private static class Entry<K, V> {
Entry<K, V> pre;
Entry<K, V> next;
K key;
V value;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
Entry<K, V> entry = head;
while (entry != null) {
stringBuilder.append(String.format("%s:%s ", entry.key, entry.value));
entry = entry.next;
}
return stringBuilder.toString();
}
public static void main(String[] args) {
LRU2<Integer, Integer> lru2 = new LRU2<>(5);
lru2.put(1, 1);
System.out.println(lru2);
lru2.put(2, 2);
System.out.println(lru2);
lru2.put(3, 3);
System.out.println(lru2);
lru2.get(1);
System.out.println(lru2);
lru2.put(4, 4);
lru2.put(5, 5);
lru2.put(6, 6);
System.out.println(lru2);
}
}
運(yùn)行結(jié)果：
FIFO
FIFO就是先進(jìn)先出，可以使用LinkedHashMap進(jìn)行實(shí)現(xiàn)。
當(dāng)?shù)谌齻€參數(shù)傳入為false或者是默認(rèn)的時候，就可以實(shí)現(xiàn)按插入順序排序，就可以實(shí)現(xiàn)FIFO緩存了。
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
實(shí)現(xiàn)代碼跟上述使用LinkedHashMap實(shí)現(xiàn)LRU的代碼基本一致，主要就是構(gòu)造函數(shù)的傳值有些不同。
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class LRU1<K, V> {
private final int MAX_CACHE_SIZE;
private final float DEFAULT_LOAD_FACTORY = 0.75f;
LinkedHashMap<K, V> map;
public LRU1(int cacheSize) {
MAX_CACHE_SIZE = cacheSize;
int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
/*
* 第三個參數(shù)設(shè)置為true，代表linkedlist按訪問順序排序，可作為LRU緩存
* 第三個參數(shù)設(shè)置為false，代表按插入順序排序，可作為FIFO緩存
*/
map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, false) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> 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();
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (Map.Entry<K, V> entry : map.entrySet()) {
stringBuilder.append(String.format("%s: %s ", entry.getKey(), entry.getValue()));
}
return stringBuilder.toString();
}
public static void main(String[] args) {
LRU1<Integer, Integer> lru1 = new LRU1<>(5);
lru1.put(1, 1);
lru1.put(2, 2);
lru1.put(3, 3);
System.out.println(lru1);
lru1.get(1);
System.out.println(lru1);
lru1.put(4, 4);
lru1.put(5, 5);
lru1.put(6, 6);
System.out.println(lru1);
}
}
運(yùn)行結(jié)果：
以上就是使用Java實(shí)現(xiàn)這兩種緩存的方式，從中可以看出，LinkedHashMap實(shí)現(xiàn)緩存較為容易，因?yàn)榈讓雍瘮?shù)對此已經(jīng)有了支持，自己編寫鏈表實(shí)現(xiàn)LRU緩存也是借鑒了LinkedHashMap中實(shí)現(xiàn)的思想。在Java中不只是這兩種數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)緩存，比如ConcurrentHashMap、WeakHashMap在某些場景下也是可以作為緩存的，到底用哪一種數(shù)據(jù)結(jié)構(gòu)主要是看場景再進(jìn)行選擇，但是很多思想都是可以通用的。
相關(guān)文章
本文主要介紹了java中常見的中文亂碼以及解決方法，主要包括字節(jié)碼文件讀取時出現(xiàn)的亂碼問題，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有很好的參考價值，感興趣的朋友跟隨小編一起看看吧2017-03-03
JVM性能調(diào)優(yōu)實(shí)戰(zhàn):讓你的IntelliJ Idea縱享絲滑
這篇文章主要介紹了JVM性能調(diào)優(yōu)實(shí)戰(zhàn):讓你的IntelliJ Idea縱享絲滑的相關(guān)資料,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
這篇文章主要介紹了快速搭建SSM框架（Maven）五步曲的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10
如何用ObjectMapper將復(fù)雜Map轉(zhuǎn)換為實(shí)體類
這篇文章主要介紹了如何用ObjectMapper將復(fù)雜Map轉(zhuǎn)換為實(shí)體類的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
EhCache是一個比較成熟的Java緩存框架，Springboot對ehcache的使用非常支持，所以在Springboot中只需做些配置就可使用，且使用方式也簡易，今天給大家分享springboot ehcache 配置使用教程，一起看看吧2021-06-06
這篇文章主要介紹了Java多線程中的Phaser使用解析,java多線程技術(shù)提供了Phaser工具類,Phaser表示“階段器”,用來解決控制多個線程分階段共同完成任務(wù)的情景問題,其作用相比CountDownLatch和CyclicBarrier更加靈活,需要的朋友可以參考下2023-11-11
Spring中ApplicationEventPublisher發(fā)布訂閱模式的實(shí)現(xiàn)
本文主要介紹了Spring中ApplicationEventPublisher發(fā)布訂閱模式的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
下面小編就為大家?guī)硪黄赒uartz定時調(diào)度任務(wù)(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-11-11
本文主要給大家簡單講解了一下java的發(fā)展史，詳細(xì)說明了java的由來以及如何一步步發(fā)展起來的，想了解的小伙伴可以來參考下2016-10-10
這篇文章主要介紹了Spring Boot設(shè)置支持跨域請求過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08