Πώς λειτουργεί ένας πίνακας κατακερματισμού;

Ένα πίνακας κατακερματισμού (hash table) είναι μια δομή δεδομένων που υλοποιεί έναν συσχετιστικό πίνακα.

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

1. Κατακερματισμός. Για κάθε κλειδί (key), υπολογίζεται ένας κωδικός κατακερματισμού (hash code) με μια συνάρτηση κατακερματισμού (hash function). Ο κωδικός κατακερματισμού είναι ένας ακέραιος αριθμός.
2. Δεικτοδότηση. Ο κωδικός κατακερματισμού χρησιμοποιείται για τον προσδιορισμό ενός δείκτη (index) στον εσωτερικό πίνακα (ή διανύσμα) της δομής. Συνήθως, ο δείκτης υπολογίζεται ως hash_code % μέγεθος_πίνακα, όπου μέγεθος_πίνακα είναι το μέγεθος του πίνακα.
3. Αποθήκευση. Στον βρεθέντα δείκτη αποθηκεύεται η τιμή (value) που σχετίζεται με το κλειδί.

Προβλήματα και λύσεις:

• Συγκρούσεις. Διάφορα κλειδιά μπορεί να δίνουν τον ίδιο κωδικό κατακερματισμού και, κατά συνέπεια, τον ίδιο δείκτη στον πίνακα. Αυτό ονομάζεται σύγκρουση.
  • Μέθοδοι επίλυσης συγκρούσεων:
    • Μέθοδος αλυσίδας (Separate Chaining): Σε κάθε κελί του πίνακα αποθηκεύεται μια λίστα (λίστα, διανύσμα, κ.λπ.) ζευγών "κλειδί-τιμή". Σε περίπτωση σύγκρουσης, το νέο ζευγάρι προστίθεται σε αυτή τη λίστα. Κατά την αναζήτηση με βάση τον δείκτη, διατρέχεται η αντίστοιχη λίστα για να βρεθεί το επιθυμητό κλειδί.
    • Μέθοδος ανοικτής διεύθυνσης (Open Addressing): Σε περίπτωση σύγκρουσης, αναζητείται άλλο ελεύθερο κελί στον πίνακα σύμφωνα με έναν ορισμένο κανόνα (δοκιμή).
      • Γραμμική δοκιμή (Linear Probing): Ελέγχονται διαδοχικά τα κελιά index + 1, index + 2, κ.λπ., modulo το μέγεθος του πίνακα.
      • Τετραγωνική δοκιμή (Quadratic Probing): Ελέγχονται τα κελιά index + 1^2, index + 2^2, κ.λπ., modulo το μέγεθος του πίνακα.
      • Διπλό κατακερματισμό (Double Hashing): Χρησιμοποιείται μια δεύτερη συνάρτηση κατακερματισμού για τον προσδιορισμό του βήματος δοκιμής.

Πλεονεκτήματα:

• Κατά μέσο όρο, οι λειτουργίες εισαγωγής, διαγραφής και αναζήτησης εκτελούνται με πολυπλοκότητα O(1).

Μειονεκτήματα:

• Στην χειρότερη περίπτωση (π.χ., πολλαπλές συγκρούσεις ή κακή συνάρτηση κατακερματισμού), η πολυπλοκότητα των λειτουργιών μπορεί να φτάσει το O(n), όπου n είναι ο αριθμός των στοιχείων.
• Απαιτεί επιπλέον μνήμη (π.χ., για λίστες στη μέθοδο αλυσίδας ή για δοκιμές στην ανοικτή διεύθυνση).

Παράδειγμα χρήσης σε C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Δημιουργία πίνακα κατακερματισμού (unordered_map)
    std::unordered_map<std::string, int> ηλικίες;

    // Εισαγωγή στοιχείων
    ηλικίες["Alice"] = 30;
    ηλικίες["Bob"] = 25;
    ηλικίες["Charlie"] = 35;

    // Λήψη τιμής με βάση το κλειδί
    std::cout << "Ηλικία της Alice: " << ηλικίες["Alice"] << std::endl;

    // Αναζήτηση στοιχείου
    if (ηλικίες.count("Bob")) {
        std::cout << "Ο Bob είναι στον χάρτη." << std::endl;
    }

    // Διαγραφή στοιχείου
    ηλικίες.erase("Charlie");

    return 0;
}