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

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Εισαγωγή

Ορισμοί

Σε ένα σύστημα κατακερματισμού μπορούμε να ορίσουμε τα παρακάτω:

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

Η συνάρτηση κατακερματισμού πρέπει να εκτελείται γρήγορα και να είναι κατά το δυνατό ομοιόμορφη. Οι παρακάτω είναι μερικές ενδεικτικές μέθοδοι υλοποίησης: Οι παραπάνω μέθοδοι μπορούν να χρησιμοποιηθούν και σε συνδυασμό.

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

Σε περίπτωση που σημειωθεί μια σύγκρουση υπάρχουν οι παρακάτω επιλογές:

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

Ο ορισμός της γλώσσας προγραμματισμού C εγγυάται ότι οι αριθμητικές και λογικές πράξεις μη προσημασμένων ακεραίων (π.χ. unsigned int) γίνονται πάντα με υπερχείλιση modulo ν όπου ν ο αριθμός των bits που χρησιμοποιείται για τη φύλλαξη των αριθμών.

Ο παρακάτω πίκανας απεικονίζει τους αντίστοιχους αριθμούς ν στην αρχιτεκτονική Intel Pentium:
Τύποςν (bits)
unsigned char8
unsigned short16
unsigned int32
unsigned long32

Έτσι για παράδειγμα σε πρόσθεση δύο τιμών τύπου unsigned char 250 + 10 το αποτέλεσμα θα είναι 4 μια και 260 mod 2 8 = 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);
}

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

Ασκήσεις

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

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

    Παράδειγμα:

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