Πώς είναι δομημένος ένας πίνακας κατακερματισμού στο…

Το unordered_map σε C++ υλοποιείται ως πίνακας κατακερματισμού.

Αρχή λειτουργίας:

Κατακερματισμός: Το κλειδί μετατρέπεται σε ακέραιο αριθμό — κωδικός κατακερματισμού — με τη βοήθεια μιας συνάρτησης κατακερματισμού.
Δεικτοδότηση: Ο κωδικός κατακερματισμού χρησιμοποιείται για τον προσδιορισμό του δείκτη (κουβάς ή bucket) σε έναν πίνακα δεικτών ή λιστών.
Αποθήκευση: Σε κάθε κουβά αποθηκεύονται ζεύγη κλειδιού-τιμής.

Χαρακτηριστικά:

Κουβάδες: Ο πίνακας κατακερματισμού αποτελείται από έναν πίνακα κουβάδων. Ο αριθμός των κουβάδων μπορεί να αλλάξει δυναμικά (rehashing) όταν επιτευχθεί ένας συγκεκριμένος δείκτης φόρτωσης.
Συγκρούσεις: Διάφορα κλειδιά μπορούν να δώσουν τον ίδιο κωδικό κατακερματισμού. Αυτό ονομάζεται σύγκρουση. Για την επίλυση συγκρούσεων, το unordered_map χρησιμοποιεί τη μέθοδο ** chaining **: τα στοιχεία με τον ίδιο hash προστίθενται σε μια συνδεδεμένη λίστα (ή άλλη δομή δεδομένων) στον αντίστοιχο κουβά.
Συνάρτηση κατακερματισμού και συνάρτηση σύγκρισης: Για σωστή λειτουργία, χρειάζονται δύο πράγματα:
- Μια καλή συνάρτηση κατακερματισμού, που διανέμει ομοιόμορφα τα κλειδιά στους κουβάδες, ελαχιστοποιώντας τις συγκρούσεις.
- Μια συνάρτηση ισοδυναμίας (==), για να διακρίνει τα κλειδιά με τον ίδιο κωδικό κατακερματισμού στον ίδιο κουβά.
Απόδοση: Κατά μέσο όρο, οι λειτουργίες εισαγωγής, διαγραφής και αναζήτησης έχουν χρονική πολυπλοκότητα O(1). Στην χειρότερη περίπτωση (π.χ., πολλαπλές συγκρούσεις ή κακή επιλογή συνάρτησης κατακερματισμού), η απόδοση μπορεί να επιδεινωθεί σε O(n), όπου n είναι ο αριθμός των στοιχείων.

Παράδειγμα δομής (απλοποιημένο):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Για συνδεδεμένη λίστα στον κουβά
};

struct Bucket {
  Node* head; // Δείκτης στην αρχή της λίστας
};

Bucket* buckets; // Πίνακας κουβάδων
size_t num_buckets;

Διαδικασία προσθήκης στοιχείου:

Υπολογίζεται ο κωδικός κατακερματισμού του κλειδιού.
Ορίζεται ο δείκτης του κουβά: bucket_index = hash(key) % num_buckets.
Το ζεύγος κλειδιού-τιμής προστίθεται στη λίστα στοιχείων σε αυτόν τον κουβά. Αν το κλειδί ήδη υπάρχει, η τιμή ενημερώνεται.

Διαδικασία αναζήτησης στοιχείου:

Υπολογίζεται ο κωδικός κατακερματισμού του κλειδιού.
Ορίζεται ο δείκτης του κουβά.
Διατρέχεται η λίστα στοιχείων σε αυτόν τον κουβά, συγκρίνοντας τα κλειδιά με το ζητούμενο κλειδί χρησιμοποιώντας τον τελεστή ==.

Ο rehashing πραγματοποιείται όταν ο αριθμός των στοιχείων σε σχέση με τον αριθμό των κουβάδων υπερβαίνει ένα όριο (παραγόμενος παράγοντας φόρτωσης). Κατά το rehashing, δημιουργείται ένας νέος, μεγαλύτερος πίνακας κουβάδων, και όλα τα στοιχεία από τους παλιούς κουβάδες επαναhash-άρονται και μετακινούνται στους νέους.

Πώς είναι δομημένος ένας πίνακας κατακερματισμού στο δοχείο unordered_map;