предисловие
Есть много семейств Map, из которых больше всего используются HashMap и ConcurrentHashMap, а LinkedHashMap вроде бы используется меньше, но у него порядок. Два, один — порядок добавления, другой — порядок доступа.
Подробности
LinkedHashMap наследует HashMap. Итак, если бы это были вы, как бы вы реализовали эти две последовательности?
Если реализован порядок добавления, мы можем добавить к этому классу связанный список, и каждый узел соответствует корзине в хеш-таблице. Таким образом, когда цикл пройден, его можно пройти в соответствии со связанным списком. Это просто увеличивает потребление памяти.
Если реализован порядок доступа, можно также использовать связанный список, но каждый раз при чтении данных связанный список необходимо обновлять, а самое последнее чтение помещается в конец цепочки. Это также может быть достигнуто. В настоящее время вы также можете использовать эту функцию для реализации кэша LRU (наименее недавно использовавшегося).
как пользоваться?
Ниже небольшая демонстрация
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
for (int i = 0; i < 10; i++) {
map.put(i, i);
}
for (Map.Entry entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
map.get(3);
System.out.println();
for (Map.Entry entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
распечатать результат:
0:0
1:1
2:2
3:3
4:4
5:5
6:6
7:7
8:8
9:9
0:0
1:1
2:2
4:4
5:5
6:6
7:7
8:8
9:9
3:3
В первую очередь интересен метод построения: булевского параметра accessOrder больше, чем HashMap. Представляет, отсортированные по порядку доступа. Последний доступ помещается в конец связанного списка.
Если это значение по умолчанию, оно находится в порядке добавления, то есть accessOrder по умолчанию имеет значение false.
реализация исходного кода
Если вы посмотрите на внутренний исходный код LinkedHashMap, вы обнаружите, что связанный список действительно поддерживается внутри:
/**
* 双向链表的头，最久访问的
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 双向链表的尾，最新访问的
*/
transient LinkedHashMap.Entry<K,V> tail;
И этот LinkedHashMap.Entry также поддерживает необходимые элементы двусвязного списка до, после:
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
При добавлении элементов он будет добавлен в конец.
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
При получении он изменит порядок связанного списка в соответствии с атрибутом accessOrder:
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;
}
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;
}
}
Также обратите внимание: здесь модифицируется modCount, даже если это операция чтения, параллелизм небезопасен.
Как реализовать кэш LRU?
LRU-кэш:LRU（Least Recently Used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
LinkedHashMap не помог мне реализовать конкретику, нам нужно реализовать ее самим. Конкретным методом реализации является метод removeEldestEntry.
Давайте посмотрим принцип вместе.
Прежде всего, HashMap вызовет метод afterNodeInsertion в конце метода putVal, который фактически зарезервирован для LinkedHashMap. Конкретная реализация LinkedHashMap заключается в том, чтобы определить, нужно ли удалять головной узел в соответствии с некоторыми условиями.
Исходный код выглядит следующим образом:
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);
}
}
представление параметров исключения是否需要删除某个元素, а условия, которые необходимо выполнить для этого при оценке, следующие: заголовок не может быть нулевым, вызвать метод removeEldestEntry и, если он возвращает true, удалить заголовок. И этот метод по умолчанию возвращает false, ожидая, пока вы его переопределите.
Итак, реализация метода removeEldestEntry обычно выглядит так:
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
return size() > capacity;
}
Если длина больше емкости, то кеш, к которому редко обращаются, необходимо очистить. afterNodeInsertion вызывает метод removeNode, который удаляет головной узел — наименее посещаемый узел, если accessOrder имеет значение true.
Дополнения
LinkedHashMap переписывает некоторые методы HashMap, такие как метод containsValue.Давайте попробуем угадать этот метод.Как переписать его более разумно?
HashMap использует двойной цикл, сначала зацикливая внешнюю хеш-таблицу, а затем зацикливая связанный список с внутренней записью. Спектакль можно представить.
Но внутри LinkedHashMap есть связанный список элементов, просто пройдите напрямую по связанному списку. Относительно гораздо выше.
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
Это также стратегия «пространство во времени».
Метод get, конечно же, также переопределяется. Поскольку связанный список необходимо обновить в соответствии с accessOrder.
Суммировать
Резюме Сюэ Вэя:
LinkedHashMap содержит порядок обслуживания двусвязного списка, который поддерживает два вида порядка — порядок добавления и порядок доступа.
По умолчанию используется порядок добавления.Если вы хотите изменить порядок доступа, для параметра accessOrder в конструкторе необходимо установить значение true. Таким образом, каждый раз, когда вызывается метод get, только что доступный элемент будет обновляться до конца связанного списка.
Что касается LRU, в режиме, где accessOrder имеет значение true, вы можете переопределить метод removeEldestEntry для возвратаsize() > capacity, который удаляет наименее часто используемые элементы.