Мне было интересно, как Java заказывает элементы в Map (HashMap или Hashtable) при их добавлении. Являются ли ключи упорядоченными хэш-кодом, ссылкой на память или приоритетом размещения...?
Это потому, что я заметил, что те же пары в Map не всегда находятся в одном порядке
java.util.HashMap неупорядочен; вы не можете и не должны предполагать ничего сверх этого.
Этот класс не дает никаких гарантий относительно порядка карты; в частности, он не гарантирует, что порядок будет оставаться постоянным с течением времени.
java.util.LinkedHashMap использует порядок вставки.
Эта реализация отличается от
HashMapтем, что она поддерживает список с двойной связью, проходящий через все его записи. Этот связанный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (порядок вставки).
java.util.TreeMap, SortedMap, использует естественный или пользовательский порядок ключей.
Карта сортируется в соответствии с естественным порядком ее ключей или посредством
Comparator, предоставленной при создании карты, в зависимости от того, какой конструктор используется.
Прежде всего: HashMap в частности не обеспечивает стабильное и/или определенное упорядочение. Таким образом, все, что вы наблюдаете, представляет собой просто деталь реализации, и вы не должны зависеть от него каким-либо образом.
Так как иногда полезно знать причину кажущегося случайного упорядочения, здесь основная идея:
A HashMap имеет количество ковшей (реализовано как массив), в котором хранятся записи.
Когда элемент добавляется к карте, он присваивается ковшим на основе значения, полученного из его hashCode и размера ковша HashMap. (Обратите внимание, что возможно, что ведро уже занято, что называется столкновением. Это обрабатывается изящно и правильно, но я проигнорирую эту обработку для описания, потому что это не меняет концепцию).
Предполагаемое упорядочение entites (например, возвращаемое путем итерации по Map) зависит от порядка записей в этих ведрах.
Всякий раз, когда размер перерисовывается (поскольку карта превысила порог полноты), тогда число ковшей изменяется, что означает, что позиция каждого элемента может измениться, так как позиция ковша получается из числа ковшей.
HashMap не сортируется вообще. Для карты, которая сортирует по ключевым значениям, вы должны использовать TreeMap.
Из JavaDocs для TreeMap:
Реализация на основе красных и черных деревьев интерфейс SortedMap. Этот класс гарантирует, что карта будет находиться в по возрастанию, порядок сортировки к естественному порядку для ключа класса (см. сравнимое) или компаратор, предоставленный во время создания, в зависимости от того, какой конструктор б.
Из документации HashMap:
Этот класс не дает никаких гарантий относительно порядок карты; в частности, это не гарантирует, что заказ будет оставаться постоянным с течением времени.
A Map не упорядоченная структура данных - вы не должны полагаться на записи в HashMap, находящиеся в определенном порядке. Некоторые реализации Map, такие как LinkedHashMap и TreeMap, гарантируют определенный порядок, но HashMap не работает.
Если вы действительно хотите узнать, что происходит внутри, найдите исходный код HashMap - вы можете найти его в src.zip, который должен находиться в каталоге установки JDK.
A HashMap имеет ряд "ведер", в которых он хранит свои записи. Какое ведро хранится запись, определяется хеш-кодом ключа записи. Порядок, в котором вы видите записи в HashMap, зависит от хэш-кодов клавиш. Но не пишите программы, которые полагаются на записи, находящиеся в определенном порядке в HashMap - реализация может измениться в будущей версии Java, и ваша программа больше не будет работать.
hashmap имеет не определенный порядок элементов
В хэш-таблице нет определенного порядка. Ключи помещаются в слот на основе хеш-кода, но даже это не тривиальный порядок-хэш-код.
HashMap сохраняет значения, используя уникальное значение хэш-функции, сгенерированное с использованием части ключа. Это хэш-значение отображает адрес, в котором он будет храниться. Таким образом, он обеспечивает доступ O (1).
LinkedHashmap, с другой стороны, сохраняет порядок, в который вы добавили карту.