User Tools

Site Tools


Hash table

A hash table is a data structure that maps keys to values. The keys are distributed across a number of buckets by hashing the key to produce a bucket index.

A good hash function produces an even distribution across all the buckets so that no bucket is overloaded.

Even with a good hash function collisions happen, where two keys are hashed to the same slot. Therefore most hash tables have some collision resolution strategy to handle this case.

Separate chaining

In separate chaining (also called open hashing or closed addressing) each bucket has its own list of entries. A good hash table only has very few items in each bucket, and so data structures like a linked list are popular.

This example is hash set, as it only stores a key. However all the main logic is the same, a hash table stores a (key, value) pair instead of just a key, but all the hashing and equality checks are still performed on the key.

This example uses the Fowler Noll Vo hash function for hashing strings, and the raw data for numbers.

λ hash_set-open_hashing

hash_table.txt · Last modified: 2015/02/02 08:28 (external edit)