Be familiar with the concept of a hash table and its uses.
A hash table is a data structure that creates a mapping between keys and values.
A hash function takes a key and performs a series of operations on it to produce a hash. The value is then stored against this hash in the table.
Hash tables are often used to implement other in memory data structures such as associative arrays. Additionally they are used a lot in database indexing and caching.
Be able to apply simple hashing algorithms.
Know what is meant by a collision and how collisions are handled using rehashing.
A collision occurs when two key values compute the same hash.
Rehashing is when a new, larger, table is created and the values are hashed into that table. The new table must use a new hash function.
- Make larger table
- Go through old hash table ignoring empty slots
- Recompute the hash value and put in new position in new table
In linear probing, after a collision has occurred, the table is scanned until the next available slot is found. Then the value is stored against that key.