Не могу разобраться с хеш-функциями, хеш-кодом и в целом с HashMap

 
 
 
Сообщения:4
Здравствуйте, я начал свое знакомство с классом HashMap в Java и ввиду расхождений в разных источниках, которые запутали меня, возник вопрос насчет хеширования и поиска нужного индекса в хеш-таблице.

Хеш-функция и хеш-код это вроде бы разные понятия, но почему-то в некоторых статьях я не раз видел, что их смешивают и приравнивают, что вводит меня в дополнительную путаницу. Да и большинство статей с подробным разбором довольно старые. Например, в Java 7 индекс нужной ячейки вычислялся в методе indexFor, сейчас же его нет (использую JDK 12). Прошу помощи, чтобы я смог разобраться и не плутал вокруг этого уже третий день.

Я попробовал посмотреть в документации (я не программист, я учу язык) и попробовал что-то найти. Внутри массива в ячейках лежат узлы (класс Node). В этом классе есть поле hash - это и есть тот самый хеш-код?
Также там есть метод hashCode(), который вычисляется так:

return Objects.hashCode(key) ^ Objects.hashCode(value);

Но я думал, что хеш-код вычисляется только по ключу? Именно результат этого метода будет лежать в поле hash? И при переопределении метода hashCode() мы переопределяем именно этот метод?

Но дальше по классу я нахожу следующий метод: static final int hash(Object key), который уже вычисляется как:

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

Описание этого метода в документации мне почти ничего не дало. Это хеш-функция, которая вычисляет нужную ячейку массива? Если нет, то где она?

При добавлении объекта в HashMap, вычисляется хеш (хеш-код) ключа, который мы получаем в результате работы метода hashCode(), а далее хеш-функция в результате своей работы "получает" индексы нужных ячеек массива для вставки?
 
 
Сообщения:9915
Как работает HashMap и почему

Прежде чем разбираться в деталях, давай об общей картине. Нам нужно разместить N объектов в массиве потому как элементы в массиве можно быстро вытащить по индексу. Однако у нашего обычного объекта нет понятия индекса - как узнать в какую ячейку массива его положить? Для этого мы вычисляем хеш код - он и будет нашим индексом. Однако хеш код может быть огромным числом в то время как массив у нас может состоять из мм... 16и элементов. А создавать массив из миллиарда элементов только ради того чтоб занести наш объект в миллиардную ячейку - памяти не хватит. Поэтому мы этот хеш код должны как-то трансформировать в значения от 0 до 15 (если размер массива 16). И вот для этого используется модульная арифметика. Другое название - часовая арифметика.

Можно представить циферблат и там стрелка - когда значение достигает 12и стрелка возвращается на самом деле в начало - в 0. И круг начинается снова. Т.е. мы можем взять большие числа и заключить таким образом их в диапазон малых чисел. Так, к примеру: 101 % 10 = 1.

Т.е. чтоб построить HashMap нам нужно сгенерировать хеш код, вычислить его модуль - это и есть индекс ячейки в массиве. Правда, может так случиться что два хеш кода попадут в одну и ту же ячейку: 1 % 16 = 17 % 16. Это называется коллизией. Из этого положения можно выйти разными подходами - один из них называется linear probing (реализован в IdentityHashMap), однако HashMap использует external chaining - т.е. в ячейке на самом деле содержится список (chain). А уже в списке может содержаться несколько значений у которых один и тот же хеш код. Чтоб определить есть ли в HashMap'e некий ключ - мы сначала вычислим по его хеш коду ячейку, а затем пройдемся по списку и уже сравним объекты по equals(). И так найдем какой из двух объектов - наш.

А теперь ответы

hsadik:
Хеш-функция и хеш-код это вроде бы разные понятия, но почему-то в некоторых статьях я не раз видел, что их смешивают и приравнивают
Хеш-функция - это алгоритм который вычисляет некоторое короткое значение по объекту/данным. Вызвав два раза хеш функцию с одним объектом мы должны получить одно и то же значение. Хеш-кодом в Java называют либо само посчитанное значение, либо функцию hashCode() (которая и является хеш-функцией).
hsadik:
Я попробовал посмотреть в документации (я не программист, я учу язык) и попробовал что-то найти. Внутри массива в ячейках лежат узлы (класс Node). В этом классе есть поле hash - это и есть тот самый хеш-код?
Да, в Node.hash записывается результат выполнения твоего hashCode(). С небольшим уточнением (ниже).
hsadik:
Также там есть метод hashCode(), который вычисляется так:

return Objects.hashCode(key) ^ Objects.hashCode(value);

Но я думал, что хеш-код вычисляется только по ключу? Именно результат этого метода будет лежать в поле hash?
Нет, это hashCode() самого класса Node. Для него поля key, value, hash - являются своими личными полями (хоть они и получены из твоих объектов). Зачем этому классу hashCode() - хороший вопрос, я не думаю что его кто-то помещает еще в какую-то другую HashMap'у. Возможно он был реализован потому что в этом классе нужен метод equals(), а определяя его принято переопределять и hashCode().

hsadik:
Но дальше по классу я нахожу следующий метод: static final int hash(Object key), который уже вычисляется как:

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

Описание этого метода в документации мне почти ничего не дало.
Вот key.hashCode() - это твой хеш код. Собсно мог бы и он напрямую использоваться, однако в качестве оптимизации есть еще смещение бит. Т.е. в Node.hash на самом деле хранится не твой посчитанный hashCode() - он еще немного модифицируется. Это сделано потому что hashCode() можно реализовать так что только нижние биты int'a будут заполнены. Например, Integer, Float - если мы в HashMap кладем маленькие значения, то у них и биты хешкодов будут заполнены только нижние. В таком случае ключи в хеш мапе будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми. Что не эффективно.

hsadik:
Это хеш-функция, которая вычисляет нужную ячейку массива? Если нет, то где она?
Функция которая вычисляет ячейку не может зависеть только от хеш кода - она еще должна зависеть от кол-ва ячеек в хеш-мапе. Поэтому нет, этот код не может вычислять ячейку. Вот то что ты ищешь (это Java8):
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
А конкретнее: i = (n - 1) & hash. Как видишь на самом деле здесь используется не модульная арифметика, а немного другой алгоритм, но функционирует он так же - ограничивает миллиарды разных значений набором маленьких значений. Если кол-во ячеек = 16, то n-1=15. Это значит что нижние 4 бита заполнены единицами: 00000000 00000000 00000000 00001111. Делая операцию & мы у нашего хеш кода отметаем все значения что стоят выше этих 4х бит. Так, 17 & 16 = 1:
00000000 00000000 00000000 00001111
& 
00000000 00000000 00000000 00010001
=
00000000 00000000 00000000 00000001
Нам нужно чтоб в конце нашего размера массива в таком случае были только 1111... Именно поэтому размер внутреннего массива обязан быть степенью двойки: 16, 64, 128 и т.д.
Изменен:16 янв 2020 18:09
 
 
Сообщения:4
Староверъ, Большое Вам спасибо за столь развернутый ответ!
Староверъ:
Node. Для него поля key, value, hash - являются своими личными полями (хоть они и получены из твоих объектов). Зачем этому классу hashCode() - хороший вопрос, я не думаю что его кто-то помещает еще в какую-то другую HashMap'у. Возможно он был реализован потому что в этом классе нужен метод equals(), а определяя его принято переопределять и hashCode().


А это может быть связано с тем, что связный список в корзине при заполнении перестраивается в дерево и для этого ему нужен этот самый хеш?
Староверъ:
Вот key.hashCode() - это твой хеш код. Собсно мог бы и он напрямую использоваться, однако в качестве оптимизации есть еще смещение бит. Т.е. в Node.hash на самом деле хранится не твой посчитанный hashCode() - он еще немного модифицируется.

Ага, значит для своих классов я переопределяю этот самый хеш-код, а затем с ним проводятся дополнительные манипуляции в этом методе hash.
Теперь стало еще более понятно предназначение контракта (equals - hashcode). А при получении нужного объекта (get) мы получается передаем методу get() результат выполнения static final int hash(Object key) и сам ключ. А там внутри уже идет сравнение поля hash класса Node с тем, что мы ему передали. Находим подходящую ячейку, а далее по equals ищем объект.

P.S.
Староверъ:
Это сделано для потому что hashCode() можно реализовать так что только нижние биты int'a будут заполнены. Например, Integer, Float - если мы в HashMap кладем маленькие значения, то у них и биты хешкодов будут заполнены только нижние. В таком случае ключи в хеш мапе будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми. Что не эффективно.

Т.е. на то, в какой бакет попадёт новая запись, влияют только младшие биты хеша? Поэтому там какие-то манипуляции, чтобы старшие биты "смешать" с нижними?
Изменен:16 янв 2020 12:03
 
 
Сообщения:9915
hsadik:
А это может быть связано с тем, что связный список в корзине при заполнении перестраивается в дерево и для этого ему нужен этот самый хеш?
Нет, там используется Node.hash:
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
hsadik:
Т.е. на то, в какой бакет попадёт новая запись, влияют только младшие биты хеша? Поэтому там какие-то манипуляции, чтобы старшие биты "смешать" с нижними?
Да. Если кол-во бакетов 16, то у хеша возьмется только последние 4 бита. Если 32, то 5. Если 64, то 6 бит. И если у двух хешей заполнены только верхние биты, то оба они укажут на 0ую ячейку. У класса Float hashCode() просто берет битовое представление и переводит его в int:
    public static int hashCode(float value) {
        return floatToIntBits(value);
    }
Нижние биты в float отвечают за мантиссу (дробную часть) которая потом умножается на число полученное в экспоненте (верхние биты). Т.е. числа 1.0, 2.0, 4.0 (чистая экспонента без мантиссы) - у них нижние биты 0. Если бы shift'a не было, то они все попали бы в 0й бакет.

Ну и немного о том как это все использовать в реальной жизни. Чаще всего в веб приложениях объекты с одной ID не дублируются в памяти. Т.е. если мы вытащили из БД объект User=10, то мы не будем его еще раз вытаскивать. Поэтому когда мы будем складывать такие объекты в HashSet или делать их ключами в HashMap - им не нужен на самом деле equals/hashCode потому как это прям один и тот же объект. Другого объекта User=10 нет, соответственно мы можем не реализовывать equals/hashCode и будет использоваться стандартная реалицация которая определяет указывает ли ссылка на один и тот же объект.

Объекты с уникальной ID называют Entity. Также есть понятие Value Object - это чаще всего обертка над 1 или парочкой примитивов которая более предметно-ориентированная. Т.е. вместо того чтоб работать везде с double я могу создать классы Money, Volume, Mass, Hour - у них будут полезные методы специфичные именно для них (а не просто общие методы по работе с Double). У таких классов нет ID - это просто значения обернутые в классы. Вот им чаще всего нужны equals/hashCode.
Изменен:16 янв 2020 18:19
 
 
Сообщения:4
Староверъ, Благодарю!

А вот у меня еще возник вопрос.
Когда мы добавляем новый элемент (Node) мы смотрим, есть ли уже в этом бакете элементы. Если нет, то просто вставляем новый.
А вот если элемент(ы) в бакете уже есть, тогда мы сначала сравниваем хеши ключей. Если сравнение возвращает false, тогда остальная часть условия игнорируется, так как объекты гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неравенства, ключи сравниваются уже методом equals(). И новый элемент вставляется в конец списка, если объекты разные, иначе новый перезаписывает старый.

Вот в этом участке:
if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))


Но получается, что это применимо к одному элементу? Так как я не вижу здесь какого-либо цикла, чтобы сравнивать эти параметры во всех элементах в списке. Ведь судя по этому коду, если в одной корзине допустим 1 элемент, добавляю в этот же бакет 2, сравниваю, они не равны, добавляю, окей тут понятно. Пробую вставить 3 элемент в этот самый бакет, так с чем он будет сравниваться? С каким элементом? Со всеми? Но вроде бы это не исходит из кода. Для меня это магия, которой я не вижу в коде :)

А, кажись разобрался и вопрос отпал, цикл дальше же идет:
for (int binCount = 0; ; ++binCount)
Изменен:17 янв 2020 15:18
 
Модераторы:frymock
Сейчас эту тему просматривают:Нет