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

Question

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

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

Таким образом, он имеет массив объектов Входа.

Вопросы:

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

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

Answer 1

Таким образом, он имеет массив Entry объектов.

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

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

Поскольку объекты Entry связаны друг от друга. См. Выше. (И «картина» в вашем вопросе!)

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

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

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

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

Answer 2

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. Сохраняет заказ на размещение. От docs:

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

Answer 3

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

Java источник LinkedHashMap

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

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

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

EDIT: (в ответ на комментарий ФП в):
HashMap опирается на массив, в котором некоторые слоты содержат цепочки Entry объектов для обработки столкновений. Чтобы перебрать все пары (ключ, значение), вам нужно будет пройти через все слоты в массиве, а затем пройти через LinkedLists; следовательно, ваше общее время будет пропорционально емкости.

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

Answer 4

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

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

---

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

---

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

---

На oracle docs есть цитата, подтверждающие некоторые из моих догадок.

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

Другая соответствующая цитата с того же сайта.

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

Answer 5

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

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

Вступление LinkedHashMap выглядит this-

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

спасибо .. !!