hashing

课 Progress

0% Complete

Hashing algorithms

A hashing algorithm is used to calculate the storage location (address) of a record in a random (direct access) file
It allows for fast access to data without searching sequentially through a file

Provides direct access to records using a key (e.g. ID, account number)
Useful when dealing with large files that need fast search, read, or write operations
Used in random files and sometimes in indexed sequential files

A hashing algorithm takes a key (e.g. StudentID) and uses a mathematical function to calculate a file address

Address = HashFunction(Key)

Writing a record to a file:

Address ← HashFunction(Key)
WRITE file[Address], Record

Reading a record from a file:

Address ← HashFunction(Key)
READ file[Address], Record

If the expected record is not found, collision handling must be applied to find the correct record

Method	Description
Modulo Division	Most common method: `Key MOD TableSize`
Folding Method	Breaks the key into parts and adds them together
Mid-Square Method	Square the key and use the middle digits as the address
Multiplicative Hashing	Multiplies the key by a constant and uses fractional part × tablesize

Strategy	Description
Linear probing	Try the next available slot in sequence
Overflow area	Store conflicting records in a separate file/area
Chaining	Store all records with the same address in a list