Kādiem veidiem var samazināt sadursmju iespējamību, izmantojot hašēšanas tabulas?

Lai samazinātu sadursmju (kolīziju) iespējamību hash tabulās, tiek izmantotas šādas metodes:

1. Izvēlēties labu hash funkciju — funkcijai jāizdala atslēgas vienmērīgi pa hash tabulu, samazinot kolīziju iespējamību.

2. Palielināt tabulas izmēru — jo lielāks masīvs, jo mazāka iespējamība, ka divi atslēgas nonāks tajā pašā šūnā.

3. Izmantot kolīziju risināšanas metodes:

   • Atvērtā adresešana (līnijas meklēšana, kvadrātveida meklēšana, dubultā hash) — kolīzijas gadījumā tiek meklēta nākamā brīvā šūna.
   • Saites (chaining) — katrā šūnā tiek glabāta saistīta saraksta vai cita konteineris ar visiem elementiem ar to pašu hash.

4. Rehashing (pārformatēšana) — kad sasniegts noteikts slodzes koeficients, izmērs tiek palielināts un elementi tiek pārkārtoti.

Piemērs Kotlin valodā (saites):

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
    }
}