Hash tables are a data structure, typically an array, which contains a set of unique indices, and values associated with these.

Given a piece of data, we can apply an algorithm which will uniquely determine where to store this data.

Searching in a hash table for data is a near instantaneous process, O (1).

Example algorithm

A hash table is set up to store just seven records, numbered 0, 1, 2, 3, 4, 5, 6

In a given database, records are stored using the hash key which is calculated as follows:

H(K) = K MOD 7

This will return a number between 0 and 6 so whatever ID number we have; we can find a place in the table to put it.

Given ID number 64156921, we store it in 64156921 MOD 7 = 3

Therefore, the ID will be stored at index 3 in the table.

Collisions happen when the hashing algorithm produces the same index for two or more keys.

What problems does this cause?

The records for both items map to the same location.

The information for the second item will overwrite the first.

Dealing with Collisions

• Store values in same location using a linked list

• Use the next available memory location

• Rehashing (same algorithm again or different algorithm entirely)