Hash Tables

Often you only need the "dictionary" functions:

Insert, Search, Delete

Example: symbol table in a compiler

Example: discrete logarithm (later)

Searching in a linked list can be as bad as O (n), a hash table makes the average case O (1). This compares favorable to direct addressing into an array. With an array usually the key is the array index. With hashing the array index is computed from the key via a hash function, h (k).