Welche Methoden können verwendet werden, um die Wahrscheinlichkeit von Kollisionen bei der Verwendung von Hashtabellen zu verringern?

Um die Wahrscheinlichkeit von Kollisionen in Hash-Tabellen zu verringern, werden folgende Methoden angewendet:

1. Wahl einer guten Hash-Funktion — die Funktion sollte die Schlüssel gleichmäßig auf die Hash-Tabelle verteilen, um die Wahrscheinlichkeit von Kollisionen zu minimieren.

2. Erhöhung der Tabellengröße — je größer das Array, desto geringer ist die Wahrscheinlichkeit, dass zwei Schlüssel in die gleiche Zelle fallen.

3. Verwendung von Kollisionsauflösungsmethoden:

   • Offene Adressierung (lineares Sondieren, quadratisches Sondieren, doppelte Hashing) — bei Kollision wird die nächste freie Zelle gesucht.
   • Chaining (Verkettung) — in jeder Zelle wird eine verkettete Liste oder ein anderer Container für alle Elemente mit demselben Hash gespeichert.

4. Rehashing (Neugestaltung) — wenn ein bestimmter Ladefaktor erreicht ist, wird die Größe erhöht und die Elemente neu verteilt.

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