Προς το περιεχόμενο
  • 0

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


realez

Ερώτηση

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

Είχα φτιάξει ένα struct της μορφής:

 

struct data

{

   int key;

   char c[20];

};

Τα βήματα που ακολουθούσα μετά ήταν

-Hashing στο κλειδί που έδινε της μορφής hash(key, m) = key mod m. Όπου key=κλειδί, m=μέγεθος πίνακα

-Πήγαινα στη διεύθυνση (ας πουμε ότι ο πίνακας μου λεγόταν array) array[hash(key,m)]

-Εκεί άμα ήταν άδεια έβαζα το κλειδί και τη λέξη

-Αμα δεν ήταν το έβαζα στην επόμενη κενή θέση που θα έβρισκα

-Αμα ξαναέφτανε στην αρχική θέση ο πίνακας ήταν γεμάτος.

 

Τώρα προσπαθώ να φτιάξω έναν πίνακα κατακερματισού αλλά αυτή τη φορά το Input το παίρνω από txts (γύρω στα 30 και το καθένα περιέχει μυθιστορήματα) και τα κλειδιά αυτή τη φορά είναι strings.

Οι απορίες μου είναι οι εξείς:

-Ποιό πρέπει να είναι το μέγεθος του πίνακα (σταθερό η να το αλλάζω);

-Πως μπορώ να κάνω σωστό hasing στις λέξεις;

-Τι είναι πιο σωστό να χρησιμοποιήσω hashing με ανοιχτή διεύθυνση η με αλυσίδες;

ps: Οί γνώσεις μου στη C++ είναι αρκετά περιορισμένες.

Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Προτεινόμενες αναρτήσεις

  • 0

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

Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

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

 

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

Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

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

 

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

 

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

 

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

Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε έναν λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι εύκολο!

Εγγραφείτε για έναν νέο λογαριασμό

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
  • Δημιουργία νέου...

Με την περιήγησή σας στο insomnia.gr, αποδέχεστε τη χρήση cookies που ενισχύουν σημαντικά την εμπειρία χρήσης.