Чем реализация LinkedHashMap отличается от HashMap?

Question

Если сложность времени LinkedHashMap такая же, как сложность HashMap, зачем нам HashMap?Каковы все дополнительные издержки LinkedHashMap по сравнению с HashMap в Java?

Answer 1

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

Answer 2

Если сложность времени LinkedHashMap такая же, как сложность HashMap, зачем нам HashMap?

Не стоит путать сложность с производительностью. Два алгоритма могут иметь одинаковую сложность, но один может последовательно работать лучше, чем другой.

Помните, что f(N) is O(N) означает, что:

C1*N <= limit(f(N), N -> infinity) <= C2*N  

, где C1 и C2 - строго положительные постоянные. Сложность ничего не говорит о том, насколько малы или велики значения C. Для двух разных алгоритмов константы, скорее всего, будут отличаться .

(И помните, что сложность big-O связана с поведением / производительностью, поскольку N становится очень большой. Она ничего не говорит о поведении / производительности для небольших значений N.)

---

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

Answer 3

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

Answer 4

LinkedHashMap - это полезная структура данных, когда вам нужно знать порядок вставки ключей на карту.Один подходящий вариант использования - для реализации кэша LRU.Из-за поддержания порядка в LinkedHashMap структуре данных требуется дополнительная память по сравнению с HashMap.Если порядок вставки не является обязательным, вы всегда должны использовать HashMap.

Answer 5

Существует еще одно существенное различие между HashMap и LinkedHashMap: Итерация более эффективна в случае LinkedHashMap.

Поскольку элементы LinkedHashMap связаны друг с другомДля итерации требуется время, пропорциональное размеру карты, независимо от ее емкости.Но в случае HashMap ;поскольку нет фиксированного порядка, поэтому для итерации по нему требуется время, пропорциональное его емкости.

Я разместил больше подробностей в своем блоге .

Answer 6

HashMap не поддерживает порядок вставки, следовательно, не поддерживает двусвязный список.

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

Запись LinkedHashMap выглядит следующим образом:

  static class Entry<K, V> {
     K key;
     V value;
     Entry<K,V> next;
     Entry<K,V> before, after;        //For maintaining insertion order    
     public Entry(K key, V value, Entry<K,V> next){
         this.key = key;
         this.value = value;
         this.next = next;
     }
  }

Используя до и после - мы отслеживаем вновь добавленную запись в LinkedHashMap, что помогает нам в поддержании порядка вставки.

Перед ссылками на предыдущую запись и после относится к следующей записи в LinkedHashMap.

Диаграммы и пошаговое объяснение см. http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

Answer 7

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

Это выглядит так:

узел заголовка <---> узел 1 <---> узел 2 <---> узел 3 <----> узел 4 <---> узел заголовка.

Таким образом, дополнительная перегрузка поддерживает вставку и удаление в этом двусвязном списке. Преимущество: Порядок итерации гарантированно является порядком вставки, которого нет в HashMap.

Answer 8

• Изменение размера должно выполняться быстрее, поскольку оно выполняет итерацию по своему двойному списку для переноса содержимого в новый массив таблиц.
• containsValue () переопределяется, чтобы использовать преимущества более быстрогоiterator.
• LinkedHashMap также можно использовать для создания кэша LRU.Специальный конструктор LinkedHashMap (acity, loadFactor, accessOrderBoolean) предоставляется для создания связанной хэш-карты, порядок итераций которой соответствует порядку последнего обращения к ее записям, от наименее недавнего доступа к последнему.В этом случае просто запрос карты с помощью get () является структурной модификацией.