Как реализация LinkedHashMap отличается от HashMap?

Ответ 1

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

Ответ 2

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

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

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

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

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

Я добавил более подробную информацию о blog.

Ответ 6

HashMap не поддерживает порядок вставки, поэтому не поддерживает ни одного дважды связанного списка.

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

Ввод 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

Ответ 7

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

Он выглядит следующим образом:

header Node < --- > Node 1 < --- > Node 2 < --- > Node 3 < ---- > Node 4 < --- > заголовок node.

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

Ответ 8

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