Courses / HEC NSCT – National Skill Competency Test: Complete Preparation for Computing Graduates
3.5 Hashing
Area 3 – Data Structures & Algorithms (10%) · 35 min read · 12 MCQs to check yourself
A hash table stores key–value pairs. A hash function turns a key into an index, e.g. h(k) = k mod m (m = table size, ideally a prime).
- Average search / insert / delete: O(1); worst case O(n) when many keys collide.
- Collision – two keys get the same index. Handling:
- Chaining: each slot keeps a linked list.
- Open addressing: find another empty slot – linear probing (h + 1, h + 2 …, causes primary clustering), quadratic probing (h + 1², h + 2² …), double hashing (second hash gives the step).
- Load factor α = n / m; when it grows (e.g. > 0.75) the table is resized/rehashed.
- Good hash functions spread keys uniformly and are fast. Python
dictand JavaHashMapare hash tables. - Cryptographic hashes (SHA-256) are different – they are for security (Unit 10).
Hash tables in 4 minutes (Michael Sambol)
This lesson ends with a quiz of 12 MCQs. Open the lesson on PrepOasis to take it and save your progress.
Previous: 3.4 Graphs · Next: 3.6 Searching, Sorting and Algorithm Design