В прошлом посте был показан механизм работы хэш-таблицы, который состоит в вычислении индекса массива с помощью так называемой хэш функции:
val index = hash(key)
// хэш таблица под капотом является обычным массивом
hashMap[index] = value
// хэш-функция вычисляет индекс практически моментально
fun hash(...) { ... }
К сожалению не все так просто и хэш функции порой возвращают один и тот же индекс для разных ключей, это называется коллизией, есть несколько вариантов как их разрулить:
1. Затирать предыдущие значения
Это может быть полезно в кэшировании, где данные не прям важны, но все должно работать моментально.
2. Использовать дополнительные структуры данных
Как раз текущая реализация хэш-таблицы в Kotlin (JVM таргет) и Java юзает этот вариант: при возникновении коллизии, создается связанный список куда кладутся все значения с одинаковым индексом, если возникнет ситуация когда список стал очень большим (плохая работа хэш-функции, неправильное переопределение hashCode и тд), на его замену приходит красно-черное дерево.
3. Использовать специальные алгоритмы
Почему бы в случае коллизии просто не попытаться использовать другой индекс:
// i это номер попытки, к примеру вычислили индекс для ключа3, а там уже есть ключ1, попробовали прибавить некоторое значение, а там ключ2 и так пока не найдется свободное место
val i = 1,2,3
// алгоритм линейного пробирования, просто прибавляем номер попытки (увеличиваем индекс на единицу) пока не найдется свободное место
val nexIndex = index + i
// алгоритм квадратичного пробирования, прибавляем помимо номера попытки еще и степень этой попытки, это увеличивает интервал между коллизиями и лучше распределяет значения по таблице
val newIndex = index + i + i*i
Кстати алгоритм квадратичного пробирования используется в структурах данных AndroidX Collection, вот классная статейка про разбор коллекций из этой библиотеки:
https://habr.com/en/articles/811415
Всем хорошего кода!