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.
- 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.
- Hash table structure
- Hash functions
- Handling collisions
- Hash table methods
- Resizing tables
- Appendix: alternative collision handling