Hash Table
- Used for fast reading
- Also known as associative arrays
- Use a deterministic hash function
- Under the good a hash stores data in a bunch of cells in a row, similar to an array.
- When a key is provided, this key is hashed, this hash will return a memory location within the row of cells.
- Collisions can happen with the hash function, a classic solutions is “separate chainging”. What we do is instead of placing a value in the cell, we puts a reference to an array in it. That array will hold a subarray for each element. So once it founds a hash location with an array, it will do a sequential lookup within that array. e.g.
[[key1, value1],[key2, value2]]
- Efficiency if a hash table is based on
- How much data we’re storing in the hash table
- How man cells are available in the hash table
- Which hash function we’re using
- Result is that Search/Insert/Delete is O(1) average and worst 0(N) in case everything ends up in one array referenced in one cell.
