Hash Table

Hash Table

Implementation

use an array of linked list and a hash code function

To insert a key

1. Compute key's hash code(a integer)

2. Compute the index in the array with the hash code(could be done with has(key) % array_length)

3. Use the index, we can find our linked list(using linked list because there could have 2 different keys with the same hash code)

To retrieve the value through key, we search through the linked list on that index

If the number of collision is very high, then the worst case is O(n), n is the number of key

Generally look up time is O(1)

Hash Table