This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Hash Tables”.
1. Which of the following is not a technique to avoid a collision?
A) Make the hash function appear random
B) Use the chaining method
C) Use uniform hashing
D) Increasing hash table size
Explanation: When the size of the hash table grows, so does the complexity of the space required to reallocate the memory size of the hash table with each collision. It is not the most effective method of avoiding a collision. By making the hash function random, using the chaining method, and using uniform hashing, we can avoid collisions.
2. What is the load factor?
A) Average array size
B) Average key size
C) Average chain length
D) Average hash table length
Explanation: The average number of elements stored in a chain in simple chaining is given by the ratio of the number of elements stored to the number of slots in the array.
3. What is simple uniform hashing?
A) Every element has equal probability of hashing into any of the slots
B) A weighted probabilistic method is used to hash elements into the slots
C) Elements has Random probability of hashing into array slots
D) Elements are hashed based on priority
Explanation: In simple uniform hashing, every given element has an equal chance of hashing into any of the array’s slots.
4. In simple uniform hashing, what is the search complexity?
Explanation: There are two cases: when the search is efficient and when it is unsuccessful; however, the complexity of both cases is O(1+alpha), where 1 is the hash function to compute and alpha is the load factor.
5. In simple chaining, what data structure is appropriate?
A) Singly linked list
B) Doubly linked list
C) Circular linked list
D) Binary trees
Explanation: Deletion is better with a doubly linked list, so it’s a good choice.
6. What is a hash table?
A) A structure that maps values to keys
B) A structure that maps keys to values
C) A structure used for storage
D) A structure used to implement stack and queue
Explanation: Associative arrays with a key-value pair are implemented using hash tables, which map keys to values.
7. If several elements are competing for the same bucket in the hash table, what is it called?
Explanation: There will be a clash among elements in a hash table if multiple elements are computing for the same bucket. Collision is the term for this situation. Collision is minimised by adding elements to a linked list and storing the linked list’s head address in a hash table.
8. What is direct addressing?
A) Distinct array position for every possible key
B) Fewer array positions than keys
C) Fewer keys than array positions
D) Same array position for all keys
Explanation: Only when we can afford to assign an array with one location per each possible key is direct addressing possible.
9. What is the search complexity in direct addressing?
Explanation: Searching takes a constant amount of time since each key has a specific array location.
10. What is a hash function?
A) A function has allocated memory to keys
B) A function that computes the location of the key in the array
C) A function that creates an array
D) A function that computes the location of the values in the array
Explanation: Since there are less array locations than keys in a hash table, the location of the key in the array must be computed using the hash function.
A hash table (also known as a hash map) is a data structure that implements an associative array abstract data form, which can map keys to values. A hash table employs a hash function to generate an index, also referred to as a hash code, into an array of buckets or slots from which the desired value can be retrieved. The key is hashed during lookup, and the hash indicates where the corresponding value is located. The hash function can allocate each key to a specific bucket in theory, but most hash table designs use an incomplete hash function, which could result in hash collisions if the hash function produces the same index for multiple keys.