Awesome Open Source
Awesome Open Source

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 James Routley, who blogs at routley.io.



Alternative Project Comparisons
Related Awesome Lists
Top Programming Languages
Top Projects

Get A Weekly Email With Trending Projects For These Topics
No Spam. Unsubscribe easily at any time.
C (183,789
Tutorial (23,597
Table (23,072
Hash (11,335
Data Structures (9,700
Write (7,709
Collision (2,701
Hashtable (1,198