HomeSubjectsUniversityBlogAbout

Hashing

Topic in Data Structures & Algorithms

210 total MCQsShowing 30 with explanations10 Easy10 Medium10 Hard
Start Timed Quiz on HashingBack to Data Structures & Algorithms

About This Topic

Hashing maps keys to positions in a fixed-size table using a hash function, allowing insertion, deletion and lookup in constant time on average. Questions examine what makes a good hash function, including the division method and why a prime table size spreads keys more evenly. Collision resolution is central: separate chaining versus open addressing with linear probing, quadratic probing and double hashing, along with primary clustering. Load factor, expected chain length and when to trigger rehashing in O(n) time are common calculations. Advanced items cover Bloom filters, which allow false positives but never false negatives, and the O(n) worst case when many keys collide.

Below are 30 practice questions from a pool of 210 Hashing MCQs, one of 12 topics in Data Structures & Algorithms. Each shows the correct answer with an explanation; when you are ready, take a timed quiz to test recall under exam conditions.

Practice Questions

Each question below shows the correct answer with a full explanation. Use these to build conceptual understanding before attempting a timed quiz.

HashingEasy

Q1. What is a collision in hashing?

  1. A.When a key is not found in the table
  2. B.When two keys hash to the same index✓ Correct
  3. C.When the hash table is completely full
  4. D.When the hash function fails to compute

Explanation

A collision occurs when two different keys produce the same hash value (index) in the hash table.

Report an error in this question

HashingEasy

Q2. What is a hash table?

  1. A.A binary tree data structure
  2. B.A sorted array structure
  3. C.A type of linked list structure
  4. D.A key-value store using hash function✓ Correct

Explanation

A hash table (hash map) stores key-value pairs and uses a hash function to compute an index for quick insertion, deletion, and lookup.

Report an error in this question

HashingEasy

Q3. What is the worst-case time complexity of hash table lookup?

  1. A.O(1)
  2. B.O(n^2)
  3. C.O(log n)
  4. D.O(n)✓ Correct

Explanation

In the worst case, all keys hash to the same index, creating a single linked list (chaining) that must be traversed, giving O(n).

Report an error in this question

HashingEasy

Q4. What is the average time complexity of lookup in a hash table?

  1. A.O(n)
  2. B.O(log n)
  3. C.O(n^2)
  4. D.O(1)✓ Correct

Explanation

With a good hash function and low load factor, hash table lookups take O(1) average time.

Report an error in this question

HashingMedium

Q5. What is linear probing?

  1. A.Using a linear hash function for keys
  2. B.Checking next consecutive slots on collision✓ Correct
  3. C.Using a linked list for collision handling
  4. D.Probing with a linear mathematical equation

Explanation

Linear probing resolves collisions by sequentially checking the next slots (index + 1, index + 2, ...) until an empty slot is found.

Report an error in this question

HashingEasy

Q6. What is a hash function?

  1. A.A function that encrypts all data
  2. B.A function that compresses file data
  3. C.A function that sorts data elements
  4. D.A function that maps data to fixed-size value✓ Correct

Explanation

A hash function maps input data of arbitrary size to a fixed-size output value, used to determine the index in a hash table.

Report an error in this question

HashingEasy

Q7. Which of the following is a simple hash function for integers?

  1. A.h(k) = k + table_size
  2. B.h(k) = k × table_size
  3. C.h(k) = k / table_size
  4. D.h(k) = k mod table_size✓ Correct

Explanation

The division method h(k) = k mod table_size is one of the simplest and most common hash functions for integer keys.

Report an error in this question

HashingEasy

Q8. What is the purpose of a hash table?

  1. A.To store data in sorted ascending order
  2. B.To compress data for storage saving
  3. C.To sort data elements efficiently
  4. D.To provide fast insert, delete, and lookup✓ Correct

Explanation

Hash tables provide average O(1) time for insertion, deletion, and lookup operations.

Report an error in this question

HashingEasy

Q9. What happens when you insert a key that already exists in a hash table?

  1. A.The insertion is silently ignored completely
  2. B.Both old and new values are stored
  3. C.The old value is typically updated with new✓ Correct
  4. D.It causes a runtime error exception

Explanation

In most hash table implementations, inserting an existing key updates (overwrites) the associated value.

Report an error in this question

HashingMedium

Q10. What is open addressing in hash tables?

  1. A.Using multiple hash tables for distribution
  2. B.Finding another open slot when collision occurs✓ Correct
  3. C.Doubling the table size on every collision
  4. D.Using linked lists for collision resolution

Explanation

Open addressing resolves collisions by probing for the next available slot in the hash table itself, rather than using external data structures.

Report an error in this question

HashingEasy

Q11. What is chaining in hash tables?

  1. A.Linking multiple hash tables together
  2. B.Connecting hash functions in sequence
  3. C.Storing colliding elements in a linked list✓ Correct
  4. D.A type of hash function computation

Explanation

Chaining handles collisions by maintaining a linked list at each index; colliding elements are appended to the list at that index.

Report an error in this question

HashingEasy

Q12. What is the load factor of a hash table?

  1. A.The ratio of entries to number of slots✓ Correct
  2. B.The number of hash functions being used
  3. C.The total number of collisions occurred
  4. D.The total size of the hash table

Explanation

Load factor = (number of entries) / (number of slots). It measures how full the hash table is.

Report an error in this question

HashingMedium

Q13. What is the primary clustering problem in linear probing?

  1. A.Keys are stored in sorted order clusters
  2. B.Consecutive occupied slots form long clusters✓ Correct
  3. C.Hash values clustering near zero index
  4. D.Multiple hash functions produce same values

Explanation

Primary clustering occurs when consecutive occupied slots form long clusters, causing new insertions and lookups near those clusters to take longer.

Report an error in this question

HashingMedium

Q14. What is double hashing?

  1. A.Using two hash functions for probe step size✓ Correct
  2. B.Hashing the hash value itself recursively
  3. C.Hashing a value twice in succession
  4. D.Using two separate hash tables for storage

Explanation

Double hashing uses a second hash function to determine the step size for probing: h(k, i) = (h1(k) + i × h2(k)) mod m.

Report an error in this question

HashingMedium

Q15. What is quadratic probing?

  1. A.Using four different hash functions total
  2. B.Squaring the hash value before modding
  3. C.Using a quadratic hash function for keys
  4. D.Probing at positions h+1², h+2², h+3², etc.✓ Correct

Explanation

Quadratic probing uses a quadratic function to determine the next probe position: h(k) + 1², h(k) + 2², h(k) + 3², etc.

Report an error in this question

HashingMedium

Q16. What is rehashing?

  1. A.Hashing the same key multiple times in a row
  2. B.Removing all elements and starting fresh over
  3. C.Changing the hash function to a new one
  4. D.Creating a larger table and reinserting all elements✓ Correct

Explanation

Rehashing involves creating a new hash table (usually double the size) and reinserting all existing elements when the load factor gets too high.

Report an error in this question

HashingMedium

Q17. Why should the hash table size be a prime number?

  1. A.It is required by all hash functions
  2. B.It distributes hash values more uniformly✓ Correct
  3. C.It speeds up the hash value computation
  4. D.It makes the table smaller in memory

Explanation

A prime table size helps distribute keys more uniformly across the table, especially with the division method, reducing the likelihood of collisions.

Report an error in this question

HashingMedium

Q18. What is the multiplication method for hashing?

  1. A.h(k) = k mod (m × 2)
  2. B.h(k) = k^2 mod m
  3. C.h(k) = floor(m × (k × A mod 1)) where 0 < A < 1✓ Correct
  4. D.h(k) = k × m

Explanation

The multiplication method computes h(k) = floor(m × (k × A mod 1)), where A is a constant (commonly the golden ratio ≈ 0.618).

Report an error in this question

HashingMedium

Q19. What is the advantage of chaining over open addressing?

  1. A.Chaining is always faster for all operations
  2. B.Chaining uses less memory per element overall
  3. C.Chaining handles high load factors and deletion better✓ Correct
  4. D.Chaining has better CPU cache performance overall

Explanation

Chaining handles collisions gracefully even at high load factors, and deletion is straightforward (just remove from the linked list).

Report an error in this question

HashingHard

Q20. What is a Bloom filter?

  1. A.A type of hash table with chaining
  2. B.A comparison-based sorting algorithm
  3. C.A filter for removing duplicate elements
  4. D.A probabilistic structure testing set membership✓ Correct

Explanation

A Bloom filter uses multiple hash functions and a bit array to test membership. It can have false positives but never false negatives.

Report an error in this question

HashingHard

Q21. What is cuckoo hashing?

  1. A.A technique using random hash function selection
  2. B.A technique using two hash functions with displacement✓ Correct
  3. C.A hashing technique inspired by bird nesting
  4. D.A type of perfect hashing for static keys

Explanation

Cuckoo hashing uses two hash functions and tables. On collision, the new element displaces the existing one, which is then rehashed to its alternative location.

Report an error in this question

HashingHard

Q22. What is universal hashing?

  1. A.Hashing all elements to the same single bucket
  2. B.Using the same hash function across all applications
  3. C.Randomly selecting a hash function from a family of functions✓ Correct
  4. D.A single hash function that works for all data types

Explanation

Universal hashing randomly selects a hash function from a family of functions, guaranteeing that the probability of collision for any two keys is at most 1/m.

Report an error in this question

HashingMedium

Q23. What is a hash set?

  1. A.A multiset allowing duplicate elements
  2. B.A set using hashing for fast unique lookups✓ Correct
  3. C.A sorted set with ordered elements
  4. D.A set implemented using sorted arrays

Explanation

A hash set is a collection that stores unique elements using hashing, providing O(1) average time for add, remove, and contains operations.

Report an error in this question

HashingHard

Q24. What is consistent hashing?

  1. A.Using the same hash function consistently always
  2. B.A collision-free hashing technique for all inputs
  3. C.A hashing that always produces the same output
  4. D.A scheme remapping only a fraction of keys on change✓ Correct

Explanation

Consistent hashing maps both keys and nodes to a ring. When a node is added or removed, only keys near that node are remapped, minimizing disruption.

Report an error in this question

HashingHard

Q25. What is perfect hashing?

  1. A.A hash function that always distributes keys evenly
  2. B.A hash function with no collisions for any input set
  3. C.A hashing technique that requires no table at all
  4. D.A two-level scheme guaranteeing O(1) worst-case lookup✓ Correct

Explanation

Perfect hashing uses a two-level scheme with universal hashing at each level, achieving O(1) worst-case lookup time for a known, static set of keys.

Report an error in this question

HashingHard

Q26. What is the purpose of a cryptographic hash function?

  1. A.To speed up hash table lookups efficiently
  2. B.To compress files to smaller size format
  3. C.To produce collision-resistant irreversible fixed output✓ Correct
  4. D.To sort data in a deterministic order

Explanation

Cryptographic hash functions (e.g., SHA-256) produce fixed-size digests that are one-way (hard to reverse) and collision-resistant, used in security applications.

Report an error in this question

HashingHard

Q27. What is Robin Hood hashing?

  1. A.A two-level hashing scheme with perfect balance
  2. B.A charitable hashing distribution across buckets
  3. C.Stealing hash values from other tables entirely
  4. D.Open addressing where longer probes displace shorter ones✓ Correct

Explanation

Robin Hood hashing is an open addressing technique where a new element can displace an existing one if the new element's probe distance is longer, reducing variance in probe lengths.

Report an error in this question

HashingHard

Q28. What is hopscotch hashing?

  1. A.An open addressing scheme with bounded neighborhoods✓ Correct
  2. B.A random displacement hashing for load balance
  3. C.A hashing game-based approach to distribution
  4. D.A chaining variant using skip list buckets

Explanation

Hopscotch hashing ensures items are stored within a fixed-size neighborhood of their original hash bucket, combining benefits of open addressing and chaining with good cache performance.

Report an error in this question

HashingHard

Q29. What is the false positive probability of a Bloom filter with m bits, k hash functions, and n inserted elements?

  1. A.(1 - e^(-kn/m))^k approx✓ Correct
  2. B.n / m ratio
  3. C.1 / 2^k value
  4. D.k / m ratio

Explanation

The false positive probability is approximately (1 - e^(-kn/m))^k, where m is the number of bits, k is hash functions, and n is inserted elements.

Report an error in this question

HashingHard

Q30. What is the expected maximum chain length in a hash table with n elements and n slots using chaining?

  1. A.O(log n / log log n)✓ Correct
  2. B.O(√n)
  3. C.O(1)
  4. D.O(n)

Explanation

With uniform hashing and load factor 1, the expected maximum chain length is Θ(log n / log log n).

Report an error in this question

More Data Structures & Algorithms Topics

Foundations of DS & Algorithms

Practice MCQs with explanations

Linear Data Structures

Practice MCQs with explanations

Non-Linear Data Structures

Practice MCQs with explanations

Searching Algorithms

Practice MCQs with explanations

Sorting Algorithms

Practice MCQs with explanations

Tree Algorithms

Practice MCQs with explanations

Ready to test yourself on Hashing?

Take a timed quiz drawn from 210+ questions on this topic. No signup required — your progress saves in your browser.

Start Hashing Quiz