Συνάρτηση κατακερματισμού
From Wikipedia, the free encyclopedia
Η συνάρτηση κατακερματισμού, γνωστή και ως συνάρτηση κατατεμαχισμού, είναι μια μαθηματική συνάρτηση που δέχεται ως είσοδο κάποιο δεδομένο τυχαίου μεγέθους και επιστρέφει ένα ακέραιο σταθερού μεγέθους αναπαράστασης. Το μέγεθος αυτό μπορεί να είναι από 32bit μέχρι 256bit ή περισσότερα, ανάλογα με το λόγο χρήσης της συνάρτησης. Οι τιμές που επιστρέφει η συνάρτηση κατατεμαχισμού ονομάζονται τιμές κατατεμαχισμού (hash values), κώδικες κατατεμαχισμού (hash codes), αθροίσματα κατατεμαχισμού (hash sums) ή απλά τιμές κατατεμαχισμού (hashes).
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Οι τιμές αυτές θα πρέπει να είναι διαφορετικές για διαφορετική είσοδο, καθώς η κύρια χρησιμότητα αυτών των συναρτήσεων είναι να ταυτοποιούν τα δεδομένα. Μια εφαρμογή αυτή της ιδιότητας είναι στην υλοποίηση της δομής δεδομένων σύνολο όπου θα πρέπει να αποτρέπεται η προσθήκη στοιχείου που το σύνολο ήδη περιέχει. Σε αυτή την περίπτωση τιμές 32bit αρκούν, εκτός αν το σύνολο μπορεί να φτάσει υπερβολικά μεγάλο μέγεθος. Μια άλλη εφαρμογή είναι στη δημιουργία ψηφιακών υπογραφών όπου χρησιμοποιούνται τιμές κατατεμαχισμού μεγάλου μεγέθους για να ελαχιστοποιηθεί ο κίνδυνος πλαστογράφησής τους.
Μια συνάρτηση κατατεμαχισμού μπορεί να αντιστοιχίζει δύο ή περισσότερες εισόδους στην ίδια τιμή κατατεμαχισμού. Στις περισσότερες εφαρμογές είναι επιθυμητή η ελαχιστοποίηση αυτών των συγκρούσεων. Αυτό σημαίνει ότι η συνάρτηση κατατεμαχισμού θα πρέπει να αντιστοιχίζει κάθε είσοδο σε διαφορετική τιμή κατατεμαχισμού. Ανάλογα με την εφαρμογή χρήσης, η συνάρτηση κατατεμαχισμού σχεδιάζεται με διαφορετικές προδιαγραφές. Η ιδέα αυτών των συναρτήσεων εμφανίστηκε το 1950 αλλά ακόμη και σήμερα ο σχεδιασμός μιας καλής συνάρτησης κατατεμαχισμού είναι αντικείμενο έρευνας.
Οι συναρτήσεις κατατεμαχισμού συσχετίζονται (αν και πολλές φορές μπερδεύονται ως έννοιες) με τις συναρτήσεις αθροίσματος ελέγχου (π.χ. ο Κυκλικός Έλεγχος Πλεονασμού), τον υπολογισμό ψηφίου ελέγχου (check digit), δακτυλικά αποτυπώματα (fingerprints) και τους κώδικες ελέγχου λαθών (error correcting codes)..