What methods can reduce the likelihood of collisions when using hash tables?

The following methods are used to reduce the likelihood of collisions in hash tables:

1. Choosing a good hash function — the function should distribute keys evenly across the hash table, minimizing the probability of collisions.

2. Increasing the size of the table — the larger the array size, the less likely it is that two keys will land in the same cell.

3. Using collision resolution methods:

   • Open addressing (linear probing, quadratic probing, double hashing) — when a collision occurs, the next free cell is searched.
   • Chaining — each cell contains a linked list or another container for all elements with the same hash.

4. Re-hashing (resizing) — when a certain load factor is reached, the size is increased and elements are redistributed.

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