Ποιο είναι το αρχή λειτουργίας ενός πίνακα…

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

Βήματα:

Υπολογισμός του hash: Για ένα δοσμένο κλειδί, υπολογίζεται το hash.

<?php
$key = "example";
$hash = crc32($key); // Παράδειγμα απλής συνάρτησης hash

Ορισμός του δείκτη: Το hash μετατρέπεται σε δείκτη πίνακα, συνήθως με τη χρήση της λειτουργίας modulo του μεγέθους του πίνακα.
```
<?php
$arraySize = 10;
$index = $hash % $arraySize;
```
Πρόσβαση στο καλάθι: Γίνεται πρόσβαση στο αντίστοιχο καλάθι στον πίνακα χρησιμοποιώντας τον υπολογισμένο δείκτη.
Επίλυση συγκρούσεων: Δεδομένου ότι διαφορετικά κλειδιά μπορεί να έχουν το ίδιο hash (σύγκρουση), το καλάθι μπορεί να περιέχει πολλά ζεύγη "κλειδί-τιμή". Για την επίλυση συγκρούσεων, χρησιμοποιούνται διάφορες μέθοδοι:
- Μέθοδος αλυσίδας (Separate Chaining): Κάθε καλάθι αποθηκεύει μια λίστα (π.χ. συνδεδεμένη λίστα) ζευγών "κλειδί-τιμή" των οποίων τα hash ταιριάζουν.
- Μέθοδος ανοικτής διεύθυνσης (Open Addressing): Σε περίπτωση σύγκρουσης, πραγματοποιείται επαναληπτική αναζήτηση για ελεύθερο κελί στον πίνακα σύμφωνα με έναν κανόνα (γραμμική, τετραγωνική, διπλή κατακερματισμός).

Ενέργειες:

Εισαγωγή: Υπολογίζεται το hash του κλειδιού, ορίζεται ο δείκτης, και το ζεύγος "κλειδί-τιμή" τοποθετείται στο αντίστοιχο καλάθι. Σε περίπτωση σύγκρουσης, προστίθεται στη λίστα (αλυσίδα) ή αναζητείται ελεύθερη θέση.
Αναζήτηση: Υπολογίζεται το hash του κλειδιού, ορίζεται ο δείκτης. Στο αντίστοιχο καλάθι, αναζητείται η τιμή με βάση το κλειδί. Στη μέθοδο αλυσίδας, διατρέχονται τα στοιχεία της λίστας; στην ανοικτή διεύθυνση, πραγματοποιείται γραμμική αναζήτηση.
Διαγραφή: Υπολογίζεται το hash του κλειδιού, ορίζεται ο δείκτης. Στο αντίστοιχο καλάθι, βρίσκεται και διαγράφεται το ζεύγος με βάση το κλειδί.

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

Γρήγορη πρόσβαση σε στοιχεία (μέσος όρος O(1)).
Αποτελεσματική χρήση μνήμης.

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

Η απόδοση μπορεί να επιδεινωθεί με μεγάλο αριθμό συγκρούσεων.
Το μέγεθος του πίνακα μπορεί να απαιτεί ρύθμιση (rehashing) για διατήρηση της αποδοτικότητας.

Ποιο είναι το αρχή λειτουργίας ενός πίνακα κατακερματισμού;