Ποια μέθοδοι μπορούν να χρησιμοποιηθούν για να μειωθεί η πιθανότητα συγκρούσεων κατά τη χρήση πινάκων κατακερματισμού;

Για τη μείωση της πιθανότητας συγκρούσεων στους πίνακες κατακερματισμού, εφαρμόζονται οι ακόλουθες μέθοδοι:

1. Επιλογή καλής συνάρτησης κατακερματισμού — η συνάρτηση πρέπει να διανέμει ομοιόμορφα τα κλειδιά στον πίνακα, ελαχιστοποιώντας την πιθανότητα συγκρούσεων.

2. Αύξηση του μεγέθους του πίνακα — όσο μεγαλύτερος είναι ο πίνακας, τόσο μικρότερη είναι η πιθανότητα δύο κλειδιά να καταλήξουν στο ίδιο κελί.

3. Χρήση μεθόδων επίλυσης συγκρούσεων:

   • Ανοιχτή διεύθυνση (γραμμική αναζήτηση, τετραγωνική αναζήτηση, διπλό κατακερματισμό) — σε περίπτωση σύγκρουσης, αναζητείται το επόμενο ελεύθερο κελί.
   • Αλυσίδες (chaining) — σε κάθε κελί αποθηκεύεται μια συνδεδεμένη λίστα ή άλλο κοντέινερ για όλα τα στοιχεία με το ίδιο hash.

4. Rehashing (αλλαγή μεγέθους) — όταν επιτευχθεί ένας ορισμένος παράγοντας φόρτωσης, το μέγεθος αυξάνεται και τα στοιχεία αναδιανέμονται.

Παράδειγμα σε 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
    }
}