Originally posted on lonewolfer:
I will do a fairly brief and naïve benchmark of different hash table implementations. Doing a complete in depth benchmark on this topic is difficult since the behaviour and target use cases can vary greatly and different implementations do different trade-offs.
Hopefully the results will still be of some interest and significance. The reason for doing this will hopefully be more clear later on.
Associative arrays/dictionaries/maps/tables, whatever you wish to call them, are one of the most common and important container types. Most often they are implemented using hash tables for the obvious practical reason that the cost of operations like insert/lookup/delete are amortized constant, or on average O(1).
Most languages typically have built-in or standardized ways to support this. Surprisingly, perhaps, this is not the case with the “#1″ programming language, C. One of the reasons being that most…
View original 582 more words