Intro
Hashing is one of the most powerful ideas in computer science: it lets us store and look up data in average O(1) (constant) time — practically instant — instead of scanning through a list. A hash table (also called a hash map, dictionary, or associative array) is the data structure built on this idea. It powers database indexes, compiler symbol tables, caches, password stores, spell-checkers and the dict/HashMap/unordered_map you use in every language.
For BCS, Bank IT and IT-officer exams, hashing is a guaranteed high-yield topic. Examiners love it because it mixes theory (collision, load factor, O(1) claims) with small calculations (compute a hash value, place keys in a table, count probes). Master the mechanics below and you can answer almost any MCQ or short question thrown at you.
Learning objectives
- Explain what hashing is and why it gives average constant-time search, insert and delete.
- Define key terms: hash function, hash value, bucket/slot, collision, load factor, rehashing.
- Compute hash values using the division, multiplication and mid-square methods.
- Distinguish and apply the two main collision-resolution strategies: separate chaining and open addressing (linear probing, quadratic probing, double hashing).
- Analyse time complexity in average and worst cases, and reason about load factor.
- Choose good hash functions and table sizes, and avoid classic pitfalls.