Welke methoden kunnen worden gebruikt om de kans op botsingen te verminderen bij het gebruik van hash-tabellen?

Om de kans op botsingen in hash-tabellen te verminderen, worden de volgende methoden gebruikt:

1. Kies een goede hashfunctie — de functie moet de sleutels gelijkmatig over de hash-tabel verdelen, zodat de kans op botsingen minimaal is.

2. Vergroot de grootte van de tabel — hoe groter de array, hoe kleiner de kans dat twee sleutels in dezelfde cel terechtkomen.

3. Gebruik methoden voor het oplossen van botsingen:

   • Open adressering (lineair zoeken, kwadratisch zoeken, dubbele hashing) — bij botsing wordt de volgende vrije cel gezocht.
   • Chaining (kettingvorming) — elke cel bevat een gekoppelde lijst of een andere container voor alle elementen met dezelfde hash.

4. Rehashing (resizing) — wanneer een bepaald laadfactor wordt bereikt, wordt de grootte vergroot en worden de elementen opnieuw verdeeld.

Voorbeeld in Kotlin (chaining):

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