LinkedHashMap из серии Java Collection
Привет всем, про HashMap и LinkedList я рассказывал ранее, я знаю, что HashMap — это массив + односвязный список, а LinkedList реализован как двусвязный список. Сегодня я представлю коллекцию (HashMap+"LinkedList"), LinkedHashMap, где HashMap используется для хранения данных, а "LinkedList" используется для хранения порядка данных. Ладно, хватит нести чушь, старые распорядки, структура статьи:
- Разница между LinkedHashMap и HashMap
- Базовая реализация LinkedHashMap
- Кэш LRU с использованием LinkedHashMap
1. Разница между LinkedHashMap и HashMap
В большинстве случаев, если нет проблем с безопасностью потоков, Map может в основном использовать HashMap, но у HashMap есть проблема, то есть порядок, в котором повторяется HashMap, не соответствует порядку, в котором размещается HashMap, то есть out порядка. Этот недостаток HashMap часто вызывает проблемы, потому что в некоторых сценариях мы ожидаем упорядоченную карту.Это наша LinkedHashMap, см. небольшую демонстрацию:
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
输出为：
apple=苹果
watermelon=西瓜
banana=香蕉
peach=桃子
Можно видеть, что при использовании разница между LinkedHashMap и HashMap заключается в том, что LinkedHashMap упорядочен.Приведенный выше пример отсортирован по порядку вставки, кроме того, LinkedHashMap также имеет параметр для определенияСортировать ли по порядку доступа (получать, ставить) на этом основании, Помните, он сортируется на основе порядка вставки, и вы поймете почему после прочтения исходного кода. Взгляните на пример ниже:
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
map.get("banana");
map.get("apple");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
输出为：
watermelon=西瓜
peach=桃子
banana=香蕉
apple=苹果
Видно, что бананы и яблоки снова ранжируются на основе исходной сортировки.
2. Базовая реализация LinkedHashMap
Я сначала расскажу о выводе, а потом потихоньку буду следовать коду.
- LinkedHashMap наследуется от HashMap, а его методы new (put) и get (get) — это код, повторно использующий HashMap родительского класса,Просто перепишите некоторые интерфейсы внутри put, чтобы делать что-то., эта функция называется в C++крюковая технология, В Java все любят называть это полиморфизмом.На самом деле слово полиморфизм не может очень хорошо описать это явление.
- Хранилище данных LinkedHashMap такое же, как структура HashMap в форме (массив + односвязный список), за исключением того, что переменные до и после, используемые для поддержания порядка, добавляются к каждой записи узла для поддержания двусвязного списка для сохранить порядок хранения LinkedHashMap. При вызове итератора итератор HashMap больше не используется, но вы можете написать свой собственный итератор для обхода двусвязного списка.
- Внутренняя логическая схема HashMap и LinkedHashMap выглядит следующим образом:
Что ж, каждый определенно найдет это очень волшебным.Как показано на рисунке, исходные данные HashMap не нужны, такие как 0-7, но LinkedHashMap превратил их в 1.6.5.3, как показано на рисунке. . 2 Это по порядку. Как ты сделал это? На самом деле, если говорить прямо, в одном предложении,крюковая технология, двусвязный список поддерживается во время ввода и получения и упорядочивается при обходе. Ну пошагово с. Сначала посмотрите на Entry (то есть на каждый элемент) в LinkedHashMap:
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
...
}
Вы можете видеть запись, унаследованную от HashMap, и есть еще два указателя до и после, эти два указателя, грубо говоря, являются двумя недавно добавленными указателями для поддержания двусвязного списка. Перечислите все переменные-члены новой записи:
- K key
- V value
- Entry<K, V> next
- int hash
- Entry<K, V> before
- Entry<K, V> after
Первые четыре из них унаследованы от HashMap.Entry, последние два уникальны для LinkedHashMap. Не ошибитесь с рядом и до и после.Далее используется для поддержания порядка записи, подключенной к указанной позиции таблицы HashMap.До и после используются для поддержания порядка вставки записи (чтобы поддерживать двойную связанный список).
2.1 Инициализация
1 public LinkedHashMap() {
2 super();
3 accessOrder = false;
4 }
1 public HashMap() {
2 this.loadFactor = DEFAULT_LOAD_FACTOR;
3 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
4 table = new Entry[DEFAULT_INITIAL_CAPACITY];
5 init();
6 }
1 void init() {
2 header = new Entry<K,V>(-1, null, null, null);
3 header.before = header.after = header;
4 }
Здесь появляется первая технология ловушек.Хотя метод init() определен в HashMap, поскольку LinkedHashMap переписывает метод init в соответствии с полиморфным синтаксисом, будет вызываться метод init LinkedHashMap, который инициализируетHeader,Этот заголовок является заголовком связанного списка двусвязного списка...
2.2 LinkedHashMap добавляет элементы
поместите метод в HashMap:
1 public V put(K key, V value) {
2 if (key == null)
3 return putForNullKey(value);
4 int hash = hash(key.hashCode());
5 int i = indexFor(hash, table.length);
6 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
7 Object k;
8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
9 V oldValue = e.value;
10 e.value = value;
11 e.recordAccess(this);
12 return oldValue;
13 }
14 }
15
16 modCount++;
17 addEntry(hash, key, value, i);
18 return null;
19 }
addEntry в LinkedHashMap (еще одна техника ловушки):
1 void addEntry(int hash, K key, V value, int bucketIndex) {
2 createEntry(hash, key, value, bucketIndex);
3
4 // Remove eldest entry if instructed, else grow capacity if appropriate
5 Entry<K,V> eldest = header.after;
6 if (removeEldestEntry(eldest)) {
7 removeEntryForKey(eldest.key);
8 } else {
9 if (size >= threshold)
10 resize(2 * table.length);
11 }
12 }
1 void createEntry(int hash, K key, V value, int bucketIndex) {
2 HashMap.Entry<K,V> old = table[bucketIndex];
3 Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
4 table[bucketIndex] = e;
5 e.addBefore(header);
6 size++;
7 }
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
Ну а addEntry сначала добавляет данные в структуру в HashMap (массив + односвязный список), а потом вызывает addBefore, не буду с вами рисовать картинку,На самом деле, это перемещение указателей переменных-членов Before и After на себя и заголовок, чтобы добавить себя в конец двусвязного списка.Точно так же, сколько бы раз вы ни ставили, текущий элемент будет добавлен в хвост очереди. Теперь все знают, как поддерживать эту двустороннюю очередь.
Как упоминалось выше, LinkedHashMap автоматически поддерживает двусторонний список при добавлении данных.Также следует упомянуть, что есть еще один атрибут LinkedHashMap.Сортировать по порядку запросов,Грубо говоря, это отбрасывание элемента в хвост двусторонней очереди в момент получения или установки (обновления). Разве это не упорядочено?? Это включает в себя еще один конструктор LinkedHashMap:
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
Третий параметр, accessOrder, определяет, следует ли включитьПереключатель функции сортировки запросов, который по умолчанию имеет значение False. Если вы хотите открыть, вы должны вызвать этот конструктор. Затем посмотрите, как поддерживается очередь во время получения и установки (операции обновления).
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
Кроме того, при установке код 11 (см. код выше) также вызывает e.recordAccess(this), давайте взглянем на этот метод:
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
private void remove() {
before.after = after;
after.before = before;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
Я вижу, что каждый раз, когда RecordAccess делает две вещи:
- Соедините передний и задний вход перемещаемого входа
- Переместите запись, которую нужно переместить в конец
Конечно, все это основано на accessOrder=true. Предположим теперь, что мы включили accessOrder, а затем вызвали get("111"); и посмотрим, как это работает:
3. Используйте LinkedHashMap для реализации кэша LRU
LRU используется наименее недавно, то есть используется наименее недавно, то есть, когда кэш заполнен, данные, к которым реже всего обращаются, будут удалены в первую очередь.. Наш LinkedHashMap как раз соответствует этой функции, почему? Когда мы включаем accessOrder в true,Данные последнего доступа (получить или положить (операция обновления)) будут брошены в конец очереди, поэтому голова двусторонней очереди — это наименее часто используемые данные.. Например:
Если есть 3 записи 1 2 3, то осуществляется доступ к 1, и 1 перемещается в конец, то есть 2 3 1. При каждом доступе запрашиваемые данные перемещаются в конец двусторонней очереди, поэтому каждый раз, когда данные должны быть удалены, не являются ли данные в начале двусторонней очереди теми, к которым реже всего обращаются? Другими словами, данные в верхней части двусвязного списка — это данные, которые необходимо исключить.
Кроме того, LinkedHashMap также предоставляет метод, этот метод предоставляется нам для реализации кэша LRU,метод removeEldestEntry(Map.Entry
Давай, дам тебе простой кэш LRU:
public class LRUCache extends LinkedHashMap
{
public LRUCache(int maxSize)
{
super(maxSize, 0.75F, true);
maxElements = maxSize;
}
protected boolean removeEldestEntry(java.util.Map.Entry eldest)
{
//逻辑很简单，当大小超出了Map的容量，就移除掉双向队列头部的元素，给其他元素腾出点地来。
return size() > maxElements;
}
private static final long serialVersionUID = 1L;
protected int maxElements;
}
Разве это не просто. .
Эпилог
По сути, LinkedHashMap почти такой же, как HashMap: технически разница в том, что он определяет заголовок Entry