Hash Crash: The Basics of Hash Tables

“If I were stranded on a desert island and could only take one data structure with me, it would be a hash table.”

- Peter Van Der Linden, Author of Deep C Secrets

If you have programming experience but don’t know what a hash table is, chances are you use them regularly and don’t even know it. They are so useful and so practical that many programming languages have a hash table construct built directly in to the syntax.

They are sometimes referred to as associative arrays (PHP), or dictionaries (Python), or hashes (PERL).

If you are using a language that does not have built-in hash tables, then you must create one. The good news is, by creating your own hash table, you can tailor it to meet your specific needs with optimal efficiency.

In this article I try to provide a basic understanding of hash tables. At the end I provide a full implementation of a hash table in it’s simplest form, in plain C.

What is a Hash Table?

A hash table is a data structure that allows you to keep a list of key-value pairs (i.e. records), and it provides quick and efficient access to them.