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