Advanced Data Representation and File Organisation: Question 3

Worked solution

Part (a): Calculating hash values with MOD 7

MOD gives the remainder left over after dividing by 7, i.e. after subtracting the largest multiple of 7 that does not exceed the MemberID.

• 2041 MOD 7: the largest multiple of 7 not exceeding 2041 is 7 × 291 = 2037. 2041 − 2037 = 4. Hash value = 4.
• 2045 MOD 7: the largest multiple of 7 not exceeding 2045 is 7 × 292 = 2044. 2045 − 2044 = 1. Hash value = 1.
• 2049 MOD 7: the largest multiple of 7 not exceeding 2049 is 7 × 292 = 2044. 2049 − 2044 = 5. Hash value = 5.
• 2056 MOD 7: the largest multiple of 7 not exceeding 2056 is 7 × 293 = 2051. 2056 − 2051 = 5. Hash value = 5.

Completed table:

[4 marks]: [1] for each correct hash value (2041→4, 2045→1, 2049→5, 2056→5), with working shown for at least one row.

Part (b): Identifying the collision

A collision occurs when the hashing algorithm calculates the same hash value, and therefore the same intended storage location, for two different record keys. This is a normal risk of hashing, since many possible keys are mapped down onto a much smaller set of possible hash values (here, only 0 to 6).

Looking at the completed table, MemberID 2049 and MemberID 2056 both produce a hash value of 5, so these are the two MemberIDs that collide.

[2 marks]: [1] for correctly defining a collision (same hash value/location from two different keys), [1] for correctly identifying 2049 and 2056 as the colliding pair.

Part (c): Resolving the collision

MemberID 2049 is added first and is stored at location 5, its calculated hash value. When MemberID 2056 is added afterwards, its hash value is also 5, but that location is now occupied.

One standard way to resolve this is for the file-handling routine to search onward from location 5 for the next empty location (for example location 6, then 7, and so on, wrapping back around to location 0 if the end of the file is reached), and store 2056’s record there instead.

This matters for retrieval too: because 2056’s record is not stored at its own hashed location, any later routine that searches for MemberID 2056 must repeat exactly the same onward search. Starting again at location 5 and moving through the following locations in the same order, until it finds the record (or reaches an empty location, which would mean the record does not exist).

Location  ← Hash(MemberID)      // Location ← MemberID MOD 7
WHILE MemberFile[Location] is occupied by a different MemberID
    Location ← (Location + 1) MOD NumberOfLocations
ENDWHILE
Store the record for MemberID at MemberFile[Location]

[3 marks]: [1] for identifying that the record is stored in the next available (empty) location, [1] for describing the onward/wraparound search process, [1] for noting that a later search for the record must follow the same sequence.

Final answers

• (a) 2041 → 4, 2045 → 1, 2049 → 5, 2056 → 5
• (b) A collision is two different keys producing the same hash value; 2049 and 2056 collide (both hash to 5).
• (c) The second colliding record (2056) is stored at the next available empty location found by searching onward from location 5; the same search must be repeated to find it again later.