Κατακερματισμός

Εισαγωγή

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

Ορισμοί

• Ονομάζουμε πυκνότητα κλειδιών (key density) το λόγο του πληθαρίθμου του συνόλου του πεδίου τιμών προς τον πληθάριθμο του συνόλου του πεδίου ορισμού της συνάρτησης κατακερματισμού.
• Η διεύθυνση στην οποία απεικονίζει η συνάρτηση κατακερματισμού το κλειδί ονομάζεται βασική διεύθυνση (hash address).
• Ονομάζουμε συντελεστή φόρτισης (loading factor) το λόγο των στοιχείων της δομής που έχουν καταληφθεί προς τα στοιχεία της δομής που παραμένουν ελεύθερα.
• Συνώνυμα (Synonyms) είναι δύο κλειδιά για τα οποία η συνάρτηση κατακερματισμού δίνει την ίδια τιμή.
• Η παραπάνω κατάσταση ονομάζεται σύγκρουση (collision).
• Υπερχείλιση (Overflow) είναι η διαδικασία που εκτελείται για να υπερβούμε το πρόβλημα που δημιουργεί μια σύγκρουση.
• Η συνάρτηση κατακερματισμού καλείται ομοιόμορφη (uniform) αν είναι ίσες οι πιθανότητες απεικόνισης κάθε πιθανής τιμής του κλειδιού.
• Τέλος, η συνάρτηση κατακερματισμού καλείται τέλεια (perfect) αν ο αριθμός των δυνατών κλειδιών ταυτίζεται με τον πληθάριθμο του πεδίου τιμών της συνάρτησης χωρίς τη δημιουργία συγκρούσεων.

Συναρτήσεις κατακερματισμού

• Λογικές μέθοδοι βασισμένες σε συναρτήσεις όπως η αποκλειστική διάζευξη.
• Πολλαπλασιαστικές μέθοδοι βασισμένες στον πολλαπλασιασμό.
• Χρήση του υπολοίπου.
• Χρήση του μέσου του τετραγώνου.
• Μετατροπή βάσης.
• Διάσπαση του κλειδιού και πρόσθεση των τμημάτων.
• Αναδίπλωση των άκρων.

Διαχείριση συγκρούσεων

• Απευθείας σύνδεση του στοιχείου που καταλαβάνει τη θέση με το νέο στοιχείο το οποίο φυλάσσεται σε μια άλλη περιοχή.
• Γραμμική εξέταση: το στοιχείο φυλάσσεται στην πρώτη επόμενη κενή θέση του αρχείου.
• Δευτεροβάθμια εξέταση: αν η θέση κ είναι γεμάτη το στοιχείο φυλάσσεται σε κάποια θέση (κ+i*i) mod β όπου i = 1 ...

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 208-221 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Donald E. Knuth. The Art of Computer Programming, volume 3 / Searching and Sorting. Addison-Wesley, second edition, 1973.

• Niklaus Wirth. Algorithms + Datastructures = Programs. p. 169-280. Prentice-Hall, 1976.

Ασκήσεις

Άσκηση ADS09 (προαιρετική)

1. Να υλοποιηθεί σε Pascal πρόγραμμα το οποίο διαβάζει 5 ακεραίους και τους αποθηκεύει με κατακερματισμό σε πίνακα 50 θέσεων. Στην συνέχεια ζητάει κατ' εξακολούθηση από το χρήστη να δώσει έναν ακέραιο αριθμό και τυπώνει στην οθόνη αν ο αριθμός αυτός ήταν ανάμεσα στους 5 ή όχι. Το ενδεχόμενο της υπερχείλισης να μην εξεταστεί.

   Παράδειγμα:

   454
   3466
   456
   23
   199
   Give number: 123
   Not known
   Give number: 456
   Known
   

• Περιεχόμενα

 Τελευταία αλλαγή: Δευτέρα, 22 Μαρτίου 1999 1:59 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».