Hash Tables
Computer Science: OCR A Level, topic 4.2.5
Hash Tables
A hash table is a data structure used for very large collections of data or where quick access to the data is required, such as customer records or password verification.
Hashing algorithm
- Hashing algorithms allows for the efficient location and retrieval of data.
- The hashing algorithm generates indexes based on the key fields of sets of data.
- A common example of a hashing algorithm is one which takes the key and divides it by the number of storage spaces available.
- The remainder is then used as the address at which to store the key.
Example
- If the keys 738, 271 and 560 need storing in a hash table with 6 storage spaces, the process would be as follows:
- Calculate the remainder when 738 is divided by 6.
- 738 MOD 6 = 0
- That means first key should be stored in location 0.
Example cont.
- For the second key, 271 MOD 6 = 1.
- We store this in location 1.
- For the third key, 560 MOD 6 = 2.
- We store this in location 2.
Collisions
- A perfect hashing algorithm will always generate a unique index.
- Should this not be the case, a ‘collision’ is said to occur .
- When a collision occurs, a rehashing algorithm is used to determine the next available slot in which to store the data.
- Alternatively, we can create a separate data structure such as a linked list from each storage location and store the collisions there.
Example
- Key 362 would need adding to the hash table above in location 2 as:
- 362 MOD 6 = 2
- However, it’s already filled by 560.
- In this case, the next available slot is location 3, so key 362 is stored there.