Все мы знаем, что LRU используется реже всего в последнее время, и данные удаляются в соответствии с историческими записями доступа к данным. Основная идея заключается в том, что если к данным обращались недавно, у них больше шансов получить доступ в будущем. Здесь упоминается, что в кеше Redis есть LRU и алгоритм стратегии обновления кеша MyBatis L2. Голос за кадром: LFU используется реже всего, и данные удаляются в соответствии с частотой доступа к историческим данным. Основная идея заключается в том, что если к данным обращались несколько раз в прошлом, у них больше шансов получить доступ в будущем.
Анализ LRU в LinkedHashMap
На самом деле, когда мы упоминаем LRU, мы должны думать о LinkedHashMap. LRU реализуется через двусвязный список. При попадании данных в определенную позицию переместите их в хвост, отрегулировав положение данных. Вновь вставленный элемент также сразу помещается в хвост (метод вставки хвоста). Таким образом, самый последний использованный элемент перемещается в конец, а начало списка находится там, где находится наименее использовавшийся элемент.
Все методы afterNodeAccess(), afterNodeInsertion() и afterNodeRemoval() в HashMap являются пустыми реализациями, оставляя LinkedHashMap для перезаписи. LinkedHashMap завершает реализацию основных функций, переписывая эти три метода. Я должен вздохнуть, дизайн HashMap и LinkedHashMap прекрасен.
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
В методе get() LinkedHashMap каждый раз, когда мы получаем элемент, мы должны вызывать afterNodeAccess(e), чтобы переместить элемент в конец. Голос за кадром: accessOrder имеет значение true, которое основано на сортировке доступа, а accessOrder основано на сортировке вставками. Мы хотим, чтобы LinkedHashMap реализовал функцию LRU, accessOrder должен быть истинным. Если accessOrder ложно, это FIFO.
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
Мы видим, что при вставке данных, если removeEldestEntry(first) возвращает true, в соответствии со стратегией LRU головной узел будет удален.
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
Для нас настроена общая полка LRU LinkedHashMap. Так как же реализовать LRU на основе LinkedHashMap? Не паникуйте, давайте сначала посмотрим, как реализован LruCache в MyBatis.
public class LruCache implements Cache {
private final Cache delegate;
private Map<Object, Object> keyMap;
private Object eldestKey;
public LruCache(Cache delegate) {
this.delegate = delegate;
setSize(1024);
}
@Override
public String getId() {
return delegate.getId();
}
@Override
public int getSize() {
return delegate.getSize();
}
public void setSize(final int size) {
keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
private static final long serialVersionUID = 4267176411845948333L;
@Override
protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
boolean tooBig = size() > size;
if (tooBig) {
eldestKey = eldest.getKey();
}
return tooBig;
}
};
}
@Override
public void putObject(Object key, Object value) {
delegate.putObject(key, value);
cycleKeyList(key);
}
@Override
public Object getObject(Object key) {
keyMap.get(key); //touch
return delegate.getObject(key);
}
@Override
public Object removeObject(Object key) {
return delegate.removeObject(key);
}
@Override
public void clear() {
delegate.clear();
keyMap.clear();
}
@Override
public ReadWriteLock getReadWriteLock() {
return null;
}
private void cycleKeyList(Object key) {
keyMap.put(key, key);
if (eldestKey != null) {
delegate.removeObject(eldestKey);
eldestKey = null;
}
}
}
Можем нарисовать совок по тыкве и написать ЛРУ. На самом деле нам нужно только установить для accessOrder значение true и переписать removeEldestEntry(eldest). Мы добавляем логику выполнения операции LRU в removeEldestEntry(eldest).Например, если количество элементов в карте превышает указанный размер, мы начинаем удалять последний использованный элемент, чтобы освободить место для последующих новых элементов. .
Давайте посмотрим на наш собственный пример LRU, написанный от руки.
1. Сначала добавьте на карту 5 элементов методом хвостовой интерполяции, порядок должен быть 1, 2, 3, 4, 5.
2. позвонилmap.put("6", "6"), вставить элемент 6 с помощью хвостовой интерполяции, порядок в это время 1,2,3,4,5,6, а затем LinkedHashMap вызывает removeEldestEntry(), количество элементов в карте равно 6, что больше указанного size и возвращает true. LinkedHashMap удалит элементы головного узла, на этот раз порядок должен быть 2,3,4,5,6.
3. Позвонилmap.get("2"), элемент 2 выбран, элемент 2 нужно переместить в конец связанного списка, порядок в это время 3, 4, 5, 6, 2
4. Позвонилmap.put("7", "7"), та же операция, что и на шаге 2. Порядок в этой точке 4,5,6,2,7
5. Позвонилmap.get("4"), та же операция, что и в шаге 3. Порядок в этой точке 5,6,2,7,4
@Test
public void test1() {
int size = 5;
/**
* false, 基于插入排序
* true, 基于访问排序
*/
Map<String, String> map = new LinkedHashMap<String, String>(size, .75F,
false) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
boolean tooBig = size() > size;
if (tooBig) {
System.out.println("最近最少使用的key=" + eldest.getKey());
}
return tooBig;
}
};
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
map.put("5", "5");
System.out.println(map.toString());
map.put("6", "6");
map.get("2");
map.put("7", "7");
map.get("4");
System.out.println(map.toString());
}
HashMap для реализации LRU
Выше мы использовали полку LRU, встроенную в LinkedHashMap, для реализации LRU. Теперь мы выходим из контейнера LinkedHashMap и вручную поддерживаем отношения между элементами в связанном списке, то есть пишем собственные методы afterNodeRemoval(), afterNodeInsertion(), afterNodeAccess(), имитирующие реализацию LRU в LinkedHashMap. На самом деле он тоже нарисован по тыкве, но на этот раз сложность увеличилась на несколько звезд.
Голос за кадром: Средняя временная сложность запроса, вставки, модификации и удаления HashMap составляет O(1). В худшем случае все ключи хешируются в одну запись, а временная сложность снижается до O(N). Вот почему HashMap в Java8 представил красно-черное дерево. Когда длина связанного списка в записи превышает 8, связанный список превратится в красно-черное дерево. Красно-черное дерево — это самобалансирующееся бинарное дерево поиска со средней временной сложностью O(log(N)) для запроса/вставки/изменения/удаления.
вставка хвоста
1. В первую очередь используем метод вставки хвоста, то есть вновь вставленный элемент или хит-элемент перемещается в хвост, а элемент в заголовке используется наименее недавно использованным.
public class MyLru01<K, V> {
private int maxSize;
private Map<K, Entry<K, V>> map;
private Entry head;
private Entry tail;
public MyLru01(int maxSize) {
this.maxSize = maxSize;
map = new HashMap<>();
}
public void put(K key, V value) {
Entry<K, V> entry = new Entry<>();
entry.key = key;
entry.value = value;
afterEntryInsertion(entry);
map.put(key, entry);
if (map.size() > maxSize) {
map.remove(head.key);
afterEntryRemoval(head);
}
}
private void afterEntryInsertion(Entry<K, V> entry) {
if (entry != null) {
if (head == null) {
head = entry;
tail = head;
return;
}
if (tail != entry) {
Entry<K, V> pred = tail;
entry.before = pred;
tail = entry;
pred.after = entry;
}
}
}
private void afterEntryAccess(Entry<K, V> entry) {
Entry<K, V> last;
if ((last = tail) != entry) {
Entry<K, V> p = entry, b = p.before, a = p .after;
p.before = p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a == null) {
last = b;
} else {
a.before = b;
}
if (last == null) {
head = p;
} else {
p.before = last;
last.after = p;
}
tail = p;
}
}
private Entry<K, V> getEntry(K key) {
return map.get(key);
}
public V get(K key) {
Entry<K, V> entry = this.getEntry(key);
if (entry == null) {
return null;
}
afterEntryAccess(entry);
return entry.value;
}
public void remove(K key) {
Entry<K, V> entry = this.getEntry(key);
afterEntryRemoval(entry);
}
private void afterEntryRemoval(Entry<K, V> entry) {
if (entry != null) {
Entry<K, V> p = entry, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a == null) {
tail = b;
} else {
a.before = b;
}
}
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
Entry<K, V> entry = head;
while (entry != null) {
sb.append(String.format("%s:%s", entry.key, entry.value));
sb.append(" ");
entry = entry.after;
}
return sb.toString();
}
static final class Entry<K, V> {
private Entry before;
private Entry after;
private K key;
private V value;
}
public static void main(String[] args) {
MyLru01<String, String> map = new MyLru01<>(5);
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
map.put("5", "5");
System.out.println(map.toString());
map.put("6", "6");
map.get("2");
map.put("7", "7");
map.get("4");
System.out.println(map.toString());
}
}
2. Текущие результаты также равны 5, 6, 2, 7, 4, что согласуется с предыдущими рабочими результатами LRU, реализованными с помощью LinkedHashMap. Идея написания кода будет проанализирована позже.
3. Определите структуру двусвязного списка в Entry.
static final class Entry<K, V> {
private Entry before;
private Entry after;
private K key;
private V value;
}
4. Упакуйте ключ и значение в узел Entry. Вызовите метод afterEntryInsertion(entry), чтобы переместить узел Entry в конец двусвязного списка. Затем поместите ключ и Entry в HashMap. Если количество элементов в карте больше, чем maxSize, удалите головной узел в двусвязном списке (элемент, в котором находится головной узел, является последним использованным элементом). Сначала удалите элемент, соответствующий head.key на карте, а затем вызовите afterEntryRemoval(head), чтобы удалить головной узел в двусвязном списке.
public void put(K key, V value) {
Entry<K, V> entry = new Entry<>();
entry.key = key;
entry.value = value;
afterEntryInsertion(entry);
map.put(key, entry);
if (map.size() > maxSize) {
map.remove(head.key);
afterEntryRemoval(head);
}
}
5. Если головной узел двусвязного списка пуст, это доказывает, что двусвязный список пуст. Затем мы устанавливаем вновь вставленные элементы как головной и хвостовой узлы. В противном случае мы вставляем текущий узел в конец. Как он сюда вставляется? Хвостовой узел раньше был хвостовым узлом, а теперь внезапно вставляется узел (входной узел). Тогда хвостовой узел уже не может занимать положение хвоста, и мы устанавливаем его как предварительный узел. Предузел является предыдущим узлом нового хвостового узла (то есть входным узлом). Узел-предшественник входа указывает на pre, а узел-преемник pre-узла указывает на вход, тем самым завершая вставку хвоста.
private void afterEntryInsertion(Entry<K, V> entry) {
if (entry != null) {
if (head == null) {
head = entry;
tail = head;
return;
}
if (tail != entry) {
Entry<K, V> pred = tail;
entry.before = pred;
tail = entry;
pred.after = entry;
}
}
}
6. Как удалить узел в двусвязном списке? Теперь удаляемый узел является входным узлом. Сначала мы получаем его предшествующий узел b и последующий узел a. Если b равно нулю, то головной узел должен быть a после удаления узла входа. Если b не равно нулю, преемник b должен указывать на a. Также, если a равно нулю, то после удаления узла входа хвостовой узел должен быть b. Если a не равно нулю, предшествующий узел a должен указывать на b. На этом операция удаления завершена, если вы не разбираетесь в этом, то можете просто сделать обводку и снимок самостоятельно.
public void afterEntryRemoval(Entry<K, V> entry) {
if (entry != null) {
Entry<K, V> p = entry, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a == null) {
tail = b;
} else {
a.before = b;
}
}
}
7. Мы попадаем в узел входа с помощью метода get(). Так как же переместить входной узел в конец двусвязного списка? Если текущий узел уже находится в хвосте, то ничего не делаем. Если текущий узел не находится в хвосте, сначала получите его предшествующий узел b и последующий узел a, как описано выше. Затем установите для узла-предшественника и узла-преемника значение null, чтобы упростить последующие операции.
Если узел b равен нулю, то после перемещения узла входа в хвост головной узел должен быть узлом.
Если узел b не равен нулю, то узел-преемник b должен указывать на узел a.
Если узел равен нулю, то предыдущий узел нового хвостового узла должен быть b.
Если узел не равен нулю, то предшествующий узел a должен указывать на b.
Если последний узел (то есть предыдущий узел нового хвостового узла) равен нулю, это означает, что головной узел должен быть узлом p.
Если последний узел не равен нулю, мы указываем предшественника p на последний, а преемник последнего на p. Последний новый хвостовой узел — p.
Процесс немного извилистый, если не понимаете, то можете нарисовать от руки.
private void afterEntryAccess(Entry<K, V> entry) {
Entry<K, V> last;
if ((last = tail) != entry) {
Entry<K, V> p = entry, b = p.before, a = p .after;
p.before = p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a == null) {
last = b;
} else {
a.before = b;
}
if (last == null) {
head = p;
} else {
p.before = last;
last.after = p;
}
tail = p;
}
}
пробка для головы
Метод вставки головы на самом деле похож на метод вставки хвоста, разница в том, что вновь вставленный узел или узел попадания перемещается в начало двусвязного списка, тогда элемент в хвостовом узле двусвязного списка является элементом. элемент, который реже всего использовался.
Кодовая реализация метода вставки заголовка в основном такая же, как и у метода вставки хвоста, но методы afterEntryInsertion() и afterEntryAccess() были изменены. Изменения можно суммировать в тексте выше!
Поговорим о процессе изменения положения элемента на следующем примере. 1. Из-за метода вставки заголовка после вставки 5 элементов. Порядок должен быть 5,4,3,2,1
2. Выполнитьmap.put("6", "6")Затем вставьте элемент 6 в начало и удалите элемент 1 в конце в порядке 6,5,4,3,2.
3. Выполнитьmap.get("2")После переместите элемент 2 в голову, порядок 2,6,5,4,3
4. Выполнитьmap.put("7", "7")После этого вставьте элемент 7 в голову и удалите хвостовой элемент, 3, порядок 7, 2, 6, 5, 4
5. Выполнитьmap.get("4")После переместите элемент 4 в голову, окончательный порядок 4,7,2,6,5
/**
* @author cmazxiaoma
* @version V1.0
* @Description: TODO
* @date 2018/9/3 9:19
*/
public class MyLru02<K, V> {
private int maxSize;
private Map<K, Entry<K, V>> map;
private Entry<K, V> head;
private Entry<K, V> tail;
public MyLru02(int maxSize) {
this.maxSize = maxSize;
map = new HashMap<>();
}
public void put(K key, V value) {
Entry<K, V> entry = new Entry<>();
entry.key = key;
entry.value = value;
afterEntryInsertion(entry);
map.put(key, entry);
if (map.size() > maxSize) {
map.remove(tail.key);
afterEntryRemoval(tail);
}
}
public void afterEntryInsertion(Entry<K, V> entry) {
if (entry != null) {
if (head == null) {
head = entry;
tail = head;
return;
}
// if entry is not head
if (head != entry) {
entry.after = head;
entry.before = null;
head.before = entry;
head = entry;
}
}
}
public void afterEntryRemoval(Entry<K, V> entry) {
if (entry != null) {
Entry<K, V> p = entry, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null) {
head = a;
} else {
b.after = a;
}
if (a == null) {
tail = b;
} else {
a.before = b;
}
}
}
public void afterEntryAccess(Entry<K, V> entry) {
Entry<K, V> first;
if ((first = head) != entry) {
Entry<K, V> p = entry, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null) {
first = a;
} else {
b.after = a;
}
if (a == null) {
tail = b;
} else {
a.before = b;
}
if (first == null) {
tail = p;
} else {
p.after = first;
first.before = p;
}
head = p;
}
}
public void remove(K key) {
Entry<K, V> entry = this.getEntry(key);
afterEntryRemoval(entry);
}
public V get(K key) {
Entry<K, V> entry = this.getEntry(key);
if (entry == null) {
return null;
}
afterEntryAccess(entry);
return entry.value;
}
private Entry<K, V> getEntry(K key) {
Entry<K, V> entry = map.get(key);
if (entry == null) {
return null;
}
return entry;
}
@Override
public String toString() {
Entry<K, V> p = head;
StringBuffer sb = new StringBuffer();
while(p != null) {
sb.append(String.format("%s:%s", p.key, p.value));
sb.append(" ");
p = p.after;
}
return sb.toString();
}
static final class Entry<K, V> {
private Entry<K, V> before;
private Entry<K, V> after;
private K key;
private V value;
}
public static void main(String[] args) {
MyLru02<String, String> map = new MyLru02<>(5);
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
map.put("5", "5");
System.out.println(map.toString());
map.put("6", "6");
map.get("2");
map.put("7", "7");
map.get("4");
System.out.println(map.toString());
}
}
конечные слова
Всем привет, я cmazxiaoma (имеется в виду пони Шэнь Менганчжи), спасибо, что прочитали эту статью. Младший брат не талантлив. Если у вас есть какие-либо комментарии или ошибки в этой статье, которые необходимо исправить, пожалуйста, обсудите со мной. Если вы думаете, что это хорошо, я надеюсь, что вы можете дать ему большой палец вверх. Надеюсь, моя статья может быть вам полезна. Если у вас есть какие-либо комментарии, идеи или сомнения, пожалуйста, оставьте сообщение для обсуждения.
Наконец, отправьте его: что душе угодно, только исполните прошлое. Жизнь как путешествие в обратном направлении, тростник плывет.