Кои методи могат да се използват за намаляване на вероятността от сблъсъци при използване на хеш таблици?

За намаляване на вероятността от сблъсъци (колизии) в хеш таблиците се използват следните методи:

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

2. Увеличаване на размера на таблицата — колкото по-голям е масивът, толкова по-малка е вероятността два ключа да попаднат в една и съща клетка.

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

   • Отворена адресация (линейно пробване, квадратно пробване, двойно хеширане) — при колизия се търси следващата свободна клетка.
   • Връзки (chaining) — във всяка клетка се съхранява свързан списък или друг контейнер за всички елементи с еднакъв хеш.

4. Рехеширане (resize) — при достигане на определен коефициент на натоварване, размерът се увеличава и елементите се преразпределят.

Пример на 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
    }
}