Hash Table

From Algorithmist

This is a stub or unfinished. Contribute by editing me.

A hash table is a dictionary-like data structure that provides O(1) lookup time. You associate keys with values (e.g. a dictionary associates words with definitions). Often a hash table is implemented using a hash function and an ordinary array. Collisions (when multiple keys map to the same array index) must be dealt with somehow or the hash table is severely crippled.

Contents 1 Hash Functions 1.1 Key Length 1.2 Key Value 2 Collision Resolution 2.1 Separate Chaining 2.2 Linear Probing 2.3 Quadratic Probing 3 Common Operations 3.1 Insertion 3.2 Lookup 3.3 Deletion

[edit] Hash Functions

[edit] Key Length

An incredibly simple hash function could be the length of the key. This is a terrible hash function for (hopefully) obvious reasons.

[edit] Key Value

If the key is given as a C-like string of length L, we can define the key value as such:

key[0]   key[1]   ...   key[L-2]   key[L-1]

This is a common but poor hash function. For example, "foo", "oof", and "fnp" all hash to the same index.

[edit] Collision Resolution

[edit] Separate Chaining

[edit] Linear Probing

[edit] Quadratic Probing

[edit] Common Operations

[edit] Insertion

[edit] Lookup

[edit] Deletion