hash table για string στη C++

[migf1]

...

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

 

Το νήμα που σου έδωσα στο προηγούμενο ποστ, καθώς και τα links που περιέχει τα διάβασες; Σου δίνει όλες τις απαραίτητες πληροφορίες αλλά και έτοιμους κώδικες για να φτιάξεις hashing. Το μέγεθος του map σαφώς και έχει τεράστια σημασία κι επηρεάζει άμεσα το efficiency του hashing σου. Οπότε πολύ σωστά το κατάλαβες, σου δίνω και συγκεκριμένη σελίδα από το προαναφερθέν link: http://www.fearme.com/misc/alg/node29.html

 

Ο defacer μπερδεύει την γενική έννοια του hashing με την ειδική έννοια one-way hashing ή/και με την ειδική έννοια uniform hashing (και κάπου στο ενδιάμεσο μπερδεύει και το perfect hashing, και όλα μαζί τα μπερδεύει με cryptographic hashing).

 

Εν πάσει περιπτώσει, η δική μου πρόταση είναι εφόσον θέλεις να φτιάξεις δικό σου να διαβάσεις το παραπάνω link και να χρησιμοποιήσεις μια από τις απλές hash functions που παραθέτει, π.χ. την variable string addition, με μέγεθος πίνακα 256. Αν δεις ότι στην πράξη σε καθυστερεί (που είναι και το πιο πιθανό), μπορείς να δοκιμάσεις την division method (αυτό που έχεις ήδη κάνει) αλλά ακολουθώντας τις συμβουλές του link για το μέγεθος του map (για τον υπολογισμό του ). Αν παίρνεις και πάλι πολλά collisions, πειραματίσου πρώτα με το μέγεθος του map κι αν δεν μείνεις ούτε τότε ικανοποιημένος, δοκίμασε και την multiplication method (σου δίνει και για αυτή κώδικα το link).

 

Ως data-key που θα περνάς ως όρισμα στην hash function σου (ή θα υπολογίζεις μέσα της) μπορείς αρχικά να χρησιμοποιήσεις το άθροισμα των ASCII codes των χαρακτήρων του κάθε string. Θα μπορούσες επίσης στην τελική σούμα να προσθέτεις και το πλήθος των χαρακτήρων του. Ή θα μπορούσες να χρησιμοποιήσεις κάποια από τις έτοιμες hash functions για strings, όπως για παράδειγμα κάποια από αυτές που πιθανότατα θα σου δώσουν καλύτερα αποτελέσματα (τουλάχιστον κατά μέσο όρο).

 

Η άσκηση από μια γρήγορη ματιά που της έριξα δεν στοχεύει στο να σας εξοικειώσει με τα hashing internals, μιας και σας επιτρέπει να χρησιμοποιήσετε έτοιμες υλοποιήσεις. Οπότε η χρήση της standard library ή έστω της Boost που σου πρότεινε ο defacer δεν είναι κακή ιδέα.

 

ΥΓ. Το MD5 δεν έχει καμία σχέση με αυτό που σου ζητάει η άσκηση. Το MD5 είναι cryptographic hashing (π.χ. για signatures).

[realez]

Πολύ κατατοπιστική η απάντιση σου    Θα ολοκληρώσω την άσκηση με αυτό που είχα κάνει post πριν και μετά θα πειραματιστώ με αυτά που μου έστειλες για να βρω το πιο σωστό.

[defacer]

 defacer μπερδεύει την γενική έννοια του hashing με την ειδική έννοια one-way hashing ή/και με την ειδική έννοια uniform hashing (και κάπου στο ενδιάμεσο μπερδεύει και το perfect hashing, και όλα μαζί τα μπερδεύει με cryptographic hashing).

 

Απλά ξερνάω. Τόσο παιδάκι πια;

[migf1]

Πολύ κατατοπιστική η απάντιση σου    Θα ολοκληρώσω την άσκηση με αυτό που είχα κάνει post πριν και μετά θα πειραματιστώ με αυτά που μου έστειλες για να βρω το πιο σωστό.

 

Χαίρομαι που σε βοήθησε το μήνυμά μου!

 

Νομίζω είναι καλή ιδέα να χρησιμοποιήσεις απευθείας μια από τις έτοιμες hash functions για strings, που περιέχει το 2ο από τα λινκς του προηγούμενου ποστ, αλλά και η division method πιστεύω πως αρκεί αν χρησιμοποιήσεις κατάλληλο μέγεθος του map .

 

Καλή συνέχεια και καλή επιτυχία εύχομαι.