A hash table is a form of key, value table with the goal to immediately find an item.
A hashing function is used to calculate the position of an item in a hash table.
Implementation
Hashing Function
One-way algorithm which produces a hashed result.
The hashing function is applied to an item to determine a hash value.
A good hashing function should:
- Be calculated quickly
- Result in minimal collisions
- Use minimal memory
Examples:
- MD5
- SHA512, SHA256, SHA128
Resolving Collisions
Linear Probing
Repeatedly checking the next space in a hash table until an empty position is found, iterating in a given interval.
Requires a linear search to be performed when inserting but also searching for the item.
Chaining
When it is possible for a multitude of items to be placed at the same position.
Examples:
- Overflow table
- Linked list
- Two-dimensional table
Usage
Applications
- File systems (file name → file path)
- Identifying keywords (token → token class, data type, etc.)
Operations
- Add
- Delete
- Retrieve