Τι είναι ένας συσχετιστικός πίνακας;

Ένας συσχετιστικός πίνακας, που ονομάζεται επίσης πίνακας κατακερματισμού ή χάρτης κατακερματισμού, είναι παρόμοιος με έναν τυποποιημένο πίνακα εκτός από τον δείκτη του πίνακα μπορεί να είναι μια συμβολοσειρά αντί για έναν ακέραιο.Σε πολλές εφαρμογές βάσης δεδομένων και σε άλλα προγράμματα που ασχολούνται με μεγάλα ποσά δεδομένων, ένας συσχετιστικός πίνακας είναι ένα ζωτικό στοιχείο για να βοηθήσει στην ταξινόμηση και την πρόσβαση σε πληροφορίες με αποτελεσματικό τρόπο.Στον πυρήνα ενός συσχετιστικού πίνακα υπάρχει ένας τυπικός πίνακας που είναι ευρετηριασμένη με ακέραιους, όπως θα συνέβαινε κανονικά.Ένας ειδικός αλγόριθμος που ονομάζεται συνάρτηση κατακερματισμού μετατρέπει τον δείκτη συμβολοσειράς σε ένα ευρετήριο ακέραιο για να βρει την τιμή.Πρόκειται για μια συνεπή μετατροπή, οπότε ο πραγματικός δείκτης ακέραιων δεν πρέπει ποτέ να αποθηκευτεί, αλλά αντ 'αυτού υπολογίζεται από τη συμβολοσειρά όπως απαιτείται κάθε φορά.

Η ορολογία που χρησιμοποιείται όταν αναφέρεται σε μια συσχετιστική συστοιχία μπορεί να είναι ελαφρώς διαφορετική από αυτό που χρησιμοποιείται όταν μιλάμε γιαένας κανονικός πίνακας.Αυτό που κανονικά θα ονομαζόταν δείκτης mdash;Η αριθμητική θέση ενός στοιχείου μέσα σε μια συστοιχία mdash;ονομάζεται κλειδί.Τα δεδομένα που σχετίζονται με το κλειδί ονομάζονται τιμή.Αυτό σημαίνει ότι, μέσα σε μια συσχετιστική συστοιχία, ένα κλειδί συνδέεται με μια τιμή, η οποία συσχετίζεται με έναν δείκτη που αναφέρεται σε ένα στοιχείο σε μια τυπική συστοιχία στη δομή δεδομένων.Αυτός είναι ένας αλγόριθμος που χρησιμοποιείται για τον προσδιορισμό του αριθμητικού δείκτη μιας τιμής που βασίζεται στο κλειδί.Υπάρχουν διάφοροι τύποι λειτουργιών κατακερματισμού, μερικοί που έχουν σχεδιαστεί για να λειτουργούν σε κλειδιά που είναι ακέραιοι και μερικοί σχεδιασμένοι να εργάζονται σε κλειδιά που είναι χορδές.Στην περίπτωση ενός κλειδιού ακέραιου αριθμού, μια δημοφιλής μέθοδος είναι να διαιρέσει την βασική τιμή από το μέγεθος της συστοιχίας και να χρησιμοποιήσει το υπόλοιπο της διαίρεσης, ελπίζουμε ότι θα πάρει μια μοναδική τιμή ευρετηρίου.

Η συνάρτηση κατακερματισμού μπορεί να είναι πολύ πιο περίπλοκηΓια τα πλήκτρα που είναι χορδές.Ορισμένες μέθοδοι περιλαμβάνουν την προσθήκη της αριθμητικής τιμής κάθε χαρακτήρα στη συμβολοσειρά και στη συνέχεια τη διαίρεση του με κάποιο αριθμό ή χρησιμοποιώντας μόνο τους πρώτους λίγους χαρακτήρες της συμβολοσειράς για να αποκτήσετε έναν μοναδικό αριθμό.Υπάρχουν πολλοί τρόποι για να εξαχθεί ένας αριθμός από μια σειρά από χαρακτήρες.

Όταν ασχολείσαι με ένα μεγάλο ποσό ζευγών κλειδιού-αξίας σε μια συσχετιστική συστοιχία, ένα πρόβλημα που μπορεί να προκύψει ονομάζεται σύγκρουση.Η σύγκρουση συμβαίνει όταν ο δείκτης ακέραιων ακέραιων που προέρχεται από ένα κλειδί είναι πανομοιότυπος με τον ακέραιο δείκτη ενός άλλου κλειδιού.Αυτά τα δύο πλήκτρα στη συνέχεια δείχνουν αποτελεσματικά τον ίδιο δείκτη στη συστοιχία τιμών.Υπάρχουν διάφορες λύσεις για σύγκρουση, κυρίως επειδή έχει μεγάλη πιθανότητα να συμβεί στις περισσότερες πρακτικές εφαρμογές.

Μια λύση για τη σύγκρουση είναι να έχει κάθε δείκτης αξίας να είναι στην πραγματικότητα ένας συνδεδεμένος κατάλογος έτσι ώστε, όταν περισσότερα από ένα κλειδί επιλύονται σε αυτόν τον δείκτηΤοποθεσία, η τοποθεσία μπορεί να κρατήσει περισσότερες από μία τιμές.Αυτό ονομάζεται Chaining και είναι ένας απλός τρόπος χειρισμού μιας σύγκρουσης, αν και μπορεί επίσης να επιβραδύνει το χρόνο που χρειάζεται για να ανακτήσει τις πληροφορίες.Μια άλλη μέθοδος αντιμετώπισης μιας σύγκρουσης ονομάζεται γραμμική ανίχνευση.Όταν συμβεί μια σύγκρουση, η γραμμική ανίχνευση λειτουργεί με τη μετάβαση στη συστοιχία τιμών μέχρι να βρεθεί ένας αχρησιμοποίητος δείκτης.Αυτή η λύση μπορεί να βοηθήσει στη διατήρηση των δεδομένων ομοιόμορφα διανεμημένα στον συσχετιστικό πίνακα, αλλά μπορεί επίσης να αυξήσει το χρονικό διάστημα που απαιτείται για να αναζητήσει μια τιμή.