Hashing

Hashing removes the searching almost completely. Instead of looking for where a record is, you calculate where it must be. You feed the record's key (a unique number, like a student ID) into a small formula called a hash function. The formula gives you an address — the exact index in the array where the record lives.

# Think of n lockers numbered 0 to n-1.
# A book with code 3547 in 2000 lockers goes to:
#   3547 MOD 2000 = 1547  (because 3547 - 2000 = 1547)

# Another book with code 5547:
#   5547 MOD 2000 = 1547  (because 5547 - 4000 = 1547)
#   Same address! -> collision!

The hash function is fast, but it is not perfect. Different keys can produce the same address. For example, with MOD 2000:

3547 MOD 2000 = 1547
5547 MOD 2000 = 1547   # same address — collision!

There are three standard ways to handle a collision. Cambridge accepts any of them on the theory paper:

Try the hashing algorithm yourself. Enter keys (comma-separated), set the table and spare sizes, then click Start. Watch each key being hashed (Key MOD n), stored directly in the HashTable (green), or sent to the Spare overflow array (amber) on collision (red).

1HashValue = CalculateHash(TheRecord.Key)
2if HashTable[HashValue].Key == -1:
3    HashTable[HashValue] = TheRecord
4else:  # collision!
5    for i in range(100):
6        if Spare[i].Key == -1:
7            Spare[i] = TheRecord
8            break

This is the complete routine asked in 9618/42 May/June 2025. We build it piece by piece: the record class, two arrays, Initialise, CalculateHash, InsertIntoHash, CreateHashTable, and PrintSpare.

20.1.4a The record class

class NewRecord:
    def __init__(self, key, item1, item2):
        self.Key   = key
        self.Item1 = item1
        self.Item2 = item2

20.1.4b The two arrays

HashTable = []   # main table, 200 slots
Spare     = []   # overflow, 100 slots

20.1.4c Initialise()

def Initialise():
    global HashTable, Spare
    HashTable = [NewRecord(-1, -1, -1) for i in range(200)]
    Spare     = [NewRecord(-1, -1, -1) for i in range(100)]

20.1.4d CalculateHash()

def CalculateHash(Key):
    return Key % 200

20.1.4e InsertIntoHash()

def InsertIntoHash(TheRecord):
    global HashTable, Spare
    HashValue = CalculateHash(TheRecord.Key)

    if HashTable[HashValue].Key == -1:        # slot is free
        HashTable[HashValue] = TheRecord
    else:                                       # collision
        for i in range(100):
            if Spare[i].Key == -1:
                Spare[i] = TheRecord
                break                          # first free slot only

20.1.4f CreateHashTable() — load from file

def CreateHashTable():
    try:
        File = open("HashData.txt")
        for Line in File:
            Data = Line.strip().split(",")
            R = NewRecord(int(Data[0]), int(Data[1]), int(Data[2]))
            InsertIntoHash(R)
        File.close()
    except:
        print("Cannot open file")

20.1.4g PrintSpare() and the main program

def PrintSpare():
    for i in range(100):
        if Spare[i].Key != -1:
            print(Spare[i].Key)

# main program
Initialise()
CreateHashTable()
PrintSpare()

The Aymaan Health clinic stores patient data in a 1D array of records, Clinic, with space for 150 records. The index for each record is calculated from the key field using Key MOD 150. If two keys give the same index there is a collision; the colliding record is stored in the next free space in a second array, Reserve, which has space for 75 records.

Fifteen exam-style hashing tasks. Each shows only the question — click Hint for the thought process, or Help for the worked solution.