How are deletions typically handled in a hashmap with open addressing to avoid creating 'holes' that disrupt search operations?
By simply removing the element, leaving the slot empty.
By marking the slot as "deleted" and implementing a mechanism to handle such markers during search and insertion.
By shifting all subsequent elements one position back to fill the gap.
Deletions are not allowed in hashmaps with open addressing.
In a hash table using separate chaining for collision resolution, what is the worst-case time complexity for searching for an element?
O(1)
O(n log n)
O(log n)
O(n)
In a hash table using open addressing with quadratic probing, if the initial hash function maps a key to index 'i', and a collision occurs, what is the index probed in the second attempt (assuming table size 'm')?
(i + 2) % m
(i + 1) % m
(i + 4) % m
(i * 2) % m
What is the purpose of dynamic resizing (rehashing) in a hashmap?
To improve the efficiency of key deletion operations.
To reduce the number of keys stored in the hashmap.
To increase the size of the hash function's output range.
To maintain a low load factor and prevent performance degradation.
What is a potential drawback of using double hashing for collision resolution compared to linear or quadratic probing?
Higher risk of primary clustering
Requires dynamic memory allocation for linked lists
Not suitable for use with open addressing
Increased computational cost due to the second hash function
You need to count the frequency of each word in a large text document. Which combination of data structures would be most efficient for this task?
Two arrays: one for storing words and one for storing their frequencies
A sorted linked list where each node contains a word and its frequency
A hashmap where words are keys and their frequencies are values
A binary tree where words are stored in the nodes and their frequencies are stored in the leaves
In the worst-case scenario, what is the time complexity of searching for a key in a hashmap?
Which collision resolution strategy is generally preferred for hash tables with open addressing when the load factor is low?
Separate Chaining
Double Hashing
Linear Probing
Quadratic Probing
In the context of universal hashing, what makes a family of hash functions 'universal'?
The guarantee of zero collisions for any input set
The property that the probability of collision between any two keys is bounded
Its use of a single, universally applicable hash function
Its ability to adapt to any data distribution
When does rehashing typically occur in a hashmap?
When the load factor exceeds a predetermined threshold.
When the hash function is modified.
When the hashmap is cleared using the clear() method.
Every time a new key is inserted.