Home

Awesome

<img src="/.translations/flags/gb.png"> <img src="/.translations/flags/fr.png">

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:

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

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.