Hash cədvəllərindən istifadə edərkən toqquşma ehtimalını azaltmaq üçün hansı metodlar istifadə oluna bilər?

Hash cədvəllərində toqquşma ehtimalını azaltmaq üçün aşağıdakı metodlar tətbiq olunur:

1. Yaxşı bir hash funksiyası seçmək — funksiya açarları bərabər şəkildə hash cədvəlinə paylamalı və toqquşma ehtimalını minimuma endirməlidir.

2. Cədvəlin ölçüsünü artırmaq — array-in ölçüsü nə qədər böyük olarsa, iki açarın eyni hüceyrəyə düşmə ehtimalı o qədər az olur.

3. Toqquşma həll üsullarından istifadə etmək:

   • Açıq ünvanlama (xətti axtarış, kvadrat axtarış, ikili hash) — toqquşma baş verdikdə, növbəti boş hüceyrə axtarılır.
   • Zəncir (chaining) — hər hüceyrədə, eyni hash-ə malik bütün elementləri saxlayan əlaqəli siyahı və ya başqa konteyner yerləşir.

4. Rehashing (ölçünü artırmaq) — müəyyən yüklənmə faktoru çatdıqda, ölçü artırılır və elementlər yenidən paylanır.

Kotlin-də zəncir nümunəsi:

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