Что такое коллизия java

Разрешение коллизий

Разрешение коллизий (англ. collision resolution) в хеш-таблице, задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицами.

Разрешение коллизий с помощью цепочек

Разрешение коллизий при помощи цепочек.

Каждая ячейка [math]i[/math] массива [math]H[/math] содержит указатель на начало списка всех элементов, хеш-код которых равен [math]i[/math] , либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.

В зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, время вставки в который будет в худшем случае равна [math]O(1)[/math] . Иначе мы проверяем есть ли в списке данный элемент, а потом в случае его отсутствия мы его добавляем. В таком случае вставка элемента в худшем случае будет выполнена за [math]O(n)[/math]

Время работы поиска в наихудшем случае пропорционально длине списка, а если все [math]n[/math] ключей захешировались в одну и ту же ячейку (создав список длиной [math]n[/math] ) время поиска будет равно [math]\Theta(n)[/math] плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех [math]n[/math] элементов.

Удаления элемента может быть выполнено за [math]O(1)[/math] , как и вставка, при использовании двухсвязного списка.

Линейное разрешение коллизий

Пример хеш-таблицы с открытой адресацией и линейным пробированием.

Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.

Стратегии поиска

Последовательный поиск

При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+1, i+2, i+3[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.

Линейный поиск

Выбираем шаг [math]q[/math] . При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+(1 \cdot q), i+(2 \cdot q), i+(3 \cdot q)[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент. По сути последовательный поиск — частный случай линейного, где [math]q=1[/math] .

Квадратичный поиск

Шаг [math]q[/math] не фиксирован, а изменяется квадратично: [math]q = 1,4,9,16. [/math] . Соответственно при попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math] i+1, i+4, i+9[/math] и так далее, пока не найдём свободную ячейку.

Проверка наличия элемента в таблице

Проверка осуществляется аналогично добавлению: мы проверяем ячейку [math]i[/math] и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.

При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.

Проблемы данных стратегий

Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров — последовательностей занятых ячеек.

Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер. Для защиты от кластеризации используется двойное хеширование и хеширование кукушки.

Удаление элемента без пометок

Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на [math]q[/math] позиций назад. При этом:

• если в цепочке встречается элемент с другим хешем, то он должен остаться на своём месте (такая ситуация может возникнуть если оставшаяся часть цепочки была добавлена позже этого элемента)
• в цепочке не должно оставаться «дырок», тогда любой элемент с данным хешем будет доступен из начала цепи

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

function delete(Item i): j = i + q while table[j] == null or table[j].key != table[i].key if table[j] == null table[i] = null return j += q table[i] = table[j] delete(j)

Хеш-таблицу считаем зацикленной

Асимптотически время работы [math]\mathrm[/math] и [math]\mathrm[/math] совпадают

Вариант с зацикливанием мы не рассматриваем, поскольку если [math]q[/math] взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций

Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.

• В редактируемой цепи не остаётся дырок

Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце [math]\mathrm[/math] (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.

• Элементы, которые уже на своих местах, не должны быть сдвинуты.

• В других цепочках не появятся дыры

Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на [math]q[/math] позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно.

Двойное хеширование

Двойное хеширование (англ. double hashing) — метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.

Принцип двойного хеширования

При двойном хешировании используются две независимые хеш-функции [math] h_1(k) [/math] и [math] h_2(k) [/math] . Пусть [math] k [/math] — это наш ключ, [math] m [/math] — размер нашей таблицы, [math]n \bmod m [/math] — остаток от деления [math] n [/math] на [math] m [/math] , тогда сначала исследуется ячейка с адресом [math] h_1(k) [/math] , если она уже занята, то рассматривается [math] (h_1(k) + h_2(k)) \bmod m [/math] , затем [math] (h_1(k) + 2 \cdot h_2(k)) \bmod m [/math] и так далее. В общем случае идёт проверка последовательности ячеек [math] (h_1(k) + i \cdot h_2(k)) \bmod m [/math] где [math] i = (0, 1, \; . \;, m — 1) [/math]

Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за [math]O(1)[/math] , в худшем — за [math]O(m)[/math] , что не отличается от обычного линейного разрешения коллизий. Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной.

[math]\forall x \neq y \; \exists h_1,h_2 : p(h_1(x)=h_1(y))\gt p((h_1(x)=h_1(y)) \land (h_2(x)=h_2(y)))[/math]

Выбор хеш-функций

[math] h_1 [/math] может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, [math] h_2 [/math] должна возвращать значения:

• не равные [math] 0 [/math]
• независимые от [math] h_1 [/math]
• взаимно простые с величиной хеш-таблицы

Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а [math] h_2 [/math] возвращает натуральные числа, меньшие [math] m [/math] . Второй — размер таблицы является степенью двойки, а [math] h_2 [/math] возвращает нечетные значения.

Например, если размер таблицы равен [math] m [/math] , то в качестве [math] h_2 [/math] можно использовать функцию вида [math] h_2(k) = k \bmod (m-1) + 1 [/math]

Вставка при двойном хешировании

Пример

Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

[math] h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod 13 [/math]

[math] h_1(k) = k \bmod 13 [/math]

[math] h_2(k) = 1 + k \bmod 11 [/math]

Мы хотим вставить ключ 14. Изначально [math] i = 0 [/math] . Тогда [math] h(14,0) = (h_1(14) + 0\cdot h_2(14)) \bmod 13 = 1 [/math] . Но ячейка с индексом 1 занята, поэтому увеличиваем [math] i [/math] на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При [math] i = 2 [/math] получаем [math] h(14,2) = (h_1(14) + 2\cdot h_2(14)) \bmod 13 = 9 [/math] . Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Таким образом, основная особенность двойного хеширования состоит в том, что при различных [math] k [/math] пара [math] (h_1(k),h_2(k)) [/math] дает различные последовательности ячеек для исследования.

Простая реализация

Пусть у нас есть некоторый объект [math] item [/math] , в котором определено поле [math] key [/math] , от которого можно вычислить хеш-функции [math] h_1(key)[/math] и [math] h_2(key) [/math]

Так же у нас есть таблица [math] table [/math] величиной [math] m [/math] , состоящая из объектов типа [math] item [/math] .

function add(Item item): x = h1(item.key) y = h2(item.key) for (i = 0..m) if table[x] == null table[x] = item return x = (x + y) mod m table.resize()// ошибка, требуется увеличить размер таблицы

Item search(Item key): x = h1(key) y = h2(key) for (i = 0..m) if table[x] != null if table[x].key == key return table[x] else return null x = (x + y) mod m return null 

Реализация с удалением

Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив [math]deleted[/math] типов [math]bool[/math] , равный по величине массиву [math]table[/math] . Теперь при удалении мы просто будем помечать наш объект как удалённый, а при добавлении как не удалённый и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.

function add(Item item): x = h1(item.key) y = h2(item.key) for (i = 0..m) if table[x] == null or deleted[x] table[x] = item deleted[x] = false return x = (x + y) mod m table.resize()// ошибка, требуется увеличить размер таблицы

Item search(Item key): x = h1(key) y = h2(key) for (i = 0..m) if table[x] != null if table[x].key == key and !deleted[x] return table[x] else return null x = (x + y) mod m return null 

function remove(Item key): x = h1(key) y = h2(key) for (i = 0..m) if table[x] != null if table[x].key == key deleted[x] = true else return x = (x + y) mod m

Альтернативная реализация метода цепочек

В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию сбалансированного дерева. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан линейный порядок. То есть при использовании данныx типа [math]\mathbf[/math] или [math]\mathbf[/math] имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с [math]O(n)[/math] до [math]O(\log(n))[/math] . Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.

См. также

• Хеширование
• Хеширование кукушки
• Идеальное хеширование

Источники информации

• Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в Delphi», 2003
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом «Вильямс», 2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
• Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г.— ISBN 0-201-89685-0
• Седжвик Р. «Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск», 2003
• Handle Frequent HashMap Collisions with Balanced Trees
• Wikipedia — Double_hashing
• Разрешение коллизий
• Пример хеш таблицы
• Пример хеш таблицы с двойным хешированием

Что такое HashMap

Программирование

Автор Михаил Граблевский На чтение 6 мин Просмотров 3.9к. Опубликовано 02.11.2019

Почему я выбрал эту тему? Ее нужно знать обязательно если Вы пришли на собеседование. Не знаете = не готовы!
Ниже я перечислил наиболее популярные вопросы по этой теме. Для тех кому лень читать – можно посмотреть видос.

Расскажите про устройство HashMap?

Во-первых что такое HashMap? HashMap – это ассоциативный массив. Если вкратце, то ассоциативный массив – это структура данных, которая хранит пары ключ-значения.

Чтобы было проще понять что это такое, можно представлять HashMap как пронумерованные корзинки, в которых хранятся какие-то данные. При добавлении нового объекта в HashMap, мы помимо самого объекта передаем еще и ключ, по которому в дальнейшем, его можно будет отыскать.

Как по ключу можно определить положение искомого объекта? Для этого нам нужно знать hashCode ключа. Где же его взять? Все очень просто, если понимать, что в качестве ключа, может выступать любой объект в java. Все знают что класс Object реализует метод hashCode(), это означает что он будет унаследован или переопределен самим “ключом”. Т.к. все в java наследуются от класса Object. Теперь понятно откуда у ключа берется hashCode!

После того как в hashMap, был передан ключ + сохраняемый объект, специальная hash-функция вычисляет то в какую корзину отнести наши данные.

Как вы понимаете, никаких корзинок в HashMap-е нет. Вместо них есть массив, который хранит ссылки на связанные списки в которых хранятся наши данные. Каждому элементу массива соответствует один список.

Какое начальное количество корзин в HashMap?
Данный вопрос мне ни разу не задавали я его нашел на хабре. Ответ – 16. Но как и с ArrayList-ом в конструкторе можно задать другое количество.

Что такое коллизия? Способ решения коллизий.
Этот вопрос так же часто встречается. Коллизия это когда два разных объекта попадают в одну корзинку(связанный список). Причиной этому служит то, что они имеют одинаковый hashcode. Для более эффективной работы с HashMap, hashcode не должен повторяться для не эквивалентных объектов.

Как я уже упомянул выше, все данные хранятся в списках. Почему так? Почему не хранить всего один объект? Ответ прост. Все потому, что это способ разрешения коллизий. Как происходит добавление? Смотр код 1

Первое – мы выясняем то какая корзина соответствует ключу объекта. Затем проверяем, есть ли в ней уже какие-то объекты, если нет – то добавляем текущий. Если да, то это случилась коллизия.
Тогда мы начинаем сравнивать ключ и hashcode текущего объекта и тех которые внутри (если конечно их там несколько).
Сначала проверяем равны ли hashcode ключей.
Если да, то сравниваем их ключ методом equals.
Если equals возвращает true, значит ключи совпадают по “значению” и hashcode – производится замена, новый объект заменяет тот который уже там находится под тем же ключом,
Если hashcode и “значение” ключа неравны – новый объект добавляется в конец списка.

if (e.hash == hash && (e.key == key || key.equals(e.key)))

Как и когда происходит увеличение количества корзин в HashMap?
HashMap имеет поле loadFactor. Оно может быть задано через конструктор. По умолчанию равняется 0.75. Для чего оно нужно? Его произведение на количество корзин дает нам необходимое число объектов, которое нужно добавить, чтобы состоялось удвоение количества корзин. Например, если у нас мапка с 16-ю корзинами, а loadFactor равняется 0.75, то расширение произойдет когда мы добавим 16 * 0.75 = 12 объектов. Мапка увеличивается вдвое.

Какая оценка временной сложности операций с HashMap? Гарантирует ли HashMap указанную сложность выборки элемента?
Рассмотрим сначала случай в котором нет коллизий. В этом случае добавление, удаление и поиск объектов по ключу выполняется за константное время O(1). Разумеется, не учитывается случай с расширением количества элементов. Вообще говоря, когда Вы работаете с HashMap, лучше сразу указать в конструкторе, сколько корзин нужно для работы и хорошо если оно равняется числу уникальных объектов с которыми Вы будите работать. В таком случае не придется тратить время и ресурсы на создание нового HashMap с удвоенным количеством bucket-ов. Почему такая хорошая производительность? Тут все просто. Повторюсь что коллизий нет – в таком случае нет никакой зависимости от других элементов из этой мапки. Удаление, Вставка, Поиск выполняются примерно по одной схеме. Берется HashCode ключа, вычисляется корзинка, и производится удаление, вставка или поиск. Все! Нигде не встречаются другие объекты. Но это лишь в том случае, если нет коллизий.

Теперь поговорим о случае когда коллизии все-таки присутствуют. Теоретически работая с HashMap в котором могут присутствовать коллизии, мы получаем временную сложность O(log(n)) на операции вставки, сохранения и удаления. В самом худшем случае, когда все объекты возвращают один и тот же HashCode, а значит попадают в одну корзину. На самом деле это связный список и тогда временная сложность как у LinkedList O(n).

Вопросы на собеседовании 2. HashMap.

Предположим, что в мапку, созданную данным способом (Код 1), нужно добавить 1 миллион объектов. Что тут плохого? Давайте подумаем.

Map map = new HashMap();

Как обычно, видос для ленивых:

Что произойдет, когда выполнится данный код? Создастся массив на 16 элементов с loadFactor = 0.75. Получаем, что после добавления 12 элементов произойдет удвоение длинны массива. Напомню, что это число получается перемножив loadFactor и текущее количество корзинок или длину массива.

Как-бы, что тут плохого, ну удвоилось количество корзинок, можно добавлять дальше. Нет! Все работает не так. После того как состоялось удвоение, все элементы, которые уже были добавлены, будут перераспределены по корзинкам заново с учетом их нового количества.

Добавили 12. Потом эти 12 снова добавили, после увеличения массива. Грубо говоря добавили всего 24. Что получаем? В следующий раз, удвоение числа корзинок произойдет после добавления 24-го элемента, а в мапке уже 12.

Добавили еще 12 + снова перераспределение и еще 24, получаем 36.
Представляете сколько нужно будет выполнить работы, пока мы не закончим добавлять все 1 миллион объектов.

Когда я обдумывал данный пример, предполагал, что коллизий нет совсем. Боюсь представить, что было бы, если бы они все таки присутствовали.

В каком случае может быть потерян элемент в HashMap?

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

Java Blog

До Java 8, HashMap и все другие классы реализации карты на основе хэш-таблиц в Java обрабатывают столкновения путем объединения в цепочку, то есть они используют связанный список для хранения записей карты, которые заканчиваются в той же корзине из-за столкновения. Если ключ попадает в то же место корзины, где уже хранится запись, то эта запись просто добавляется в начало связанного списка. В худшем случае это снижает производительность метода get() HashMap до O(n) с O(1). Чтобы решить эту проблему в случае частых конфликтов HashMap, Java 8 начала использовать сбалансированное дерево вместо связанного списка для хранения конфликтующих записей. Это также означает, что в худшем случае вы получите прирост производительности с O(n) до O(log n).

Порог переключения на сбалансированное дерево определяется как константа TREEIFY_THRESHOLD в коде java.util.HashMap JDK 8. В настоящее время его значение равно 8, что означает, что если в одной корзине более 8 элементов, то HashMap будет использовать дерево вместо связанного списка для хранения их в одной корзине.

• Методы класса Object в Java
• Различия между Array и ArrayList в Java
• В чем будет проблема, если не переопределять метод hashCode()

Коллизии HashCode

Представьте, вы пишите мессенжер или почтовый клинт. Вам придется работать с кучей повторяющихся строковых значений. Например в чате — какой-то влюбленный Вася может спамить десятки аналогичных признаний в любви своей даме сердца Насте. Но мы то знаем, что все Насти шлю** Наверняка мы захотим как-то кэшировать эти сообщения. Для этого подойдет HashMap или HashSet, например. Все знают, что эти структуры данных, ссылаются на хэш значение объекта, которое не бесконечно, а ограничено 32 битами. Но проблемы могут начаться уже с пары строк.

Пример такой коллизии:

fun main()  ​//generates 310265957 as hashcode ​​print("I have a common prefixDB".hashCode()) //generates 310265957 as hashcode print("I have a common prefixCa".hashCode()) >

Вообще если длина строк одинаковая и выполняется:

31*(b[n-2] — a[n-2]) == (a[n-1] — b[n-1])

то, хэши всегда будут одинаковыми, не буду вдаваться в подробности почему так 😀

Окей, хэши могут быть одинаковыми на ровном месте, но по какому принципу они рассчитываются?

Стандартная реализация hashCode

Посмотри сгенерированный idea hashCode() для простого POJO класса.

class Lover( private val id: Long, private val name: String, private val mum: Mum? )  // Также генерится реализация equals, зачем она нужна узнаем ниже override fun equals(other: Any?): Boolean  if (this === other) return true if (javaClass != other?.javaClass) return false other as Lover if (id != other.id) return false if (name != other.name) return false if (mum != other.mum) return false return true > override fun hashCode(): Int  var result = id.hashCode() result = 31 * result + name.hashCode() result = 31 * result + (mum?.hashCode() ?: 0) // Если объект null, он не влияет return result > >

У String, кстати свой алгоритм: h(s)=∑(s[index] * 31 ^(n-1-index)) Смысл тот же, только проходим по всем char

31

Как вы заметили везде используется это непонятное число 31. Вопрос: А че не 41 или 97, например?

А по каким критериям оно отбирается?

• Число должно быть простым и нечетным, чтобы уменьшить вероятность коллизий.
• Число должно занимать мало места в памяти
• Умножение должно выполняться быстро

Оказывается 31 идеальный кандидат ведь:

• Оно простое и нечетное
• Занимает всего 1 байт в памяти
• Уго умножение можно заменить на быстрый побитовой сдвиг. 31 * i == (i

Побитовой сдвиг влево на x позиций. Работает точно также как умножить какое-то число на 2 x раз.

println(n.shl(1)) // 6 println(n.shl(2)) // 12 println(n.shl(3)) // 24

Вернемся к сути.

Окей, выяснили, по какому принципу считается HashCode и что в любой момент может произойти коллизия и данные перетрутся. Так че делать?

Да ничего, HashMap и HashSet самоcтоятельно обрабытывают такие ситуации. Важно только правильно переопределить метод equals(o) у класса.

Логика работы такая:

1. Кладем в список объект по ключу “cat”
2. Кладем в него другой по этому же ключу
3. HashMap/Set проверяет равны ли эти объекты в методе equals
4. Если равны — заменяет, если нет, создает в этой ячейке связный список, а например в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.

Важно помнить, что получение элемента из связного списка работает за время O(n), и если колиизий наберется много, скорость hash таблицы станет уже далеко не константной.

Поэтому если все же решили использовать String в качестве ключа, можно за основу брать 2 простых числа, скажем 17 и 37. Ребята из Project Lombok придумали здесь

fun main(args: ArrayString>)  val first = BetterHashString("I have a common prefixDB") val second = BetterHashString("I have a common prefixCa") println(first.hashCode()) // 177503352 println(second.hashCode()) // 177503346 > class BetterHashString(val value: String)  override fun hashCode(): Int  val prime = 37 var result = 17 value.chars().forEach  c -> result = prime * result + c > return result > >

Минуточку

Переопределил я hashCode() , но как-же теперь JVM узнает, на какой адрес в памяти ссылается этот объект?

На самом деле у каждого объекта есть идентификационный хеш (identity hash code). Если класс переопределил hashCode() , всегда можно вызвать System.identityHashCode(o) .

Да и вообще, hashCode() не возвращает какой-либо адрес объекта в памяти, что бы это не значило. В версиях java 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока. Подробнее об этом можно почитать здесь