Ядро LinkedHashMap составляет всего 2 пункта.Если разберетесь, то освоите.

Java

Одним из недостатков HashMap является то, что вповторятьвремя элемента сНесогласованный порядок размещения. И большинству людей нравится делать определенные вещи по порядку, поэтому LinkedHashMap расширяет HashMap для этого, в основном добавляя **"два метода итерации"**:

  • в порядке вставки- Убедитесь, что порядок повторяющихся элементов совпадает с порядком вставки.
  • по порядку доступа- Специальный порядок итерации, от наименее недавно посещенного к наиболее посещаемому порядку доступа к элементам, идеально подходит для построенияLRUтайник

В центре внимания LinkedHashMap находятся эти два момента, как только вы разберетесь с ними, вы освоите их. Поскольку он наследуется от HashMap, перед анализом исходного кодадолженЧтобы сначала увидеть исходный код HashMap, вы можете проверить эту статью"Глубокий анализ принципа, реализации и оптимизации HashMap в JDK8".

В JDK 8 из-за существования подкласса LinkedHashMap красно-черное дерево, представленное HashMap, между обычным режимом и режимом дереваПреобразование усложняется, так как же это спроектировано и упрощено? см. далееJDK 8Разработка и реализация исходного кода LinkedHashMap в формате .

1. Итерация в порядке вставки

Почему HashMap терпит неудачу при итерации?неорганизованныйуже? Посмотрите, как он получает следующий элемент во время итерации, и вы увидите:

final Node<K,V> nextNode() {
  Node<K,V>[] t;
  Node<K,V> e = next; // 下一个元素要访问节点
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
  if (e == null) throw new NoSuchElementException();
  // 首先迭代自身所在链表
  if ((next = (current = e).next) == null && (t = table) != null) {
    // 如果链表访问结束，遍历哈希桶数组中下一个非空元素
    do {} while (index < t.length && (next = t[index++]) == null);
  }
  return e;
}

Как видите, HashMap соответствует массиву хеш-контейнеров.непустой слотПоследовательный обход вкупе с коллизией хешей (связный список) более хаотичен, чем порядок вставки.

Как LinkedHashMap решил эту проблему? Он поддерживаетДвусвязный список, при обходе итератор напрямую выполняет итерацию по двусвязному списку, тем самым обеспечивая согласованность с порядком вставки.Атрибуты ключевых элементов и информация об узле определяются следующим образом:

// 双向链表头节点，也是最久没有访问的元素
transient LinkedHashMap.Entry<K,V> head;
// 双向链表尾节点，也是最近刚刚访问的元素
transient LinkedHashMap.Entry<K,V> tail;
// 迭代方式，true-按访问顺序迭代，false-按插入顺序迭代，默认 false
final boolean accessOrder;
// 添加了构建双向链表的前驱和后继指针
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);
  }
}

HashMap определяет и вызывает некоторые элементы при вставке, удалении и доступе к элементам.Крючковый метод, эти методы делают внутренний механизм упорядочения LinkedHashMap относительнонезависимый, что снижает сложность преобразования обычного режима и режима дерева.

Кроме того, красно-черный узел дерева наследует Entry от LinkedHashMap, хотя указателей может быть на два больше, но это помогает избежать ошибок путаницы при работе с указателями.

Когда элемент вставляется в LinkedHashMap, охватываемые методы обратного вызова в основном включают newNode, replaceNode, replaceTreeNode, newTreeNode, в основном для поддержки двусвязного списка.Основными являются следующие два метода:

// 插入到双向链表的尾部
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;
  }
}

// 连接两个节点之间的前后指针
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                           LinkedHashMap.Entry<K,V> dst) {
  LinkedHashMap.Entry<K,V> b = dst.before = src.before;
  LinkedHashMap.Entry<K,V> a = dst.after = src.after;
  if (b == null)
    head = dst;
  else
    b.after = dst;
  if (a == null)
    tail = dst;
  else
    a.before = dst;
}

Реализация итератора относительно проста, его можно выполнять непосредственно в двусвязном списке, а порядок итерации в настоящее время — порядок вставки.

2. Итерация в порядке доступа

Чтобы упорядочить элементы в порядке доступа, HashMap определяет следующие методы Hook для реализации LinkedHashMap:

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

Принцип каждого метода следующий:

  • afterNodeAccessПринцип таков: если элемент, к которому осуществляется доступ, не является хвостовым узлом, то он обменивается с хвостовым узлом, поэтому чем больше посещается элемент, тем позже происходит доступ к элементу.
  • afterNodeRemovalСпециальной операции для этого нет, обычная цепь разъединения
  • afterNodeInsertionПринцип таков: после того, как элемент вставлен,может бытьУдалите самый старый, наименее посещаемый элемент, который является головным узлом.

Сосредоточьтесь на реализации после вставки:

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, который по умолчанию возвращает false. При переопределении этого метода вы не можете просто вернуть true, потому что это может привести к пустой LinkedHashMap.Обычная практика заключается в том, чтобы вставить указанное количество элементов, а затем удалить их.Подробнее см. реализацию кэша LRU ниже.

3. Реализуйте кеш LRU

С помощью LinkedHashMap можно легко реализовать структуру данных кэша LRU.Просто установите для accessOrder значение true и переопределите метод removeEldestEntry.Код выглядит следующим образом:

final int MAX_CACHE_SIZE = 100;
LinkedHashMap<Object, Object> lru = new LinkedHashMap<Object, Object>(MAX_CACHE_SIZE, 0.75f, true) {
    private static final long serialVersionUID = 1L;
    protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
      return size() > MAX_CACHE_SIZE;
    }
};

4. Резюме

Код LinkedHashMap относительно прост, а сложные реализованы на HashMap :) Их сходства и различия заключаются в следующем:

  • Нижний слой — массив + связанный список + красно-черное дерево (ерунда)
  • Итераторы быстро выходят из строя и не являются потокобезопасными
  • LinkedHashMap имеет два порядка итерации вставки и доступа, в то время как HashMap выходит из строя, и порядок итерации непредсказуем.

Глядя на исходный код этого класса, самое главное — взглянуть на определение HashMap метода Hook, чтобы LinkedHashMap сохранял упорядоченный механизм относительно независимым дизайном, которыйРежим шаблонаПриложения.

Поиск в общедоступном аккаунте "Исходный код Крещения” для более подробного анализа исходного кода и создания колес.

Категории