前段時間做了Android端IM消息模塊的重構(gòu)糠睡，重構(gòu)的過程中優(yōu)化了對聊天消息的緩存設(shè)計诚亚，其中就包括實現(xiàn)的一個LRU緩存淘汰算法的工具類。舊代碼里對緩存使用較少学少，重構(gòu)的時候，考慮到多個IM會話聊天消息的場景很適合用LRU緩存秧骑。
為啥用緩存版确？
緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)。在軟件和硬件設(shè)計中都廣泛在使用乎折，如CPU緩存绒疗、數(shù)據(jù)庫緩存、瀏覽器緩存骂澄、Redis緩存等吓蘑。
緩存淘汰有哪些策略？
緩存的空間大小有限酗洒，緩存滿時哪些數(shù)據(jù)保留士修，哪些被清除，常見有三種策略：
- 先進(jìn)先出策略FIFO（First In, First Out）
- 最少使用策略LFU（Least Frequently Used）
- 最近最少使用策略LRU（Least Recently Used）
LRU緩存淘汰算法
維護(hù)一個按訪問時間從小到大有序排列的鏈表結(jié)構(gòu)樱衷，越靠近鏈表頭部的節(jié)點就是越早之前訪問過的棋嘲。
每次訪問緩存時，將節(jié)點移動到鏈表尾部表示最近才訪問過的矩桂，所以最近使用越多的越接近鏈表尾部沸移，最近使用越少的越接近鏈表頭部。
每次添加緩存時侄榴，緩存空間夠的情況下雹锣，直接添加到鏈表尾部，否則當(dāng)緩存空間不夠時癞蚕，優(yōu)先淘汰鏈表頭部的節(jié)點蕊爵，即離最近最少使用的節(jié)點。
- 訪問或添加緩存桦山，鏈表中存在時：將其從原位置刪除攒射，再插入到鏈表尾部；
- 添加緩存恒水，鏈表中不存在時：
- 緩存未滿：將數(shù)據(jù)直接插入鏈表尾部会放；
- 緩存已滿：先淘汰刪除鏈表頭結(jié)點，再將數(shù)據(jù)插入鏈表尾部钉凌；
代碼實現(xiàn)：
1. 緩存接口
/**
* 緩存接口
*
* @author LiuFeng
* @date 2020/10/20
*/
public interface ICache<K, V> {
/**
* 存入緩存
*
* @param key
* @param value
*/
void put(K key, V value);
/**
* 獲取緩存
*
* @param key
* @return
*/
V get(K key);
/**
* 刪除緩存
*
* @param key
*/
void remove(K key);
/**
* 緩存中是否存在
*
* @param key
* @return
*/
boolean containsKey(K key);
/**
* 判斷是否為空
*
* @return
*/
boolean isEmpty();
/**
* 清空緩存
*/
void clear();
}
2. 緩存實現(xiàn)類：
/**
* 自定義LRU緩存
* 描述：基于雙向循環(huán)鏈表和散列表實現(xiàn)的LRU緩存
* 時間復(fù)雜度：get和put都為O(1)
*
* @author LiuFeng
* @data 2020/10/20
*/
public class CustomLRUCache<K, V> implements ICache<K, V> {
// 緩存鍵的最大數(shù)量
private int keyMaxNum;
// 雙向循環(huán)鏈表頭結(jié)點
private Node<K, V> head;
// 緩存數(shù)據(jù)
private Map<K, Node<K, V>> cacheMap = new ConcurrentHashMap<>();
/**
* 構(gòu)造方法
*
* @param keyMaxNum 緩存鍵的最大數(shù)量
*/
public CustomLRUCache(int keyMaxNum) {
if (keyMaxNum < 1) {
throw new IllegalArgumentException("keyMaxNum has to be greater than 0");
}
this.keyMaxNum = keyMaxNum;
}
/**
* 存入緩存
*
* @param key
* @param value
*/
@Override
public synchronized void put(K key, V value) {
// 超出緩存容量咧最、且無此緩存數(shù)據(jù)時，移除尾結(jié)點的key
if (cacheMap.size() >= keyMaxNum && !cacheMap.containsKey(key)) {
Node<K, V> tail = head.prev;
remove(tail.key);
}
Node<K, V> node = cacheMap.get(key);
if (node != null) {
// 當(dāng)前結(jié)點是頭結(jié)點時，就不更新結(jié)點位置
if (node == head) {
return;
}
// 存在前驅(qū)結(jié)點時矢沿，將前驅(qū)結(jié)點next指針指向后繼結(jié)點
if (node.prev != node) {
node.prev.next = node.next;
}
// 存在后繼結(jié)點時滥搭，將后繼結(jié)點prev指針指向前驅(qū)結(jié)點
if (node.next != node) {
node.next.prev = node.prev;
}
} else {
node = new Node<>(key, value, null, null);
}
// 頭結(jié)點為空時，此時為鏈表無數(shù)據(jù)咨察，讓第一個結(jié)點前后指針都指向自己
if (head == null) {
node.prev = node;
node.next = node;
} else {
// 頭結(jié)點的前驅(qū)結(jié)點即tail尾結(jié)點
Node<K, V> tail = head.prev;
// 修改當(dāng)前結(jié)點前后指針
node.prev = tail;
node.next = tail.next;
// 修改head頭結(jié)點prev指針论熙，指向新的頭結(jié)點
tail.next.prev = node;
// 修改tail尾結(jié)點next指針，指向新的頭結(jié)點
tail.next = node;
}
// 保存最新頭結(jié)點數(shù)據(jù)
head = node;
// 緩存數(shù)據(jù)
cacheMap.put(key, node);
}
/**
* 獲取緩存
*
* @param key
* @return
*/
@Override
public synchronized V get(K key) {
Node<K, V> node = cacheMap.get(key);
if (node == null) {
return null;
}
if (node != head) {
// 存在前驅(qū)結(jié)點時摄狱，將前驅(qū)結(jié)點next指針指向后繼結(jié)點
if (node.prev != node) {
node.prev.next = node.next;
}
// 存在后繼結(jié)點時脓诡，將后繼結(jié)點prev指針指向前驅(qū)結(jié)點
if (node.next != node) {
node.next.prev = node.prev;
}
// 頭結(jié)點的前驅(qū)結(jié)點即tail尾結(jié)點
Node<K, V> tail = head.prev;
// 修改當(dāng)前結(jié)點前后指針
node.prev = tail;
node.next = tail.next;
// 修改head頭結(jié)點prev指針，指向新的頭結(jié)點
tail.next.prev = node;
// 修改tail尾結(jié)點next指針媒役，指向新的頭結(jié)點
tail.next = node;
// 保存最新頭結(jié)點數(shù)據(jù)
head = node;
cacheMap.put(key, node);
}
return node.value;
}
/**
* 刪除緩存
*
* @param key
*/
@Override
public synchronized void remove(K key) {
Node<K, V> node = cacheMap.get(key);
if (node != null) {
// 存在前驅(qū)結(jié)點時祝谚，將前驅(qū)結(jié)點next指針指向后繼結(jié)點
if (node.prev != node) {
node.prev.next = node.next;
}
// 存在后繼結(jié)點時，將后繼結(jié)點prev指針指向前驅(qū)結(jié)點
if (node.next != node) {
node.next.prev = node.prev;
}
// 移除的是頭結(jié)點時
if (node == head) {
// 鏈表僅包含一個結(jié)點時酣衷，head置空交惯，否則指向后繼結(jié)點
if (node == head.next) {
head = null;
} else {
head = head.next;
}
}
cacheMap.remove(key);
}
}
/**
* 緩存中是否存在
*
* @param key
* @return
*/
@Override
public synchronized boolean containsKey(K key) {
return cacheMap.containsKey(key);
}
/**
* 判斷是否為空
*
* @return
*/
@Override
public synchronized boolean isEmpty() {
return cacheMap.isEmpty();
}
/**
* 清空緩存
*/
@Override
public synchronized void clear() {
head = null;
cacheMap.clear();
}
/**
* 雙向鏈表結(jié)點
*
* @param <K>
* @param <V>
*/
private class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value, Node<K, V> prev, Node<K, V> next) {
this.key = key;
this.value = value;
this.prev = prev;
this.next = next;
}
}
}
3. 業(yè)務(wù)簡化消息實體類
/**
* 簡化消息實體類
*
* @author LiuFeng
* @data 2020/10/20
*/
public class Message {
/**
* 消息唯一序列號id
*/
public long messageId;
/**
* 時間戳
*/
public long timestamp;
/**
* 消息會話id（一個群、好友等）
*/
public String sessionId;
/**
* 消息內(nèi)容
*/
public String content;
}
4. 業(yè)務(wù)IM消息緩存類
/**
* 最近會話緩存
*
* @author LiuFeng
* @data 2020/10/20
*/
public class MessageCache {
private static final MessageCache instance = new MessageCache();
// 緩存池最多緩存多少個最近會話消息
public static final int SESSION_MAX_NUM = 50;
// 緩存池每個最近會話消息最多緩存多少個消息體
public static final int MESSAGE_MAX_NUM = 20;
// LRU緩存容器
private CustomLRUCache<String, Map<Long, Message>> cache = new CustomLRUCache<>(SESSION_MAX_NUM);
/**
* 私有化構(gòu)造函數(shù)
*/
private MessageCache() {}
/**
* 獲取單例
*
* @return
*/
public static MessageCache getInstance() {
return instance;
}
/**
* 獲取數(shù)據(jù)
*
* @param sessionId
* @return
*/
public List<Message> getData(@NonNull String sessionId) {
Map<Long, Message> messageMap = cache.get(sessionId);
if (messageMap != null) {
List<Message> messages = new ArrayList<>(messageMap.values());
sort(messages);
return messages;
}
return null;
}
/**
* 設(shè)置新數(shù)據(jù)（將清理舊的緩存）
*
* @param sessionId
* @param messages
*/
public void setNewData(@NonNull String sessionId, @NonNull List<Message> messages) {
cache.remove(sessionId);
addData(sessionId, messages);
}
/**
* 添加數(shù)據(jù)
*
* @param sessionId
* @param message
*/
public void addData(@NonNull String sessionId, @NonNull Message message) {
addData(sessionId, Collections.singletonList(message));
}
/**
* 添加數(shù)據(jù)
*
* @param sessionId
* @param messages
*/
public void addData(@NonNull String sessionId, @NonNull List<Message> messages) {
// 邊界值處理
if (messages == null || messages.isEmpty()) {
return;
}
Map<Long, Message> messageMap = cache.get(sessionId);
if (messageMap == null) {
// 新添加緩存容器
messageMap = new ConcurrentHashMap<>(MESSAGE_MAX_NUM);
cache.put(sessionId, messageMap);
}
// 新消息超過最大數(shù)量穿仪，直接清空舊數(shù)據(jù)席爽、截取集合
int outSize = messages.size() - MESSAGE_MAX_NUM;
if (outSize > 0) {
messageMap.clear();
// 消息時間從小到大排序，這里從集合尾部截取最新MESSAGE_MAX_NUM條
messages = messages.subList(outSize, messages.size());
}
// 新舊總消息超過最大數(shù)量啊片，整體移動清除舊數(shù)據(jù)
outSize = (messageMap.size() + messages.size()) - MESSAGE_MAX_NUM;
if (outSize > 0) {
List<Message> oldMessages = new ArrayList<>(messageMap.values());
sort(oldMessages);
for (int i = 0; i < outSize; i++) {
Message oldMessage = oldMessages.get(i);
messageMap.remove(oldMessage.messageId);
}
}
// 新存入緩存
for (Message message : messages) {
messageMap.put(message.messageId, message);
}
}
/**
* 移除會話
*
* @param sessionId
*/
public void remove(@NonNull String sessionId) {
cache.remove(sessionId);
}
/**
* 移除會話的某條消息
*
* @param sessionId
* @param messageId
*/
public void remove(@NonNull String sessionId, long messageId) {
if (cache.containsKey(sessionId)) {
Map<Long, Message> messageMap = cache.get(sessionId);
if (messageMap != null && !messageMap.isEmpty()) {
messageMap.remove(messageId);
}
}
}
/**
* 判空
*
* @return
*/
public boolean isEmpty() {
return cache.isEmpty();
}
/**
* 是否包含會話
*
* @param sessionId
* @return
*/
public boolean containsKey(@NonNull String sessionId) {
return cache.containsKey(sessionId);
}
/**
* 是否包含會話的某條消息
*
* @param sessionId
* @param messageId
* @return
*/
public boolean containsKey(@NonNull String sessionId, long messageId) {
if (cache.containsKey(sessionId)) {
Map<Long, Message> messageMap = cache.get(sessionId);
if (messageMap != null && !messageMap.isEmpty()) {
return messageMap.containsKey(messageId);
}
}
return false;
}
/**
* 清空緩存
*/
public void clear() {
cache.clear();
}
/**
* 按時間戳升序排序
*
* @param messages
*/
private void sort(List<Message> messages) {
Collections.sort(messages, (o1, o2) -> {
long diff = o1.timestamp - o2.timestamp;
return diff > 0 ? 1 : diff == 0 ? 0 : -1;
});
}
}
以上代碼實現(xiàn)中只锻，1、2是LRU算法實現(xiàn)的容器類工具紫谷，可以直接使用齐饮，而3、4則是基于IM消息場景具體的封裝使用笤昨，可供參考祖驱。
注意：在這個聊天消息的業(yè)務(wù)場景中，我以50個聊天會話作為LRU最大緩存數(shù)瞒窒，每個會話存儲了最多20條消息捺僻，多個會話來回點擊時，每個會話是遵循LRU策略的崇裁，但具體的消息是value部分匕坯，不遵守LRU策略的，消息的條數(shù)限制是在MessageCache中限制的寇壳。
