предисловие
ЛРУ этоLeast Recently UsedСокращенно, это буквально最近最少使用.
Обычно используется для реализации стратегии устранения кэша, поскольку кэш-память очень ценна, необходимо удалять данные по определенным правилам, чтобы память не была заполнена.
Например, обычно используемый Redis имеет следующие стратегии:
| Стратегия | описывать |
|---|---|
| volatile-lru | Выберите наименее недавно использованные данные из набора данных со сроком действия, установленным для удаления |
| volatile-ttl | Из установленного времени срока действия выбора данных, установленных, чтобы истечь данные из |
| volatile-random | Любой выбор данных, удаленных из набора данных, который настроил время истек |
| allkeys-lru | Выберите наименее использованные данные из всех наборов данных |
| allkeys-random | Произвольно выбрать данные из всех наборов данных для исключения |
| no-envicition | Запретить вытеснение данных |
Выдержка из:GitHub.com/CY C2018/int…
Осведомленность
Перед тем, как есть вопросы в контакт с поверхностью, вероятно, необходимо:
- Реализуйте кеш LRU, и когда количество кэшированных данных достигнет N, данные, которые использовались наименее недавно, должны быть удалены.
- Данные, к которым не было доступа в течение N часов, также необходимо удалить.
Вот моя реализация:
public class LRUAbstractMap extends java.util.AbstractMap {
private final static Logger LOGGER = LoggerFactory.getLogger(LRUAbstractMap.class);
/**
* 检查是否超期线程
*/
private ExecutorService checkTimePool ;
/**
* map 最大size
*/
private final static int MAX_SIZE = 1024 ;
private final static ArrayBlockingQueue<Node> QUEUE = new ArrayBlockingQueue<>(MAX_SIZE) ;
/**
* 默认大小
*/
private final static int DEFAULT_ARRAY_SIZE =1024 ;
/**
* 数组长度
*/
private int arraySize ;
/**
* 数组
*/
private Object[] arrays ;
/**
* 判断是否停止 flag
*/
private volatile boolean flag = true ;
/**
* 超时时间
*/
private final static Long EXPIRE_TIME = 60 * 60 * 1000L ;
/**
* 整个 Map 的大小
*/
private volatile AtomicInteger size ;
public LRUAbstractMap() {
arraySize = DEFAULT_ARRAY_SIZE;
arrays = new Object[arraySize] ;
//开启一个线程检查最先放入队列的值是否超期
executeCheckTime();
}
/**
* 开启一个线程检查最先放入队列的值是否超期 设置为守护线程
*/
private void executeCheckTime() {
ThreadFactory namedThreadFactory = new ThreadFactoryBuilder()
.setNameFormat("check-thread-%d")
.setDaemon(true)
.build();
checkTimePool = new ThreadPoolExecutor(1, 1, 0L, TimeUnit.MILLISECONDS,
new ArrayBlockingQueue<>(1),namedThreadFactory,new ThreadPoolExecutor.AbortPolicy());
checkTimePool.execute(new CheckTimeThread()) ;
}
@Override
public Set<Entry> entrySet() {
return super.keySet();
}
@Override
public Object put(Object key, Object value) {
int hash = hash(key);
int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ;
if (currentNode == null){
arrays[index] = new Node(null,null, key, value);
//写入队列
QUEUE.offer((Node) arrays[index]) ;
sizeUp();
}else {
Node cNode = currentNode ;
Node nNode = cNode ;
//存在就覆盖
if (nNode.key == key){
cNode.val = value ;
}
while (nNode.next != null){
//key 存在 就覆盖 简单判断
if (nNode.key == key){
nNode.val = value ;
break ;
}else {
//不存在就新增链表
sizeUp();
Node node = new Node(nNode,null,key,value) ;
//写入队列
QUEUE.offer(currentNode) ;
cNode.next = node ;
}
nNode = nNode.next ;
}
}
return null ;
}
@Override
public Object get(Object key) {
int hash = hash(key) ;
int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ;
if (currentNode == null){
return null ;
}
if (currentNode.next == null){
//更新时间
currentNode.setUpdateTime(System.currentTimeMillis());
//没有冲突
return currentNode ;
}
Node nNode = currentNode ;
while (nNode.next != null){
if (nNode.key == key){
//更新时间
currentNode.setUpdateTime(System.currentTimeMillis());
return nNode ;
}
nNode = nNode.next ;
}
return super.get(key);
}
@Override
public Object remove(Object key) {
int hash = hash(key) ;
int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ;
if (currentNode == null){
return null ;
}
if (currentNode.key == key){
sizeDown();
arrays[index] = null ;
//移除队列
QUEUE.poll();
return currentNode ;
}
Node nNode = currentNode ;
while (nNode.next != null){
if (nNode.key == key){
sizeDown();
//在链表中找到了 把上一个节点的 next 指向当前节点的下一个节点
nNode.pre.next = nNode.next ;
nNode = null ;
//移除队列
QUEUE.poll();
return nNode;
}
nNode = nNode.next ;
}
return super.remove(key);
}
/**
* 增加size
*/
private void sizeUp(){
//在put值时候认为里边已经有数据了
flag = true ;
if (size == null){
size = new AtomicInteger() ;
}
int size = this.size.incrementAndGet();
if (size >= MAX_SIZE) {
//找到队列头的数据
Node node = QUEUE.poll() ;
if (node == null){
throw new RuntimeException("data error") ;
}
//移除该 key
Object key = node.key ;
remove(key) ;
lruCallback() ;
}
}
/**
* 数量减小
*/
private void sizeDown(){
if (QUEUE.size() == 0){
flag = false ;
}
this.size.decrementAndGet() ;
}
@Override
public int size() {
return size.get() ;
}
/**
* 链表
*/
private class Node{
private Node next ;
private Node pre ;
private Object key ;
private Object val ;
private Long updateTime ;
public Node(Node pre,Node next, Object key, Object val) {
this.pre = pre ;
this.next = next;
this.key = key;
this.val = val;
this.updateTime = System.currentTimeMillis() ;
}
public void setUpdateTime(Long updateTime) {
this.updateTime = updateTime;
}
public Long getUpdateTime() {
return updateTime;
}
@Override
public String toString() {
return "Node{" +
"key=" + key +
", val=" + val +
'}';
}
}
/**
* copy HashMap 的 hash 实现
* @param key
* @return
*/
public int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
private void lruCallback(){
LOGGER.debug("lruCallback");
}
private class CheckTimeThread implements Runnable{
@Override
public void run() {
while (flag){
try {
Node node = QUEUE.poll();
if (node == null){
continue ;
}
Long updateTime = node.getUpdateTime() ;
if ((updateTime - System.currentTimeMillis()) >= EXPIRE_TIME){
remove(node.key) ;
}
} catch (Exception e) {
LOGGER.error("InterruptedException");
}
}
}
}
}
Заинтересованные друзья могут напрямую с:
Загрузите код RUN локально.
Код смотрите больше, на самом деле идея относительно проста для достижения:
- Он использует тот же способ сохранения данных, что и HashMap, но вручную реализует упрощенную версию.
- Внутри очередь используется для сохранения данных, записываемых каждый раз.
- При записи оценивается, превышает ли кэш пороговое значение N, и, если оно удовлетворяется, данные в начале очереди удаляются в соответствии с характеристиками FIFO очереди. Потому что данные в голове очереди должны быть поставлены первыми.
- Затем запустите поток демона, чтобы определить, просрочены ли данные, введенные первыми (поскольку даже если они просрочены, данные, помещенные первыми, скорее всего, удовлетворят условию просроченности).
- Установка его в качестве потока демона может лучше указать его назначение (в худшем случае пользовательский поток может привести к тому, что программа не завершится нормально, потому что поток всегда выполняется, чего нельзя сказать о потоке демона).
Приведенный выше код в целом удовлетворяет функции, но есть фатальная проблема.
Это самый последнийнаименее используемыйЕсли он не удовлетворен, удаленные данные первыми помещаются в данные.
Но из
put getПроцесс представляет собой простую реализацию HashMap, которая может углубить понимание HashMap.
реализация два
Итак, как реализовать полный кэш LRU, на этот раз время истечения не учитывается.
На самом деле, от предыдущей реализации, я могу подумать о некоторых идеях:
- Для записи наименее недавно использовавшихся требуется по крайней мере один отсортированный набор, чтобы гарантировать порядок записи.
- Порядок данных может быть обновлен после их использования.
Основываясь на двух приведенных выше пунктах, легко представить себе часто используемую структуру данных:связанный список.
- Поместите данные в точку связанного заголовка при записи данных.
- Используйте данные, когда данныеперейти к головному узлу.
- Когда количество кэшей превышает пороговое значение, данные в хвосте связанного списка удаляются.
Отсюда следующая реализация:
public class LRUMap<K, V> {
private final Map<K, V> cacheMap = new HashMap<>();
/**
* 最大缓存大小
*/
private int cacheSize;
/**
* 节点大小
*/
private int nodeCount;
/**
* 头结点
*/
private Node<K, V> header;
/**
* 尾结点
*/
private Node<K, V> tailer;
public LRUMap(int cacheSize) {
this.cacheSize = cacheSize;
//头结点的下一个结点为空
header = new Node<>();
header.next = null;
//尾结点的上一个结点为空
tailer = new Node<>();
tailer.tail = null;
//双向链表 头结点的上结点指向尾结点
header.tail = tailer;
//尾结点的下结点指向头结点
tailer.next = header;
}
public void put(K key, V value) {
cacheMap.put(key, value);
//双向链表中添加结点
addNode(key, value);
}
public V get(K key){
Node<K, V> node = getNode(key);
//移动到头结点
moveToHead(node) ;
return cacheMap.get(key);
}
private void moveToHead(Node<K,V> node){
//如果是最后的一个节点
if (node.tail == null){
node.next.tail = null ;
tailer = node.next ;
nodeCount -- ;
}
//如果是本来就是头节点 不作处理
if (node.next == null){
return ;
}
//如果处于中间节点
if (node.tail != null && node.next != null){
//它的上一节点指向它的下一节点 也就删除当前节点
node.tail.next = node.next ;
nodeCount -- ;
}
//最后在头部增加当前节点
//注意这里需要重新 new 一个对象，不然原本的node 还有着下面的引用，会造成内存溢出。
node = new Node<>(node.getKey(),node.getValue()) ;
addHead(node) ;
}
/**
* 链表查询 效率较低
* @param key
* @return
*/
private Node<K,V> getNode(K key){
Node<K,V> node = tailer ;
while (node != null){
if (node.getKey().equals(key)){
return node ;
}
node = node.next ;
}
return null ;
}
/**
* 写入头结点
* @param key
* @param value
*/
private void addNode(K key, V value) {
Node<K, V> node = new Node<>(key, value);
//容量满了删除最后一个
if (cacheSize == nodeCount) {
//删除尾结点
delTail();
}
//写入头结点
addHead(node);
}
/**
* 添加头结点
*
* @param node
*/
private void addHead(Node<K, V> node) {
//写入头结点
header.next = node;
node.tail = header;
header = node;
nodeCount++;
//如果写入的数据大于2个 就将初始化的头尾结点删除
if (nodeCount == 2) {
tailer.next.next.tail = null;
tailer = tailer.next.next;
}
}
private void delTail() {
//把尾结点从缓存中删除
cacheMap.remove(tailer.getKey());
//删除尾结点
tailer.next.tail = null;
tailer = tailer.next;
nodeCount--;
}
private class Node<K, V> {
private K key;
private V value;
Node<K, V> tail;
Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
public Node() {
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder() ;
Node<K,V> node = tailer ;
while (node != null){
sb.append(node.getKey()).append(":")
.append(node.getValue())
.append("-->") ;
node = node.next ;
}
return sb.toString();
}
}
Исходный код:GitHub.com/crossover J я…
Фактический эффект при написании:
@Test
public void put() throws Exception {
LRUMap<String,Integer> lruMap = new LRUMap(3) ;
lruMap.put("1",1) ;
lruMap.put("2",2) ;
lruMap.put("3",3) ;
System.out.println(lruMap.toString());
lruMap.put("4",4) ;
System.out.println(lruMap.toString());
lruMap.put("5",5) ;
System.out.println(lruMap.toString());
}
//输出：
1:1-->2:2-->3:3-->
2:2-->3:3-->4:4-->
3:3-->4:4-->5:5-->
При использовании его:
@Test
public void get() throws Exception {
LRUMap<String,Integer> lruMap = new LRUMap(3) ;
lruMap.put("1",1) ;
lruMap.put("2",2) ;
lruMap.put("3",3) ;
System.out.println(lruMap.toString());
System.out.println("==============");
Integer integer = lruMap.get("1");
System.out.println(integer);
System.out.println("==============");
System.out.println(lruMap.toString());
}
//输出
1:1-->2:2-->3:3-->
==============
1
==============
2:2-->3:3-->1:1-->
Идеи реализации согласуются с упомянутыми выше, и упоминаются следующие моменты:
- Данные хранятся напрямую с помощью HashMap.
- Двусвязный список используется внутренне для хранения данных, поэтому есть заголовок головного узла и хвостовой узел хвостового узла.
- Каждый раз, когда головной узел пишется, а хвостовой узел удаляется, это зависит от хвостовика заголовка.Если вы выглядите запутанным, рекомендуется реализовать связанный список, чтобы ознакомиться с ним или понять его в сочетании с объектом диаграмма отношений ниже.
- При использовании данных для перемещения в начало связанного списка первым шагом является поиск узла в двусвязном списке. Здесь возникает проблема связанного списка. Эффективность поиска очень низкая, наихудшая потребность
O(N).之后依赖于当前节点进行移动。 - При записи головного узла считается, что инициализированные головной и хвостовой узлы необходимо удалить, когда размер связанного списка равен 2. Это связано с тем, что во время инициализации генерируются два двунаправленных узла, и нет данных только для формирования структуры данных. Когда приходят реальные данные, их необходимо удалить, чтобы облегчить последующие операции (это можно продолжить оптимизировать).
- Все вышеперечисленные операции небезопасны для потоков и требуют контроля со стороны пользователя.
Ниже приведена диаграмма отношений объектов:
при инициализации
При записи данных
LRUMap<String,Integer> lruMap = new LRUMap(3) ;
lruMap.put("1",1) ;
lruMap.put("2",2) ;
lruMap.put("3",3) ;
lruMap.put("4",4) ;
при получении данных
И данные, как описано выше:
Integer integer = lruMap.get("2");
Благодаря приведенным выше изображениям должно быть хорошее понимание того, как хранятся данные.
реализовать три
На самом деле, если вы знакомы с коллекциями Java, вы обнаружите, что приведенная выше структура очень похожа на LinkedHashMap.
Друзья, которые не знакомы с этим, могут сначала понятьБазовый анализ LinkedHashMap.
Таким образом, мы можем использовать его для достижения:
public class LRULinkedMap<K,V> {
/**
* 最大缓存大小
*/
private int cacheSize;
private LinkedHashMap<K,V> cacheMap ;
public LRULinkedMap(int cacheSize) {
this.cacheSize = cacheSize;
cacheMap = new LinkedHashMap(16,0.75F,true){
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
if (cacheSize + 1 == cacheMap.size()){
return true ;
}else {
return false ;
}
}
};
}
public void put(K key,V value){
cacheMap.put(key,value) ;
}
public V get(K key){
return cacheMap.get(key) ;
}
public Collection<Map.Entry<K, V>> getAll() {
return new ArrayList<Map.Entry<K, V>>(cacheMap.entrySet());
}
}
Исходный код:GitHub.com/crossover J я…
На этот раз более лаконично, всего несколько строчек кода (конкретная логика LinkedHashMap уже реализована за нас)
фактический эффект:
@Test
public void put() throws Exception {
LRULinkedMap<String,Integer> map = new LRULinkedMap(3) ;
map.put("1",1);
map.put("2",2);
map.put("3",3);
for (Map.Entry<String, Integer> e : map.getAll()){
System.out.print(e.getKey() + " : " + e.getValue() + "\t");
}
System.out.println("");
map.put("4",4);
for (Map.Entry<String, Integer> e : map.getAll()){
System.out.print(e.getKey() + " : " + e.getValue() + "\t");
}
}
//输出
1 : 1 2 : 2 3 : 3
2 : 2 3 : 3 4 : 4
при его использовании:
@Test
public void get() throws Exception {
LRULinkedMap<String,Integer> map = new LRULinkedMap(4) ;
map.put("1",1);
map.put("2",2);
map.put("3",3);
map.put("4",4);
for (Map.Entry<String, Integer> e : map.getAll()){
System.out.print(e.getKey() + " : " + e.getValue() + "\t");
}
System.out.println("");
map.get("1") ;
for (Map.Entry<String, Integer> e : map.getAll()){
System.out.print(e.getKey() + " : " + e.getValue() + "\t");
}
}
}
//输出
1 : 1 2 : 2 3 : 3 4 : 4
2 : 2 3 : 3 4 : 4 1 : 1
LinkedHashMap также поддерживает внутреннюю двустороннюю очередь, а пороговое значение размера кэша также задается во время инициализации. При инициализации укажите, нужно ли удалять недавно использованные данные. Если да, данные будут управляться в соответствии с методом реализации 2.
На самом деле, основным кодом является переопределение метода RelebradeDentry LinkedHashMap:
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
По умолчанию он возвращает false, то есть ему все равно, превышен порог или нет.
Поэтому мы настраиваем его так, чтобы он возвращал true, когда он превышает пороговое значение, чтобы LinkedHashMap помогал нам удалять данные, которые использовались реже всего.
Суммировать
Выше приведена реализация кэша LRU.Если вы понимаете это, вы можете понять, почему, по крайней мере, когда вы используете их в обычное время.
Конечно, промышленность использует большеguavaРеализация, а также поддерживает различные стратегии истечения срока действия.
Дополнительный
Недавно я обобщил некоторые знания, связанные с Java, и заинтересованные друзья могут поддерживать их вместе.