# Data Structures T5 Hash Tables

?

Searching algorithms

• If in random order
• Must use a sequential (linear) search
• If there are 10 million items, searching could take a long time
• Else
• Any other search algorithm, such as binary search.
• Hash Table
• Find any record in the dataset almost instantly
• Items to be deleted must be replaced with a dummy marker, e.g; "N/A"
• If a new item has to be added, and the address contains "N/A", it will replace the dummy item.
• Address of data is calculated using the data itself via hashing algorithm
• A simple hashing algorithm is to assign 1000 slots which have a 4 digit key
• Address = key mod (no# slots)
• This turns the following example data into the following addresses
• 0287 -> 287
• 0999 -> 999
• 1074 -> 074
• 9074 -> 074
• 3287 -> 287
• Address 074 has two pieces of data - this is known as a collison.
• Happens when an algorithm generates the same address for different primary keys.
• Also known as a "synonym"
• Collisions are unavoidable.

Dealing with collisions

• Simplest method is to put the item in the next free slot in the table.
• This can lead to clustering of items in the table.
• Another method…