Μπορείς να δώσεις παραδείγματα τρόπων αντιμετώπισης συγκρούσεων κατά την εργασία με πίνακες κατακερματισμού;

Όταν εργάζεστε με πίνακες κατακερματισμού, συγκρούσεις (collisions) συμβαίνουν όταν διαφορετικά κλειδιά κατακερματίζονται στο ίδιο κελί. Οι κύριοι τρόποι επίλυσης των συγκρούσεων:

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

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

Παράδειγμα μεθόδου αλυσίδας:

class HashTable {
    var buckets: [[(key: String, value: Int)]]
    
    init(size: Int) {
        buckets = Array(repeating: [], count: size)
    }
    
    func hash(_ key: String) -> Int {
        return abs(key.hashValue) % buckets.count
    }
    
    func insert(key: String, value: Int) {
        let index = hash(key)
        buckets[index].append((key, value))
    }
}

Έτσι, η επιλογή της μεθόδου εξαρτάται από τις απαιτήσεις απόδοσης και μνήμης.