Συνάρτηση κατατεμαχισμού

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Η συγκεκριμένη συνάρτηση κατατεμαχισμού (hash function) αντιστοιχίζει ονόματα-κλειδιά (keys) σε ακέραιους αριθμούς από το 0 μέχρι και 15 (τιμές κατατεμαχισμού - hashes). Στο συγκεκριμένο παράδειγμα υπάρχει μια σύγκρουση κλειδιών. Το όνομα-κλειδί "John Smith" και "Sandra Dee" έχουν την ίδια τιμή κατατεμαχισμού.

Η συνάρτηση κατατεμαχισμού, γνωστή και ως συνάρτηση κατακερματισμού, είναι μια μαθηματική συνάρτηση που έχοντας ως είσοδο μια αυθαίρετου μεγέθους ομάδα δεδομένων δίνει έξοδο μια καθορισμένου μεγέθους στοιχειοσειρά (string) (συνήθως ένα ακέραιο αριθμό), πολύ μικρότερη από την είσοδο. Η έξοδος της συνάρτησης μπορεί να χρησιμοποιηθεί ως δείκτης σε κάποιο πίνακα. Οι τιμές που επιστρέφει η συνάρτηση κατατεμαχισμού ονομάζονται τιμές κατατεμαχισμού (hash values), κώδικες κατατεμαχισμού (hash codes), αθροίσματα κατατεμαχισμού (hash sums) ή απλά τιμές κατατεμαχισμού (hashes).

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

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

Οι συναρτήσεις κατατεμαχισμού συσχετίζονται (αν και πολλές φορές μπερδεύονται ως έννοιες) με τις συναρτήσεις αθροίσματος ελέγχου (π.χ. ο Κυκλικός Έλεγχος Πλεονασμού), τον υπολογισμό ψηφίου ελέγχου (check digit), δακτυλικά αποτυπώματα (fingerprints), κώδικες ελέγχου λαθών (error correcting codes) και την κρυπτογραφική συνάρτηση κατατεμαχισμού.

Εφαρμογές συναρτήσεων κατατεμαχισμού[Επεξεργασία | επεξεργασία κώδικα]

Πίνακες κατατεμαχισμού[Επεξεργασία | επεξεργασία κώδικα]

Παράδειγμα πίνακα κατατεμαχισμού. Το κάθε όνομα (key) αντιστοιχίζεται σε την βοήθεια της συνάρτησης κατατεμαχισμού (hash function) σε ένα πίνακα κατατεμαχισμού (hash table) που δημιουργεί αντιστοιχίσεις σε αριθμούς τηλεφώνων (ευρετήριο κατατεμαχισμού).

Οι συναρτήσεις κατατεμαχισμού κυρίως χρησιμοποιούνται σε πίνακες κατατεμαχισμού (hash tables), για γρήγορη εύρεση εγγραφών σε βάσεις δεδομένων. Για παράδειγμα σε ένα λεξικό έχουμε τις λέξεις-κλειδιά και τους αντίστοιχους ορισμούς-περιγραφές. Η συνάρτηση κατατεμαχισμού μπορεί να εξυπηρετήσει αντιστοιχώντας τις λέξεις-κλειδιά με τις αντίστοιχες τιμές κατατεμαχισμού (ονομάζεται πίνακας κατατεμαχισμού - hash table, στην ελληνική βιβλιογραφία αναφέρεται και ως πίνακας κατακερματισμού).

Σε γενικές γραμμές μια συνάρτηση κατατεμαχισμού μπορεί να αντιστοιχίζει διαφορετικά κλειδιά στην ίδια τιμή κατατεμαχισμού. Τότε η τιμή κατατεμαχισμού αντιστοιχίζει σε ένα σύνολο από εγγραφές, αντί για μια μόνο εγγραφή. Για αυτόν ακριβώς η/οι εγγραφή/ές που αντιστοιχίζει μια τιμή κατατεμαχισμού ονομάζεται bucket (μεταφράζεται ως κουβάς ή κάδος και σημαίνει μονάδα αποθήκευσης). Ο πίνακας κατατεμαχισμού τότε ονομάζεται ευρετήριο κατατεμαχισμού (hash indices ή bucket indices).

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

Αλγόριθμοι συναρτήσεων κατατεμαχισμού[Επεξεργασία | επεξεργασία κώδικα]

Συναρτήσεις αθροισμάτων ελέγχου[Επεξεργασία | επεξεργασία κώδικα]

Έλεγχος ακεραιότητας κατεβασμένων αρχείων π.χ. από το Διαδίκτυο: Σε μεγάλα downloads, μπορούμε συνήθως να κατεβάσουμε και ένα αρχείο αθροίσματος ελέγχου (checksum) που περιέχει μέσα την τιμές κατατεμαχισμού του μεγάλου αρχείου. Εκτελώντας τη συνάρτηση κατατεμαχισμού στο δικό μας μηχάνημα, μπορούμε να συγκρίνουμε τις συνόψεις: αν είναι ίδιες το αρχείο έχει κατέβει σωστά.

Κρυπτογραφικές συναρτήσεις κατατεμαχισμού[Επεξεργασία | επεξεργασία κώδικα]

Η κρυπτογραφική συνάρτηση κατατεμαχισμού SHA-1. Εδώ φαίνονται μόνο τα 4 πρώτα bytes (4*8=32bits) σε δεκαεξαδική μορφή της συνάρτησης SHA-1 (η έξοδος της SHA-1 είναι 160bits ή 20bytes).

Οι κρυπτογραφικές συναρτήσεις όπως η SHA-1 παρέχουν εγγύηση ότι η έξοδος για κάθε διαφορετική είσοδο είναι μοναδική σε σύγκριση με τις "χαλαρότερες" συναρτήσεις αθροίσματος ελέγχου ή τα συναρτήσεις δακτυλικών αποτυπωμάτων (fingerprints). Επειδή η έξοδος είναι αυστηρότερα μοναδική, αυτές οι συναρτήσεις πολλές φορές χρησιμοποιούνται και ως γενικής χρήσεως συναρτήσεις κατατεμαχισμού.

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Hash function της Αγγλόγλωσσης Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).