Hash tables, also known as hash maps, are an essential data structure in computer science. They offer quick access to values based on a key. Here are some questions to test your understanding of this vital data structure.
1. What is the primary use of a hash table?
Answer:
Explanation:
Hash tables are designed to optimize the searching of a value by its key. The other options are not the primary purposes of a hash table.
2. Which of the following best describes a collision in a hash table?
Answer:
Explanation:
A collision occurs when two different keys produce the same index in a hash table.
3. What is the time complexity of a successful search in a hash table, in the best case scenario?
Answer:
Explanation:
Ideally, if there are no collisions and the hash function is perfect, retrieving a value by its key happens in constant time.
4. Which method resolves collisions by inserting the collided item into the next available space?
Answer:
Explanation:
Linear probing resolves collisions by placing the collided item into the next available slot in the hash table.
5. In the context of a hash table, what does the load factor represent?
Answer:
Explanation:
Load factor is used to determine when to resize the hash table. It’s calculated as (number of keys / array size).
6. Which of the following data structures is commonly used for implementing collision resolution in hash tables?
Answer:
Explanation:
Linked lists are often used in the “Separate Chaining” method of collision resolution.
7. What’s the main disadvantage of a high load factor in a hash table?
Answer:
Explanation:
A high load factor means the hash table is getting filled, increasing the chances of collisions, and thus, slowing down operations.
8. If a hash table has a load factor greater than 1, it means:
Answer:
Explanation:
A load factor greater than 1 indicates that the number of entries exceeds the table’s size.
9. Which of the following best describes open addressing?
Answer:
Explanation:
Open addressing means that all elements are stored in the hash table array itself, and when collisions occur, we find another slot in the same table.
10. What would be the worst case time complexity for searching an element in a hash table?
Answer:
Explanation:
If all keys collide to the same index, the search operation might need to traverse through all of them, making it O(n).
11. Which of the following scenarios would make a hash table perform poorly?
Answer:
Explanation:
Non-uniform key distribution means that many keys hash to the same indices, leading to collisions and poor performance.
12. Rehashing in a hash table means:
Answer:
Explanation:
Rehashing involves resizing the hash table (usually doubling its size) and re-inserting the elements to distribute them uniformly.
Hash tables are immensely powerful for optimizing access times. As with any data structure, understanding their underlying principles and potential pitfalls ensures efficient utilization in real-world applications.