allensmile / write-a-hash-table

Write a hash table in C

Hash tables are one of the most useful data structures. Their quick and scalable insert, search and delete make them relevant to a large number of computer science problems.

In this tutorial, we implement an open-addressed, double-hashed hash table in C. By working through this tutorial, you will gain:

• Understanding of how a fundamental data structure works under the hood
• Deeper knowledge of when to use hash tables, when not to use them, and how they can fail
• Exposure to new C code

C is a great language to write a hash table in because:

• The language doesn't come with one included
• It is a low-level language, so you get deeper exposure to how things work at a machine level

This tutorial assumes some familiarity with programming and C syntax. The code itself is relatively straightforward, and most issues should be solvable with a web search. If you run into further problems, please open a GitHub Issue.

The full implementation is around 200 lines of code, and should take around an hour or two to work through.

Contents

1. Introduction
2. Hash table structure
3. Hash functions
4. Handling collisions
5. Hash table methods
6. Resizing tables
7. Appendix: alternative collision handling

Credits

This tutorial was written by @jamesroutley, who blogs at routley.io.