Обсуждение HashSet, в частности- хранит HashSet объекты отсортированными или нет?

@kravam · Регистрация: 04.06.2008

Студворк — интернет-сервис помощи студентам

Что-то я не могу понять. Смотрите, мне надо запихать 10000 случайных элементов типа Integer в порядке их генерирования в HashSet, а потом их вывести. Вроде как если HachSeеt хранит их неотсортированными, то и вывести они должны абы как. Но нет. Вот их вывод:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;
 
public class SetOfInteger {
  public static void main(String[] args) {
    Random rand = new Random(47);
    Set<Integer> intset = new HashSet<Integer>();
    for(int i = 0; i < 10000; i++) {
      Integer x= rand.nextInt(10);
      // System.out.print(x);
      intset.add(x);
    }
    System.out.println(intset);
  }
}

Вывод:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28]

Это что, прикол такой? Я надеялся работать с рандомной последовательностью c нормальным распределением. Мне что её, по новой перемешивать?

Так, наверное, это HashSet так реализован, что ему, чтобы удалять (или вообще не включать в себя) из себя повторяющиеся элементы, необходимо прибегать к какой-то там сортировке. Повторяю, не сортировка, чтобы элементы сортирнуть (по определению, они хранятся неотсортированными), а сортировка, чтобы не было одинаковых. Но как-то мне от этого не легче. Тем более, что вот вывод этого же примера, взятый из книги Брюса Эккеля:

[15, 8, 23, 16, 7, 22, 9, 21, 6, 1, 29, 14, 24, 4, 19, 26, 11, 18, 3, 12, 27, 17, 2, 13, 28, 20, 25, 10, 5, 0]

Вот это мешанина так мешанина, я понимаю. Почему же у Брюса Эккеля получилось, а у меня нет? Какие будут соображения на этот счёт? Спасибо, кто откликнется. verylazy не беспокоиться.

@Insane__ · 01.04.2014, 00:21

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

В вашем случае получается отсортированная коллекция потому что это совпадение

Просто получилось что хэш коды размещены в подобном порядке:
X1 < X2 < X3 < X4 < ... < X9

@tankomaz · 01.04.2014, 03:48

А вообще виновато "бинарное дерево", реализация HashSet целиком и полностью делегирует HashMap (тойсь не имеет своей реализации, а заставляет всю работу делать HashMap'e), а у HashMap есть изначальный массив на 16 ячеек типа Entry, а в какую ячейку попадет значение - вычисляется (hashCode % к-во_ячеек - 1), итого и имеем. Представьте себе массив на 16 элементов...

1 % 16 - 1 = 0 - значит попадает в table[0]
2 % 16 - 1 = 1 - а эта попадает в table[1]
....
17 % 16 - 1 = 0 - и по кругу, идея понятна

когда "степень загрузки" достигает oldCapacity * loadFactor ... loadFactor = 0.75 по умолчанию, то размер увеличивается массива table в два раза, и происходит пересчет позиций (теперь то у нас 32 корзины для хранения, а затем 64.....128.......), но т.к. у нас тип Integer - то как бы не старались - Insane__ правильно написал - всегда будет в порядке возрастания, но стоит нам переопределить метод hashCode и поставить свои условия - такой "шары" больше не будет

IntegerWrapper.java

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class IntegerWrapper {
    int i;
    Random random = new Random();
 
    IntegerWrapper (int i) {
        this.i = i;
    }
 
    @Override
    public int hashCode() {
        return i * random.nextInt(100);
    }
 
    @Override
    public String toString() {
        return Integer.toString(i);
    }
}

и для теста

Java
1
2
3
4
5
        Set<IntegerWrapper> set = new HashSet<>();
        for (int i = 0; i < 100; i++) {
            set.add(new IntegerWrapper(i));
        }
        System.out.println(set);

Добавлено через 4 минуты
кстати, вот hashCode класса Integer

Java
1
2
3
    public int hashCode() {
        return value;
    }

Добавлено через 27 секунд
что собственно и есть логично, не подумайте

@turbanoff · 01.04.2014, 09:03

Сообщение от tankomaz

А вообще виновато "бинарное дерево"

Осталось понять, причем здесь бинарное дерево?

@kravam · 01.04.2014, 13:41 **[ТС]**

Сообщение от Insane__

HashSet хранит информацию используя механизм хэширования, в котором содержание ключа используется для вычисления уникального значения - хещ код. Этот хеш код затем применается в качестве индекса которому ассоциированные данные, т.е. в вашем случае это X. Преобразование ключа в хэш код выполняется автоматически и вы не можете контролировать этот процесс.
В вашем случае получается отсортированная коллекция потому что это совпадение Просто получилось что хэш коды размещены в подобном порядке:
X1 < X2 < X3 < X4 < ... < X9

То есть я правильно понял, что там внутри какая-то таблица хеширования типа такой, в которой ключи ОТСОРТИРОВАНЫ

ключ.....

значение

ключ__0

0...........

ключ__1

1...........

ключ__2

2...........

ключ__3

3...........

ключ__4

4...........

ключ__5

5...........

...........

.............

ключ_29

28..........

И потом эта таблица выводится согласно ключам, начиная от значения, которое соответствует ключ_0 и заканчивает значением, которое соответствует ключ_29. И вдруг оказывается, что выводимые значения ПОЧТИ отсортированы?

////////////////////////////////////////////////////////////////////////////////

Если это так, тогда вывод- грош цена этим ключам. Хэш-код значения (суть ключ), он должен быть каким-то сложногенерированным. А тут почти полное соответствие между значениями и ключами. Почти линейная зависимость, типа:

ключ=k*значение+какая_то_незначительная_ лямбда

Эта какая_то_незначительная_лямбда и даёт, что в некоторых местах последовательность всё же неотсортированная. Я упрощаю, но зависимость ключа от значения- прямо скажем, корявая. Не хэш это. Это ДАЛЕКО не MD5 и не SHA-1.

Они бы уж сразу ставили в соответствие значению его порядковый номер, и пусть бы значения хранились отсортированными, чтобы людей не смущать. А для мешанины добавляли бы отдельную функцию. А то и не вашим и не нашим. И отсортированной назвать нельзя, и без дополнительного перемешивания не обойтись.

////////////////////////////////////////////////////////////////////////////////

И остался вопрос- почему у Эккеля-то мешанина всё-таки получается? У него что, ключи по-другому вычисляются?

Добавлено через 6 минут

Сообщение от tankomaz

кстати, вот hashCode класса Integer

Не понял, это что, в качестве хэш-кода числа возвращается его значение?

@turbanoff · 01.04.2014, 14:07

Сообщение от kravam

И остался вопрос- почему у Эккеля-то мешанина всё-таки получается?

Может он исользовал другую реализацию HashMap-а. Старой версии, например, или вообще не от Sun/Oracle.

Сообщение от kravam

Не понял, это что, в качестве хэш-кода числа возвращается его значение?

Да

@kravam · 01.04.2014, 14:21 **[ТС]**

Сообщение от turbanoff

Да

И у меня так. Но если бы он использовался, то печаталась бы полностью отсортированная последовательность! А там начиная с 16-го чётные и нечётные значения обмениваются значениями ключей.

Это у них видать, и называется, "хранить неотсортированным"...

@tankomaz · 02.04.2014, 03:06

Сообщение от turbanoff

Осталось понять, причем здесь бинарное дерево?

виноват, но остальное считаю святой правдой, хоть в этом не ошибаюсь по знаниям?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .

@Insane__ 43 / 43 / 15 Регистрация: 10.09.2013 Сообщений: 293
	01.04.2014, 00:21
	HashSet хранит информацию используя механизм хэширования, в котором содержание ключа используется для вычисления уникального значения - хещ код. Этот хеш код затем применается в качестве индекса которому ассоциированные данные, т.е. в вашем случае это X. Преобразование ключа в хэш код выполняется автоматически и вы не можете контролировать этот процесс. В вашем случае получается отсортированная коллекция потому что это совпадение Просто получилось что хэш коды размещены в подобном порядке: X1 < X2 < X3 < X4 < ... < X9 1