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

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

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

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

Μια συνάρτηση κατατεμαχισμού μπορεί να αντιστοιχίζει δύο ή περισσότερες εισόδους στην ίδια τιμή κατατεμαχισμού. Στις περισσότερες εφαρμογές είναι επιθυμητή η ελαχιστοποίηση αυτών των συγκρούσεων. Αυτό σημαίνει ότι η συνάρτηση κατατεμαχισμού θα πρέπει να αντιστοιχίζει κάθε είσοδο σε διαφορετική τιμή κατατεμαχισμού. Ανάλογα με την εφαρμογή χρήσης, η συνάρτηση κατατεμαχισμού σχεδιάζεται με διαφορετικές προδιαγραφές. Η ιδέα αυτών των συναρτήσεων εμφανίστηκε το 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). Επειδή η έξοδος είναι αυστηρότερα μοναδική, αυτές οι συναρτήσεις πολλές φορές χρησιμοποιούνται και ως γενικής χρήσεως συναρτήσεις κατατεμαχισμού.