Как Java упорядочивает элементы в HashMap или HashTable?

Question

Как Java упорядочивает элементы в HashMap или HashTable?

мне было интересно, как Java заказывает элементы в Map (HashMap или Hashtable), когда они добавляются. Ключи упорядочены по хэш-коду, ссылке на память или по приоритету выделения...?

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

635 7

java map hashcode hashmap hashtable

7 ответов:

Comments

Ничего не найдено.

polygenelubricants · Accepted Answer · 2010-05-12 13:04:55

java.util.HashMap неупорядочен; вы не можете и не должны предполагать ничего сверх этого.

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

java.util.LinkedHashMap использует вставки-заказа.

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

java.util.TreeMap, a SortedMap, использует природный или изготовленный на заказ ключи.

карта сортируется в соответствии с естественным порядком ее ключей, или по Comparator предоставляется во время создания карты, в зависимости от того, какой конструктор используется.

Joachim Sauer · Accepted Answer · 2010-05-12 13:18:30

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

поскольку иногда полезно знать причину кажущегося случайного порядка, вот основная идея:

A HashMap имеет количество ведер (реализованных в виде массива), в которых хранятся записи.

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

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

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

Behrang · Accepted Answer · 2010-05-12 13:03:13

HashMap не сортирует вообще. Для карты, которая сортируется по ключевым значениям, вы должны использовать TreeMap вместо.

из JavaDocs для TreeMap:

красно-черное дерево на основе реализации интерфейс SortedMap. Этот класс гарантирует, что карта будет внутри по возрастанию порядок ключей, отсортированных в соответствии к естественному порядку для ключа класс (см. сопоставимый), или компараторов во время создания , в зависимости от того, какой конструктор используемый.

из документации HashMap:

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

Jesper · Accepted Answer · 2010-05-12 13:03:31

A Map не упорядоченную структуру данных, вы не должны полагаться на записи в HashMap находясь в определенном порядке. Некоторые Map реализации, такие как LinkedHashMap и TreeMap гарантируйте определенный заказ, но HashMap нет.

если вы действительно хотите знать, что происходит внутри, просмотра исходного кода HashMap - вы можете найти его в src.молнии который должен быть в вашем каталоге установки JDK.

A HashMap имеет ряд "ведра", в которых он хранит свои записи. В каком ведре хранится запись, определяется хэш-кодом ключа записи. Порядок, в котором вы видите записи в HashMap зависит от хэш-кодами ключей. Но не пишите программы, которые полагаются на записи, находящиеся в определенном порядке в HashMap - реализация может измениться в будущей версии Java, и ваша программа больше не будет работать.

Robar · Accepted Answer · 2010-05-12 13:04:38

hashmap имеет не определенный порядок элементов

Marcelo Cantos · Accepted Answer · 2010-05-12 13:03:34

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

Vaishak Suresh · Accepted Answer · 2010-05-12 13:13:19

HashMap сохраняет значения, используя уникальное хэш-значение, созданное с помощью части ключа. Это хэш-значение сопоставляется с адресом, где оно будет храниться. Вот как он обеспечивает доступ O (1).

LinkedHashmap с другой стороны сохраняет порядок, в котором вы добавили к карте.