Hash Table Search
Hash Table Search
- location of each item is determined by a hash function of the item itself.
Collision Strategies
Linear Probing:
Adding:
- Calculate index
Insert item at that index- If it is occupied, check subsequent slots sequentially
- If the end of the table is reached, wrap back to the first index (similar to circular array)
- Continue until empty slot is found
Searching:
- Similar to adding
- Continue search until empty slot or when it reaches the start location again, indicating item is not in the table
Chaining:
Adding:
- Calculate Index
- Add the data at the index using linked list
Searching:
- Apply hash function
- Use search algorithm for linked list