The location of a record in a random file is determined using a hashing algorithm. A collision may occur during the process of adding a record.

Mark scheme

Marking points from the official mark scheme (Oct/Nov 2023). The mark or mark type is shown in brackets.

1. [1] A collision is when the two values / data items in the key field for two records (pass through a hashing algorithm and) result in the same hash value
2. [1] ...so the location identified (by the hashing algorithm) may already be in use // two records cannot occupy the same address.
3. [1] A process of collision resolution is used
4. [1] Start at the original hashed storage space
5. [1] ...go through the following spaces in a linear fashion
6. [1] ...and store the data item in the first available slot.
7. [1] Search the overflow area
8. [1] ...go through the following spaces in a linear fashion
9. [1] ...and store the data item in the first available slot.
10. [1] Each storage space holds a reference to a collection / chain of items
11. [1] ...which can be searched individually.
12. [1] The data item is stored in the first available space in this chain.