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

Εισαγωγή

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

Ορισμοί

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

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

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

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

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

Υλοποίηση σε C

Ο παρακάτω πίκανας απεικονίζει τους αντίστοιχους αριθμούς ν στην αρχιτεκτονική Intel Pentium:

Τύπος	ν (bits)
unsigned char	8
unsigned short	16
unsigned int	32
unsigned long	32

Έτσι για παράδειγμα σε πρόσθεση δύο τιμών τύπου unsigned char 250 + 10 το αποτέλεσμα θα είναι 4 μια και 260 mod 2 ⁸ = 4. Η ιδιότητα αυτή σε συνδυασμό με τις πράξεις πάνω σε bits που ορίζει η C μας επιτρέπει να ορίζουμε εύκολα συναρτήσεις κατακερματισμού.

Οι τελεστές για πράξεις πάνω σε bits ακεραίων αριθμών είναι οι παρακάτω:

Τελεστής	Πράξη
|	σύζευξη (or)
&	διάζευξη (and)
^	αποκλειστική διάζευξη (exclusive or)
~	άρνηση (negation)

Μια συνάρτηση κατακερματισμού συμβολοσειράς σε τιμή 0-127 με βάση την αποκλειστική διάζευξη μπορεί να υλοποιηθεί ως εξής:

unsigned int
hash(unsigned char string)
{
	char *s;
	unsigned char sum = 0;

	for (*s = string; *s; s++)
		sum ^= *s;
	return (sum & 127);
}

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

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 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.

Ασκήσεις

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

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

   Παράδειγμα:

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

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

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