詳解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)行計算再傳入，可以將初始化大小設(shè)置為(緩存大小 / loadFactor) + 1，這樣就可以在元素數(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)文章
平衡二叉樹又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。本文將詳解介紹一下平衡二叉樹的原理與實(shí)現(xiàn)，需要的可以參考一下2022-06-06
在軟件開發(fā)過程中，經(jīng)常需要生成Excel文件來導(dǎo)出數(shù)據(jù)或者生成報表，為了簡化開發(fā)流程和提高代碼的可維護(hù)性，我們可以使用Spring Boot封裝Excel生成器，本文將介紹如何使用Spring Boot封裝Excel生成器，并提供一些示例代碼來說明其用法和功能2023-06-06
java中實(shí)現(xiàn)list或set轉(zhuǎn)map的方法
這篇文章主要介紹了java中實(shí)現(xiàn)list或set轉(zhuǎn)map的方法的相關(guān)資料,需要的朋友可以參考下2017-01-01
java.util.List接口繼承自Collection接口,是單列集合的一個重要分支,習(xí)慣性地會將實(shí)現(xiàn)了List接口的對象稱為List集合,下面這篇文章主要給大家介紹了關(guān)于java中List集合子類特點(diǎn)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-01-01
自旋鎖是專為防止多處理器并發(fā)而引入的一種鎖，它在內(nèi)核中大量應(yīng)用于中斷處理等部分。本文將用Java實(shí)現(xiàn)手寫自旋鎖，需要的可以參考一下2022-08-08
Java語言實(shí)現(xiàn)基數(shù)排序代碼分享
這篇文章主要介紹了Java語言實(shí)現(xiàn)基數(shù)排序代碼分享，具有一定借鑒價值，需要的朋友可以參考下。2017-12-12
在Java中,? extends Type是一個上界通配符,本文主要介紹了java上界通配符(? extends Type)的使用,具有一定的參考價值,感興趣的可以了解一下2024-01-01
在SpringBoot環(huán)境中使用Mockito進(jìn)行單元測試的示例詳解
Mockito特別適用于在Spring Boot環(huán)境中進(jìn)行單元測試,因?yàn)樗軌蜉p松模擬Spring應(yīng)用中的服務(wù)、存儲庫、客戶端和其他組件,通過使用Mockito,開發(fā)者可以模擬外部依賴,從而使單元測試更加獨(dú)立和可靠,本文給大家介紹了在Spring Boot環(huán)境中使用Mockito進(jìn)行單元測試2024-01-01
這篇文章主要介紹了Java冒泡排序法和選擇排序法的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
項(xiàng)目開發(fā)中對于一些數(shù)據(jù)的處理需要用到多線程，比如文件的批量上傳，數(shù)據(jù)庫的分批寫入，大文件的分段下載等，主要涉及到多線程的一些知識，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友參考下2021-11-11