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.
- Introduction
- Hash table structure
- Hash functions
- Handling collisions
- Hash table methods
- Resizing tables
- Appendix: alternative collision handling
This tutorial was written by James Routley, who blogs at routley.io.