Τι είναι ένας πίνακας κατακερματισμού;

Ο πίνακας κατακερματισμού, ή συσχετιστικός πίνακας, είναι μια δομή δεδομένων που υλοποιεί το διεπαφή συσχετιστικού πίνακα, δηλαδή συσχετίζει κλειδιά με τιμές. Χρησιμοποιεί μια συνάρτηση κατακερματισμού για τον υπολογισμό του δείκτη, ή "κατακερματισμό", του κουτιού ή της θέσης όπου πρέπει να βρίσκεται η ζητούμενη τιμή.

Βασικά στοιχεία:

• Κλειδί: Μοναδικός ταυτοποιητής του στοιχείου.
• Τιμή: Δεδομένα που σχετίζονται με το κλειδί.
• Συνάρτηση κατακερματισμού: Μετατρέπει το κλειδί σε αριθμητική τιμή (κατακερματισμό), που χρησιμοποιείται για τον προσδιορισμό του δείκτη του κουτιού.
• Κουτιά (Buckets): Πίνακας όπου αποθηκεύονται ζεύγη κλειδιού-τιμής.
• Διαχείριση συγκρούσεων (Collision Handling): Μηχανισμός επίλυσης καταστάσεων όπου διαφορετικά κλειδιά δίνουν τον ίδιο κατακερματισμό (και, κατά συνέπεια, δείχνουν σε ένα ίδιο κουτί). Δημοφιλείς μέθοδοι:
  • Μέθοδος αλυσίδας (Chaining): Σε κάθε κουτί αποθηκεύεται μια λίστα (π.χ., συνδεδεμένη λίστα) στοιχείων των οποίων οι κατακερματισμοί δείχνουν σε αυτό το κουτί.
  • Μέθοδος ανοικτής διεύθυνσης (Open Addressing): Σε περίπτωση σύγκρουσης, αναζητείται το επόμενο ελεύθερο κουτί χρησιμοποιώντας αλγόριθμους όπως η γραμμική, τετραγωνική ή διπλή κατακερματισμός.

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

1. Εισαγωγή: Η συνάρτηση κατακερματισμού εφαρμόζεται στο κλειδί για να ληφθεί ο κατακερματισμός. Ο κατακερματισμός χρησιμοποιείται για τον προσδιορισμό του δείκτη του κουτιού. Το ζεύγος κλειδιού-τιμής αποθηκεύεται σε αυτό το κουτί. Σε περίπτωση σύγκρουσης, εφαρμόζεται η μέθοδος διαχείρισης συγκρούσεων.

   // Παράδειγμα εισαγωγής στοιχείου στον πίνακα κατακερματισμού (μέθοδος αλυσίδας)
   function insert(key, value) {
     const hash = hashFunction(key); // Υπολογισμός κατακερματισμού
     const bucketIndex = hash % tableSize; // Ορισμός δείκτη κουτιού
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Δημιουργία λίστας αν δεν υπάρχει
     }
     buckets[bucketIndex].push({ key, value }); // Προσθήκη ζεύγους στη λίστα
   }
   

2. Αναζήτηση: Η συνάρτηση κατακερματισμού εφαρμόζεται στο κλειδί για να ληφθεί ο κατακερματισμός. Ο κατακερματισμός χρησιμοποιείται για τον προσδιορισμό του δείκτη του κουτιού. Στη συνέχεια, σε αυτό το κουτί, πραγματοποιείται αναζήτηση του στοιχείου με το δοσμένο κλειδί. Με τη μέθοδο αλυσίδας, αναζητείται στη λίστα εντός του κουτιού. Με την ανοικτή διεύθυνση, ελέγχονται διαδοχικά άλλα κουτιά μέχρι να βρεθεί το ζητούμενο στοιχείο ή να διαπιστωθεί η απουσία του.

   // Παράδειγμα αναζήτησης στοιχείου στον πίνακα κατακερματισμού (μέθοδος αλυσίδας)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Υπολογισμός κατακερματισμού
     const bucketIndex = hash % tableSize; // Ορισμός δείκτη κουτιού
   
     if (buckets[bucketIndex]) {
       // Αναζήτηση στοιχείου στη λίστα του κουτιού
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Αν χρειάζεται διαγραφή
           return value; // Επιστροφή τιμής
         }
       }
     }
     return undefined; // Το στοιχείο δεν βρέθηκε
   }
   

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

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

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

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