The first data structure I learned and really internalized was the hash table. I\u2019ve been using them my entire career and, given when I started, that meant implementing them myself. This was before I learned C and even C doesn\u2019t have a built-in hash table so it\u2019s always been a matter of build it or do without.<\/p>\n
These days, it\u2019s hard to find a (newer) language that doesn\u2019t have a built-in hash table or dictionary data type. There\u2019s a downside to that, however. For many younger engineers, hash tables are mysterious entities that seem like magic. There are, in fact, many strategies for implementing a hash table each with their own tradeoff and which is best depends on the particular application. The problem with a built-in type is that it\u2019s one size fits all.<\/p>\n
Chris Wellons writes mostly in C so he has implemented scores of hash tables. He\u2019s settled on his own implementation method<\/a> which is basically open addressing with double hashing. You can check his post for what exactly that means but it\u2019s one of the main implementation methods. I\u2019ve always preferred the chaining method, which is usually faster but takes more storage. Like Wellons, I\u2019ve done scores of implementations.<\/p>\n Why do that? After all, most languages have a built-in type and even C probably has a library that implements hash tables. Lots of people think there IS no point<\/a> but I disagree: if you know how things work, you know how to pick the best implementation strategy for your particular application.<\/p>\n Take a look at Wellons\u2019 post for some of those details. Section 6.4 of Volume 3 of Knuth\u2019s AOCP<\/a> has all the details on the various methods and their tradeoffs. If you\u2019re serious about software engineering, it will repay your attention.<\/p>\n","protected":false},"excerpt":{"rendered":" The first data structure I learned and really internalized was the hash table. I\u2019ve been using them my entire career and, given when I started, that meant implementing them myself. This was before I learned C and even C doesn\u2019t … Continue reading