A hash table finds an item by calculating where it is, not by searching for it.
Definition
A hash table is a data structure in which a hashing function is applied to an item's key to calculate the position (index) where the item is stored. The same calculation finds the item again, so it can be accessed directly.
Key Point
A good hashing function:
• Always gives the same position for the same key
• Is quick to calculate
• Spreads the keys evenly over the whole table, so that few keys share a position
• Always gives the same position for the same key
• Is quick to calculate
• Spreads the keys evenly over the whole table, so that few keys share a position
Collisions
Definition
A collision happens when the hashing function gives two different keys the same position. Only one item can be stored there, so the second needs another place.
Key Point
| Method | How the collision is dealt with |
|---|---|
| Linear probing | Move through the table one space at a time from the calculated position until a free space is found, and store the item there |
| Chaining | Each position holds a pointer to the start of a linked list. Every item that hashes to that position is added to the end of its list |
| Overflow area | The item is stored in a separate overflow area that the table points to, along with any other items that collided |
Worked Example
Worked Example: Adding Items with Linear Probing
The table has 10 positions, indexed 0 to 9. The hashing function is: position = key MOD 10.
With chaining, 33 would be added to the linked list at position 3, after 23, and 54 would be stored at position 4.
The table has 10 positions, indexed 0 to 9. The hashing function is: position = key MOD 10.
| Key | key MOD 10 | Stored at | Reason |
|---|---|---|---|
| 23 | 3 | 3 | Position 3 is free |
| 47 | 7 | 7 | Position 7 is free |
| 80 | 0 | 0 | Position 0 is free |
| 33 | 3 | 4 | Collision with 23, so the next free space is used |
| 54 | 4 | 5 | Position 4 is now taken by 33, so the next free space is used |
Searching, Adding and Removing
Key Point
Search:
• Apply the hashing function to the key and go to that position
• If the item there is not the one wanted, follow the same collision method that was used to store it: check the next spaces in turn, or search the linked list
• The search fails when an empty space, or the end of the list, is reached
Add:
• Apply the hashing function to the key
• If the position is free, store the item. If not, deal with the collision
Remove:
• Find the item as in a search, then remove it
• With linear probing the space is marked as deleted and not simply emptied. An empty space would make later searches stop before they reached items stored beyond it
• Apply the hashing function to the key and go to that position
• If the item there is not the one wanted, follow the same collision method that was used to store it: check the next spaces in turn, or search the linked list
• The search fails when an empty space, or the end of the list, is reached
Add:
• Apply the hashing function to the key
• If the position is free, store the item. If not, deal with the collision
Remove:
• Find the item as in a search, then remove it
• With linear probing the space is marked as deleted and not simply emptied. An empty space would make later searches stop before they reached items stored beyond it
Comparing Search Times
Key Point
| Structure | How an item is found | Search time |
|---|---|---|
| Hash table | The position is calculated from the key | O(1): constant, if there are no collisions |
| Binary search tree | One subtree is ignored at every node | O(log n) |
| Linked list | Pointers are followed from the first node until the item is found | O(n) |
Exam Tip
Hash table answers:
• Say that the key is hashed to calculate the position. The table is not searched
• Search time does not grow as more items are added, but only while collisions are rare. Many collisions slow it down
• A hash table needs more space than the data it holds and a well-chosen hashing function to keep collisions rare
• Say that the key is hashed to calculate the position. The table is not searched
• Search time does not grow as more items are added, but only while collisions are rare. Many collisions slow it down
• A hash table needs more space than the data it holds and a well-chosen hashing function to keep collisions rare