Hash Tables

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 20, 2024

What is a hash table?
A) A data structure that stores data in a sorted manner
B) A data structure that maps keys to values for efficient data retrieval
C) A type of linked list
D) A tree-based data structure
Answer: B) A data structure that maps keys to values for efficient data retrieval

What is the primary advantage of using a hash table?
A) It allows for ordered data storage
B) It provides constant time complexity for average-case search, insert, and delete operations
C) It requires less memory
D) It is easier to implement than other data structures
Answer: B) It provides constant time complexity for average-case search, insert, and delete operations

What is the role of a hash function in a hash table?
A) To sort the data
B) To generate a unique identifier for each value
C) To compute an index based on a key
D) To convert data types
Answer: C) To compute an index based on a key

What is a common issue encountered when using hash tables?
A) Data loss
B) High memory consumption
C) Collisions
D) Slow retrieval times
Answer: C) Collisions

How can collisions be resolved in hash tables?
A) By increasing the size of the hash table
B) By using chaining or open addressing
C) By sorting the data
D) By changing the hash function
Answer: B) By using chaining or open addressing

In chaining, how is a collision resolved?
A) By overwriting the existing value
B) By storing multiple values at the same index using a linked list
C) By creating a new hash table
D) By skipping to the next index
Answer: B) By storing multiple values at the same index using a linked list

What is open addressing in hash tables?
A) Storing all values in a single linked list
B) Finding the next available slot in the hash table for a colliding key
C) Using multiple hash functions
D) Deleting keys from the hash table
Answer: B) Finding the next available slot in the hash table for a colliding key

Which of the following is a common hash function?
A) Multiplication hashing
B) Division hashing
C) Linear probing
D) Both A and B
Answer: D) Both A and B

What is the load factor in a hash table?
A) The ratio of the number of elements to the size of the hash table
B) The maximum number of collisions allowed
C) The total number of slots in the hash table
D) The number of unique keys stored
Answer: A) The ratio of the number of elements to the size of the hash table

What happens when the load factor exceeds a certain threshold?
A) The hash table is deleted
B) A new hash table with a larger size is created
C) No more elements can be added
D) The performance improves
Answer: B) A new hash table with a larger size is created

What is the purpose of resizing a hash table?
A) To decrease the memory usage
B) To reduce the likelihood of collisions
C) To make the hash table easier to manage
D) To improve the speed of the hash function
Answer: B) To reduce the likelihood of collisions

Which probing technique uses a fixed interval for collision resolution?
A) Quadratic probing
B) Linear probing
C) Double hashing
D) Chaining
Answer: B) Linear probing

What is double hashing?
A) Using two different hash functions to resolve collisions
B) Storing data in two separate hash tables
C) Doubling the size of the hash table
D) Using a single hash function multiple times
Answer: A) Using two different hash functions to resolve collisions

In a perfect hash function, how many collisions would occur?
A) One
B) A few
C) None
D) Many
Answer: C) None

Which of the following is NOT a characteristic of a good hash function?
A) Fast computation
B) Uniform distribution of keys
C) High complexity
D) Minimized collisions
Answer: C) High complexity

What is the typical time complexity for searching in a hash table in the average case?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: A) O(1)

Which data structure is often used to implement chaining in hash tables?
A) Array
B) Stack
C) Linked list
D) Tree
Answer: C) Linked list

What is the primary disadvantage of chaining as a collision resolution method?
A) It can consume extra memory
B) It is slower than open addressing
C) It does not allow duplicate keys
D) It requires complex implementations
Answer: A) It can consume extra memory

In linear probing, if a collision occurs, how is the next slot found?
A) By using a random function
B) By checking subsequent slots in a sequential manner
C) By doubling the index
D) By using a different hash function
Answer: B) By checking subsequent slots in a sequential manner

What is the time complexity of inserting an element into a hash table in the worst case?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Answer: B) O(n)

Which scenario can lead to poor performance in a hash table?
A) Using a perfect hash function
B) Having a low load factor
C) Using a poor hash function that leads to clustering
D) Resizing the hash table appropriately
Answer: C) Using a poor hash function that leads to clustering

What is clustering in hash tables?
A) A method of grouping similar keys
B) A situation where consecutive slots are filled due to collisions
C) A technique to optimize memory usage
D) A way to increase the load factor
Answer: B) A situation where consecutive slots are filled due to collisions

Which of the following best describes an open addressing strategy?
A) Elements are stored in the next available position
B) Elements are linked together in chains
C) Elements are stored randomly
D) Elements can be stored in multiple tables
Answer: A) Elements are stored in the next available position

What happens to the performance of a hash table as the load factor increases?
A) It improves
B) It remains constant
C) It decreases
D) It becomes unpredictable
Answer: C) It decreases

What is the worst-case scenario for a hash table?
A) No collisions occur
B) All keys hash to the same index
C) The table is empty
D) The load factor is very low
Answer: B) All keys hash to the same index

What is a characteristic of quadratic probing?
A) It uses a linear search pattern
B) It uses a quadratic function to determine the next index
C) It requires a secondary hash function
D) It is not suitable for hash tables
Answer: B) It uses a quadratic function to determine the next index

Which operation can be inefficient in a hash table when the load factor is high?
A) Insertion
B) Deletion
C) Search
D) All of the above
Answer: D) All of the above

What is the purpose of a secondary hash function in double hashing?
A) To create a backup
B) To provide an alternative index when a collision occurs
C) To increase the load factor
D) To resize the hash table
Answer: B) To provide an alternative index when a collision occurs

What is a drawback of open addressing compared to chaining?
A) It can lead to clustering
B) It requires more memory
C) It is more complex
D) It does not allow duplicate keys
Answer: A) It can lead to clustering

Which of the following scenarios is best suited for a hash table?
A) When order matters
B) When frequent access and modification are needed
C) When data needs to be sorted
D) When data is static
Answer: B) When frequent access and modification are needed

What happens if a hash table is resized?
A) All existing keys are lost
B) The table must be rebuilt with a new hash function
C) All keys must be rehashed and reintegrated into the new table
D) The performance is unaffected
Answer: C) All keys must be rehashed and reintegrated into the new table

How does the choice of a hash function affect the performance of a hash table?
A) It has no impact
B) A better hash function can minimize collisions and improve performance
C) A poor hash function increases memory usage
D) A better hash function requires more time to compute
Answer: B) A better hash function can minimize collisions and improve performance

Which of the following is a common application of hash tables?
A) Storing ordered data
B) Implementing associative arrays or dictionaries
C) Performing mathematical computations
D) Storing large datasets sequentially
Answer: B) Implementing associative arrays or dictionaries

 

Data Structures MCQs

Basic Concepts

  1. Introduction to Data Structures
  2. Complexity Analysis MCQs

Linear Data Structures MCQs

  1. Arrays MCQs
  2. Linked Lists MCQs
  3. Stacks MCQs
  4. Queues MCQs

Non-Linear Data Structures MCQs

  1. Trees MCQs
  2. Heaps MCQs
  3. Graphs MCQs

Hashing MCQs MCQs

  1. Hash Tables

Sorting and Searching Algorithms MCQs 

  1. Sorting Algorithms MCQs
  2. Searching Algorithms MCQs

Miscellaneous

  1. Memory Management in data structures MCQs
  2. String Manipulation Algorithms MCQs
  1. Data Structures MCQs 1
  2. Data Structures MCQs 2
  3. Data Structures MCQs 3
  4. Data Structures MCQs 4
  5. Data Structures MCQs 5
  6. Stacks Solved MCQs
  7. Queues MCQs
  8. pointer mcqs
  9. Array MCQs