Какими методами можно снизить вероятность столкновений при использовании хеш-таблиц?

Для снижения вероятности столкновений (коллизий) в хеш-таблицах применяются следующие методы:

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

2. Увеличение размера таблицы — чем больше размер массива, тем меньше вероятность, что два ключа попадут в одну ячейку.

3. Использование методов разрешения коллизий:

   • Открытая адресация (linear probing, quadratic probing, double hashing) — при коллизии ищется следующая свободная ячейка.
   • Цепочки (chaining) — в каждой ячейке хранится связанный список или другой контейнер для всех элементов с одинаковым хешем.

4. Ре-хеширование (resize) — при достижении определённой загрузки таблицы (load factor) увеличивается размер и перераспределяются элементы.

Пример на Kotlin (цепочки):

class HashTable<K, V>(val size: Int) {
    private val buckets = Array<MutableList<Pair<K, V>>>(size) { mutableListOf() }

    private fun hash(key: K): Int = key.hashCode().absoluteValue % size

    fun put(key: K, value: V) {
        val index = hash(key)
        val bucket = buckets[index]
        val existing = bucket.indexOfFirst { it.first == key }
        if (existing >= 0) bucket[existing] = key to value
        else bucket.add(key to value)
    }

    fun get(key: K): V? {
        val index = hash(key)
        return buckets[index].firstOrNull { it.first == key }?.second
    }
}