Τι είναι ένα κατακερματισμό;

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

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

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

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

Πολλοί ερευνητές της επιστήμης των υπολογιστών έχουν προσπαθήσει να παράγουν την τέλεια λειτουργία κατακερματισμού mdash;ένα που δεν παράγει συγκρούσεις ή συστάδες που έχουν έναν αυξανόμενο συντελεστή φορτίου.Θεωρητικά, το κλειδί για την παραγωγή ενός τέλειου κατακερματισμού είναι να παράγει μια τέλεια λειτουργία κατακερματισμού.Γενικά, οι ερευνητές πιστεύουν ότι μια τέλεια λειτουργία κατακερματισμού πρέπει να έχει συνεχή απόδοση mdash;ο αριθμός των συγκρούσεων και των συστάδων mdash;με αυξανόμενο συντελεστή φορτίου.Στη χειρότερη περίπτωση, μια τέλεια λειτουργία κατακερματισμού θα εξακολουθούσε να επιτρέπει τη συνεχή κατακερματισμό χωρίς να φτάσει σε ένα κατώφλι.