Hash table

A hash table is a data structure that map keys to a position in a array. It does that in by using a hash function. It is possible that two or more keys map to the same index of the array and then there is a collision the the hash table need to handle.

Hash Function

The hash function first compute a hash value from the key and then module this hash value with the size of the array. The keys can be for example integers, characters, pointers or strings. An ideal hash function maps the keys to the integers in a random-like manner, so that array positions are used evenly even if there are regularities in the input data.

hash = hash_function(key)

index = hash % array_size

Murmur

Collisions

If two or more keys map to the same slot in the array there is a collision.

Open addressing
Chaining
Bucket addressing

Using the hash table

Insert(key, value)

Find(key)

Delete(key)

Reference

Robin Hood Hashing should be your default Hash Table implementation - 2013

Hash tables introduction - 2012

Hashing Strings and Pointers – Avoiding Common Pitfalls - 2011