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

Question

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

Из JavaDocs для TreeMap:

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

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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