Допомога у програмуванні, відповіді на питання / Java / Як працює порядок елементів у HashSet? - java, хешсет

Як працює порядок елементів у HashSet? - java, хешсет

Я розумію, що порядок елементів у HashSet повинен бути довільним. Але з цікавості хтось міг би сказати мені, як саме визначається порядок?

Я помітив, що коли я вставляю два елементи (скажімо, A і B), порядок вийде A, B, то повторне виконання того ж коду знову дасть мені B, A, то повторне виконання цього третього разу дозволить мені A, B.

Я маю на увазі, що це "недетермінований" і трохи дивний.

Відповіді:

4 для відповіді № 1

Порядок визначається алгоритмом хешування, використовуваним в межах Hash Map / Set, точними налаштуваннями цієї карти та Hashcodes об'єктів.

Якщо ваші об'єкти мають послідовні хеш-кодикілька прогонів (наприклад, рядки) і розміщуються в одному порядку на карті з однаковими налаштуваннями, тоді вони, як правило, виходитимуть у тому ж порядку щоразу. Якщо вони не "t, вони виграють" t.

Джерело для HashMap можна побачити тут: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java

Насправді цікавою цитатою з цього джерела є:

Цей клас не гарантує порядок карти; зокрема, це не гарантує, що замовлення залишатиметься незмінним з часом.

Тож не тільки замовлення може бути різним щоразу, коли ваша програма запускається, але насправді сам API не гарантує того, що замовлення залишатиметься постійним навіть протягом одного запуску програми!

"Недетермінований і трохи дивний" - це хороший опис впорядкування а HashMap - і насправді майже те, що кажуть документи. Якщо ви хочете замовити, використовуйте будь-який LinkedHashMap або TreeMap. Якщо ви не хочете замовляти, то не турбуйтеся про це, якщо замовлення буде фактично випадковим HashMap дає вам надзвичайно швидкі відповіді від методів, чия поведінка це гарантує!

2 для відповіді № 2

У принципі є два сприяючі фактори:

Хеш-код ваших ключів може бути недетермінованим, це буде у випадку, коли ви використовуєте хеш-код-реалізацію за замовчуванням, яка покладається на розташування пам'яті
Сам HashSet може бути не детермінованим, погляньте HashMap.initHashSeedAsNeeded (HashSet використовує HashMap в стандартній SDK Oracle в якості основної структури даних), залежно від деяких факторів, які він може використовувати sun.misc.Hashing.randomHashSeed(this) для ініціалізації hashSeed поле, яке потім використовується при обчисленні хеш-коду ключа

Рандомізація може бути важливою для досягнення ймовірних гарантій ефективності. Ось що говорить javadoc для hashSeed:

/ ** * Значення рандомізації, пов’язане з цим екземпляром, до якого застосовується
* хеш-код ключів, щоб зробити хеш-колізії важче знайти. Якщо 0, то
* альтернативне хешування вимкнено. * /

1 для відповіді № 3

Порядок не зміниться (на практиці), якщо ви щось не додасте / видалите до свого HashSet.

Порядок заснований на внутрішньому хештейн відра. І це залежить від обох hashCode() об'єкта та розмір хештеля.

Спрощений приклад:

Хеш-код "s" дорівнює 10, х "хеш-код" B "- 11. Хаштаб має розмір 2. Відображення від хеш-коду до позиції у хештелі буде суто базуватися на останньому біті, тобто навіть хеш-коди переходять у таблицю [0], непарні - у таблицю [1].

table[0] = { A }
table[1] = { B }

Ітерація над цими значеннями, швидше за все, буде A, B зараз. І цей результат повинен бути відтворений кожен раз, якщо розмір столу залишається однаковим.

Додавання третього елемента C за допомогою hashCode 12 (якщо не змінювати розмір таблиці) також додасть його до відра № 0.

table[0] = { A, C }
table[1] = { B }

Отже, ваша ітерація була б A, C, B. Or залежно від того, вставили ви A перед C: C, A, B

Додавання елементів на практиці дозволить змінити розмір таблиці та повторно скористатись хеш-версією, використовуючи скориговане відображення. Наприклад розмір таблиці збільшився б удвічі, і останні 2 біти можна було б використовувати для визначення відра

table[0] = { C }
table[1] = {   }
table[2] = { A }
table[3] = { B }

І порядок змінився б повністю, додавши лише 1 елемент.

0 для відповіді № 4

Тільки HashSet зберігає і не гарантує порядку, навіть ніякого довільного порядку (Чому hashCode () може повернути одне і те ж значення для різних об'єктів на Java?)! Не виконуйте замовлення там! Серіалізуйте та десеріалізуйте їх, і початковий порядок буде знищено.

Використовуйте LinkedHashSet замість HashSet.