Здравствуйте, я начал свое знакомство с классом HashMap в Java и ввиду расхождений в разных источниках, которые запутали меня, возник вопрос насчет хеширования и поиска нужного индекса в хеш-таблице.
Хеш-функция и хеш-код это вроде бы разные понятия, но почему-то в некоторых статьях я не раз видел, что их смешивают и приравнивают, что вводит меня в дополнительную путаницу. Да и большинство статей с подробным разбором довольно старые. Например, в Java 7 индекс нужной ячейки вычислялся в методе indexFor, сейчас же его нет (использую JDK 12). Прошу помощи, чтобы я смог разобраться и не плутал вокруг этого уже третий день.
Я попробовал посмотреть в документации (я не программист, я учу язык) и попробовал что-то найти. Внутри массива в ячейках лежат узлы (класс Node). В этом классе есть поле hash - это и есть тот самый хеш-код?
Также там есть метод hashCode(), который вычисляется так:
Но я думал, что хеш-код вычисляется только по ключу? Именно результат этого метода будет лежать в поле hash? И при переопределении метода hashCode() мы переопределяем именно этот метод?
Но дальше по классу я нахожу следующий метод: static final int hash(Object key), который уже вычисляется как:
Описание этого метода в документации мне почти ничего не дало. Это хеш-функция, которая вычисляет нужную ячейку массива? Если нет, то где она?
При добавлении объекта в HashMap, вычисляется хеш (хеш-код) ключа, который мы получаем в результате работы метода hashCode(), а далее хеш-функция в результате своей работы "получает" индексы нужных ячеек массива для вставки?
Сергей Горностаев, Возможно, но я не лезу в мудреные закрытые методы, которых там навалом. По сути, это же основы работы hashmap, которые я так и не совсем понял.
hsadik, в исходный код стандартной библиотеки или виртуальной машины вообще редко кто лезет. Обычно это сеньоры, имеющие за плечами не менее десятка лет работы и столкнувшиеся с проблемами производительности в очень нестандартном сценарии эксплуатации. Для обычной ежедневной работы вполне достаточно знания публичного интерфейса.
Сергей Горностаев, Я подобным образом разобрал ArrayList и LinkedList, и вот подошел к мапе. Я полез в исходный код не для того, чтобы модифицировать что-то, а чтобы понять, как работает хеш-мапа в Java, так как нормальных статей, которые применимы хотя бы к Java 8 просто нет.
hsadik, ваше желание разобраться в деталях я считаю похвальным. Продолжайте в том же духе.
Хэш ключа вычисляет метод static final int hash(Object key). Как вы уже увидели, он обращается к методу hashCode ключа. Для Object это нативный метод, то есть реализованный на C в коде виртуальной машины. Вероятно, вам будет интересно почитать этот ответ. Он про Java 8, но принципиально ничего не изменилось.
Сергей Горностаев,
Т.е. hash это просто дополнительный метод (хеш-функция), который проводит какие-то преобразования с тем, что получилось в hashCode()?
А зачем в самом Node существует метод hashCode()? На что он влияет?
И где определяется индекс нужной ячейки? Он же должен как-то отличаться от хеш-кода. Я знаю, что в Java 7 для этого использовался метод indexFor(), который принимал на вход полученный хеш-код и длину внутреннего массива:
return h & (length-1). А сейчас его найти не могу, а соответственно как же все-таки начиная с Java 8 определяется нужный индекс.
Простой
