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

Question

Я прочитал, что HashMap имеет следующую реализацию:

main array 
   ↓
[Entry] → Entry → Entry      ← linked-list implementation
[Entry]
[Entry] → Entry
[Entry]
[null ]

Итак, у него есть массив объектов Entry.

Вопросы:

1. Мне было интересно, как индекс этого массива может хранить несколько объектов Entry в случае одинакового hashCode, но разных объектов.

2. Чем это отличается от LinkedHashMap реализация? Это двунаправленная реализация списка map, но поддерживает ли он массив, как описано выше, и как он хранит указатели на следующий и предыдущий элемент?

Answer 1

Итак, он имеет массив Entry объекты.

Не совсем. Имеет массив Entry цепочки объектов. HashMap.Entry объект имеет next поле, позволяющее Entry объекты, которые будут объединены в один связанный список.

Мне было интересно, как индекс этого массива может хранить несколько Entry объекты в случае одинакового hashCode, но разных объектов.

Потому что (как показано на рисунке в вашем вопросе) Entry объекты скованы.

Чем это отличается от LinkedHashMap реализация? Это двунаправленная реализация списка map, но поддерживает ли он массив, как описано выше, и как он хранит указатели на следующий и предыдущий элемент?

в LinkedHashMap реализация, LinkedHashMap.Entry класс расширяет HashMap.Entry класс, добавив before а также after поля. Эти поля используются для сборки LinkedHashMap.Entry объекты в независимом двусвязном списке, который записывает порядок вставки. Итак, в LinkedHashMap класс, объекты входа находятся в двух разных цепочках:

• односвязная цепочка хешей, доступ к которой осуществляется через основной массив хешей, и

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

Answer 2

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 3

Посмотрите сами. Для дальнейшего использования, вы можете просто Google:

Java LinkedHashMap источник

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

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

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

РЕДАКТИРОВАТЬ: (в ответ на комментарий ОП):
HashMap поддерживается массивом, в котором некоторые слоты содержат цепочки Entry объекты для обработки столкновений. Чтобы перебрать все пары (ключ, значение), вам нужно пройти через все слоты в массиве, а затем пройти через LinkedLists; следовательно, ваше общее время будет пропорционально вместимости.

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

Answer 4

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

Одним из способов было бы иметь некоторую дополнительную информацию в значении (пары ключ -> значение), невидимую для пользователя, которая имела бы ссылку на предыдущий и следующий элемент, вставленный в хэш-карту. Преимущество состоит в том, что вы все равно можете удалять элементы в постоянное время, удаляя из хеш-карты постоянное время, и удаление из связанного списка происходит в этом случае, поскольку у вас есть ссылка на запись. Вы все еще можете вставлять в постоянное время, потому что вставка хэш-карты является постоянной, связанный список не является нормальным, но в этом случае у вас есть постоянный доступ по времени к точке в связанном списке, так что вы можете вставить в постоянное время, и, наконец, поиск - постоянное время потому что вам нужно иметь дело только с частью структуры хеш-карты для него.

---

Имейте в виду, что подобная структура данных не обходится без затрат. Размер хэш-карты значительно возрастет из-за всех дополнительных ссылок. Каждый из основных методов будет немного медленнее (может иметь значение, если они вызываются повторно). И косвенность структуры данных (не уверен, что это реальный термин:P) увеличивается, хотя это может быть не так уж важно, потому что ссылки гарантированно будут указывать на вещи внутри хэш-карты.

---

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

---

На документах оракула есть цитата, подтверждающая некоторые мои предположения.

Эта реализация отличается от HashMap тем, что поддерживает двусвязный список, проходящий через все его записи.

Еще одна актуальная цитата с того же сайта.

Этот класс предоставляет все необязательные операции Map и разрешает нулевые элементы. Как и HashMap, он обеспечивает постоянную производительность для основных операций (добавление, удержание и удаление), предполагая, что хеш-функция правильно распределяет элементы между сегментами. Производительность, скорее всего, будет немного ниже производительности HashMap из-за дополнительных затрат на поддержание связанного списка, за одним исключением: для итерации по представлениям коллекций LinkedHashMap требуется время, пропорциональное размеру карты, независимо от ее емкости., Итерация по HashMap, вероятно, будет более дорогой, требуя времени, пропорционального его емкости.

Answer 5

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

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392             Object k;
393             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394         `enter code here`        V oldValue = e.value;
395                 e.value = value;
396                 e.recordAccess(this);
397                 return oldValue;
398             }
399         }

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

Но разница между LinkedHashMap а также HashMap является LinkedHashMap поддерживает порядок вставки. Из документов:

Этот связанный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (порядок вставки). Обратите внимание, что порядок вставки не изменяется, если ключ повторно вставлен в карту. (Ключ k повторно вставляется в карту m, если m.put(k, v) вызывается, когда m.containsKey(k) возвращает true непосредственно перед вызовом).