Benchmarking hash table implementations

lonewolfer

A post after a very long pause, about something completely different.

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 post 498 more words

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s