Кадом усулҳо метавонанд барои кам кардани эҳтимолияти бархӯрдиҳо дар истифодаи таблицҳои хеш истифода шаванд?

Барои коҳиш додани эҳтимолияти муноқишаҳо (коллизияҳо) дар ҷадвалҳои ҳеш истифода мешаванд усулҳои зерин:

1. Танзим кардани функсияи ҳеши хуб — функсия бояд калидҳоро ба таври баробар тақсим кунад, то эҳтимолияти коллизияҳоро кам кунад.

2. Ғайр аз он, андозаи ҷадвалро зиёд кардан — ҳарчанд ки ҷадвал калонтар бошад, эҳтимолияти ду калид дар як ҳуҷра афтодан камтар мешавад.

3. Истифодаи усулҳои ҳал кардани коллизияҳо:

   • Нақшаи кушод (сонджии хаттӣ, квадратикии сонджӣ, дуруст ҳеш) — дар ҳолати коллизия, ҷустуҷӯи ҳуҷраи оянда мешавад.
   • Занҷирбандӣ (chaining) — дар ҳар ҳуҷра рӯйхати пайваст ё дигар контейнер барои ҳамаи элементҳо бо ҳамон ҳеш нигоҳ дошта мешавад.

4. Рехешинг (тарҳрезӣ) — вақте ки фоизи боркунӣ ба ҳадди муайян мерасад, андозаи ҷадвал зиёд карда мешавад ва элементҳо дубора тақсим мешаванд.

Масалан дар 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
    }
}