Хеш, хеш-функция, хеширование и HashMap

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

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

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

Также там есть метод hashCode(), который вычисляется так:

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

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

Описание этого метода в документации мне почти ничего не дало - есть упоминание, что вычисляет хеш-код для ключа и какие-то сдвигами с XOR'ами. Так где вычисляется хеш-код? И где в таком случае хеш-функция, которая распределяет объекты по нужным ячейкам?

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

0

hsad, https://www.youtube.com/user/K... /playlists - очень доступно объясняет, как в детсаду))

0

Aviz__ , это конечно хорошо, но если давать ссылку, то на конкретный материал на канале, а не сам канал, на котором 500+ видео. Нашел видео про Collections (причем судя по дате Java 8 там не пахнет, а реализацию в 7 я уже видел и знаю), а он два часа рассказывает про большое O и сортировку слиянием и быструю сортировку - как раз то, что нужно (нет).

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

0

Тогда вот так
https://habr.com/ru/post/128017/

0

Вы сами себя запутываете, неизвестно зачем..

Хэш-функция - это любая функция, вычисляющая хэш, то есть некоторое значение заданной разрядности, однозначно вычисляемое по содержимому объекта.
hashCode() - это метод объекта Java, реализующий некоторую конкретную хэш-функцию, выбранную разработчиком класса для правильной идентификации объектов класса.

Как именно по hashCode() вычисляются индексы - зачем Вам это нужно на данном этапе? Главное, что нужно знать - что объекты с разным hashCode() будут храниться более эффективно

0

vcrop , там Java 7, а в Java 8 HashMap сильно поменялась.
Black Fregat снова вернусь к Java 7, и там был отдельный метод для вычисления нужного индекса - indexFor, который принимал хеш-код и длину внутреннего массива в качестве параметров и далее по формуле определял. А вот в Java 8 и выше его нет, поэтому я задался вопросом, как определяется этот индекс в Java 8+? Неужели прямо в этой хеш-функции?

Зачем мне нужно знать? Потому что я таким же образом разобрал ArrayList и LinkedList и перешел к мапе, но тут сложнее. Максимализм это, наверное.

0

Сообщение от hsad indexFor, который принимал хеш-код и длину внутреннего массива

Бегло посмотрел - там на деревьях реализация, массива нет, индекса нет
Может, попробуете не ходить "под капот"? Для работы обычно вполне достаточно внешних спецификаций

0

Сообщение от Black Fregat Бегло посмотрел - там на деревьях реализация, массива нет, индекса нет

а еще там огромный комментарий в начале класса написан

0

Бегло посмотрел - там на деревьях реализация, массива нет, индекса нет Может, попробуете не ходить "под капот"? Для работы обычно вполне достаточно внешних спецификаций

Как это массива нет? Хеш-таблица это и есть массив, который в каждой ячейке хранит связный список до тех пор, пока количество элементов в одном связном списке меньше 8 (при условии, что бакетов не меньше 64). Если их стало 8 или больше, тогда происходит переход от связного списка к красно-черному дереву (из Node в TreeNode).

Так вычисляется индекс нужной ячейки(бакета): i = (n - 1) & hash.

0