Programming‎ > ‎Data‎ > ‎ADT‎ > ‎

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)

http://www.randygaul.net/2012/07/01/hash-tables-introduction/
Comments