Πρόσφατα σαν side project ενός προγράμματος που γράφω μου προέκυψε μια βιβλιοθήκη για hash tables0. Για την ακρίβεια ξεκίνησε σαν αντίγραφο αυτής που συνοδεύει το dnstop, αλλά κατέλληξε να είναι ένα reimplementation μια και διαβάζοντας τον κώδικα υπήρχαν ένα δύο σημεία που “εγώ θα τα έγραφα διαφορετικά” – και το έκανα. Μόλις βελτιώσω και το error handling θα την κάνω και διαθέσιμη1.
Έτσι κι αλλιώς αυτό που έχει σημασία δεν είναι τόσο η βιβλιοθήκη χειρισμού των hash tables, όσο η hash function2 που χρησιμοποιεί κάποιος. Και μετά από αρκετό ψάξιμο και διάβασμα πείστηκα κι εγώ3 πως η SuperFastHash4 είναι η καλύτερη από αυτές που είναι ελεύθερα διαθέσιμες.
| Dictionary of Algorithms and Data Structures: |
Hash function |
|---|---|
| Hash table | |
| Hash table delete5 |
Update: Ένα ενδιαφέρον thread από το comp.compilers archive.
[0] – Τι τραβάει κανείς επειδή η C δεν έχει associative arrays.
[1] – Όχι πως έχει ιδιαίτερη σημασία, οποιοσδήποτε δευτεροετής πρέπει να μπορεί να γράψει τη δικιά του (βιβλιοθήκη χειρισμού hash tables, όχι hash function).
[2] – Δεν μιλάμε για κρυπτογραφικό hash function.
[3] – Όπως και αυτοί που γράφουν το dnstop.
[4] – SuperFastHash implementation.
[5] – Ναι κάνω chaining.
Managing organized complexity 
Βασικά έχω την αίσθηση ότι δεν είναι και ΤΟΣΟ κακό που η C δεν έχει associative arrays. Αν σκεφτεί κανείς τον στόχο της C, ίσως είναι καλύτερο που βασίζεται σε εξωτερικές βιβλιοθήκες για να το πετύχει αυτό. (Τα associative arrays είναι λιγάκι πιο high level data structures από τα απλά και λιγάκι “native” που υποστηρίζει η C).
τον κώδικα υπήρχαν ένα δύο σημεία που “εγώ θα τα έγραφα διαφορετικά” – και το έκανα
Ποια σημεία; Πες το ζουμί ;)
Προσοχή με το chaining. Αν είσαι σίγουρος ότι δεν θα έχεις πολλά collisions τότε καλώς. Αλλιώς θα έχεις απόδοση σειριακού ψαξίματος – κάπου O(n/2) αν θυμάμαι καλά.
@Aristotelis:
Δεν είναι καθόλου κακό που δεν έχει associative arrays. Είναι απλά μη βολικό.
@UniqueFish:
Αρχικά η βιβλιοθήκη τους είναι φτιαγμένη έτσι ώστε να επιλέγεις από πολλά hash functions. Αν και η επιλογή τους είναι καλύτερη, εγώ διάλεξα μόνο ένα.
Έπειτα άλλαξα τον τρόπο με τον οποίο δηλώνεται ο hash table (και τα data του). Δες το σαν επιρροή από το style του ndbm και του BerkeleyDB. Ε, μετά από αυτό συνεχίζεις αλλαγές …θα δεις όταν μπορέσω να το κάνω release.
Το chaining δεν είναι πρόβλημα, αρκεί να είσαι προετοιμασμένος να κάνεις reorganize τον hash table όταν έχεις πολλά (για κάποιο ορισμό του πολλά) collisions.
Όπως κατάλαβες, δεν είναι array, του malloc(3) γίνεται.
Το O(n/2) μου φαίνεται πως ειναι για πολύ χάλια καταστάσεις. Το worst case scenario για n στοιχεία είναι να έχουνε όλα το ίδιο hash value άρα να αρχίσει chaining στο ίδιο σημείο επομένως στο hash table σου και να πρέπει να ψάξεις σειριακά μια linked list. (άρα κατά μέσο όρο , πάει για n/2 αν δεν κάνω λάθος). Αλλά πάλι αυτό είναι αρκετά χάλια από μόνο του! :)
@adamo: Το κάνεις για λόγους coding style δηλαδή και για να ελαχιστοποιήσεις τις παραμέτρους; Διαφορά στην ταχύτητα δεν θα έχεις αλλά στο μέγεθος τους κώδικα.
@aristotelis: Ναι, O(n/2) είναι η χειρότερη περίπτωση – να σου κάτσουν όλα σε ένα chain. Συνήθως αυτό που συμβαίνει είναι η επιλογή λάθος load factor και αν γίνει ομοιόμορφη κατανομή έχεις O(l/2) – όπου l ο μέσος όρος μεγέθους των αλυσίδων.
@UF:
Στην αρχή το έκανα γιατί δεν ήθελα ένα generic API που να δέχεται και το hash function σαν παράμετρο. Αφότου άρχισα να αλλάζω και τα stucts, απλά έμεινε.
Με τον τρόπο που το έχουν οι τύποι του Measurement Factory, μπορείς σε ένα πρόγραμμα να έχεις πολλά hash tables και με διαφορετικά hash functions το καθένα. Εμένα αυτό δε με ενδιέφερε. Με ενδιαφέρει όλα τα hash tables να έχουν το ίδιο hash function.
(Μετά από τόση συζήτηση υπολογίζω να το κάνω release μέχρι τη Δευτέρα.)