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

[Sakel27]

Γεια σας... Είμαι φοιτητής πληροφορικής και έχω μια απορία για τον κατακερματισμό. Στο βιβλίο αναφέρεται πως για να βρούμε τον κάδο που θα αποθηκευτεί μια εγγραφή διαιρούμε με το 41. Και έχει ένα παραδειγμα αλλα δεν εξηγεί ποιους αριθμούς διαιρούμε με το 41... Όποια βοήθεια ευπρόσδεκτη...Ευχαριστώ

 

Site: Σελ38,39 υπάρχει το παράδειγμα του βιβλίου

[AllCowsEatGrass]

Σου λέει στη σελίδα 38 τα βήματα ένα - ένα.

-> Αναπαριστά το "κλειδί", αυτό που θέλεις δηλαδή να hashareis (κατακερματίσεις) σε ASCII. 
-> Παίρνει τα bits των χαρακτήρων από την μετατροπή σε ASCII, τα βάζει στη σειρά, τα ερμηνεύει σαν να ήταν ένας αριθμός στο δυαδικό σύστημα και μετατρέπει αυτόν στο δεκαδικό σύστημα.

-> Διαιρεί τον αριθμό με το 41.

Αυτό που σου περιγράφει δεν είναι γενικά το hashing, είναι ένα συγκεκριμένο παράδειγμα αρκετά απλουστευμένο. Το 41 δεν είναι κάποιος μαγικός αριθμός, είναι επιλεγμένος.

[imitheos]

Γεια σας... Είμαι φοιτητής πληροφορικής και έχω μια απορία για τον κατακερματισμό. Στο βιβλίο αναφέρεται πως για να βρούμε τον κάδο που θα αποθηκευτεί μια εγγραφή διαιρούμε με το 41. Και έχει ένα παραδειγμα αλλα δεν εξηγεί ποιους αριθμούς διαιρούμε με το 41... Όποια βοήθεια ευπρόσδεκτη...Ευχαριστώ

 

Όταν πας να αποθηκεύσεις τα δεδομένα σου σε κάποιο πίνακα, δεν τα αποθηκεύεις σε όποια θέση να είναι αλλά χρησιμοποιείς την συνάρτηση κερματισμού (ώστε μετά που θα χρειαστεί να ψάξεις κάτι, να τρέξεις πάλι την hash function και να πας κατευθείαν στην τάδε θέση χωρίς να ψάχνεις).

 

Μια hash function λοιπόν παίρνει δεδομένα μεταβλητού μεγέθους και παράγει πάντα ένα "αριθμό" σταθερού μεγέθους ανάλογα με τι hash function είναι. Μπορεί πχ να έχεις μια 256bit hash function.

 

Αυτός ο αριθμός που θα σου δώσει, είναι η θέση του πίνακα που υπό κανονικές συνθήκες θα πήγαινες να αποθηκεύσεις τα δεδομένα σου. Υπάρχει όμως ένα πρόβλημα. Οι αριθμοί είναι συνήθως πολύ μεγάλοι οπότε θα πρέπει να δεσμεύσεις πολύ μνήμη και να ορίσεις ένα τεράστιο πίνακα. Μπορεί πχ να έχεις 3 εγγραφές και αυτές να πάρουν από την συνάρτηση αντίστοιχα αριθμούς 504785, 2757327573, 957375. Θα ορίσεις ένα πίνακα με 2757327573 στοιχεία για να αποθηκεύσεις μόλις 3 ?

 

Για αυτό το λόγο γίνεται αναγωγή (ειδικά σε ασκήσεις που δεν σε νοιάζει και τόσο αν θα έχεις συγκρούσεις λόγω της αναγωγής). Επιλέγεις ένα μέγεθος που σου φαίνεται δόκιμο και έπειτα παίρνεις την έξοδο της hash function και την ανάγεις στο μέγεθος που επέλεξες. Ο τρόπος για να το κάνεις αυτό είναι να βρεις το υπόλοιπο του αριθμού που έδωσε η hash function με το μέγεθος που όρισες.

 

Στο συγκεκριμένο παράδειγμα, έχεις χωρητικότητα 41 κάδων οπότε αυτό είναι το μέγεθος στο οποίο θα κάνεις αναγωγή. Ο αριθμός του οποίου θα βρεις το υπόλοιπο είναι αυτός που σου επέστρεψε η hash function. Από ό,τι καταλαβαίνω, η συγκεκριμένη συνάρτηση της άσκησης παίρνει για κάθε χαρακτήρα την ASCII τιμή του, κολλάει το bit pattern όλων των χαρακτήρων και μετά το ερμηνεύει ως αριθμό οπότε για το string 25X3Z προκύπτει ο αριθμός 215....562.