Хэш-таблицы, часть II. В прошлом посте был показан механизм работы хэш-таблицы, который состоит в вычислении индекса массива с помощью так называемой хэш функции: 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 Всем хорошего кода!