When does rehashing typically occur in a hashmap?
When the hash function is modified.
When the hashmap is cleared using the clear() method.
Every time a new key is inserted.
When the load factor exceeds a predetermined threshold.
In the context of universal hashing, what makes a family of hash functions 'universal'?
Its use of a single, universally applicable hash function
The guarantee of zero collisions for any input set
Its ability to adapt to any data distribution
The property that the probability of collision between any two keys is bounded
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?
A sorted linked list where each node contains a word and its frequency
Two arrays: one for storing words and one for storing their frequencies
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
What is the primary motivation behind designing hash functions with a uniform distribution property?
To simplify the implementation of the hash function itself
To maximize the amount of data that can be stored in the hash table
To reduce the memory footprint of the hash table
To minimize the occurrence of hash collisions and improve efficiency
In a hash table using separate chaining for collision resolution, what is the worst-case time complexity for searching for an element?
O(n)
O(log n)
O(1)
O(n log n)
How does the choice of a hash function impact the performance of a hashmap?
The hash function has a negligible impact on performance compared to the data structure itself.
A well-chosen hash function minimizes collisions, leading to faster lookups and insertions.
A complex hash function guarantees a lower collision rate, improving performance.
A simple hash function is always preferred as it reduces computational overhead.
What advantage does separate chaining have over open addressing techniques in hash table collision resolution?
Lower memory overhead
Handles load factors greater than 1 gracefully
Simpler implementation
Faster search times at high load factors
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.
Deletions are not allowed in hashmaps with open addressing.
By shifting all subsequent elements one position back to fill the gap.
By marking the slot as "deleted" and implementing a mechanism to handle such markers during search and insertion.
In the context of hashmaps, what does 'probing' refer to?
Determining the load factor of the hashmap.
Resizing the underlying array to accommodate more keys.
Finding an alternative slot for a key when a collision occurs.
Searching for a specific key in the hashmap.
How does universal hashing enhance the robustness of hash tables?
By dynamically adjusting the hash function to the input data
By ensuring a uniform distribution of keys across the hash table
By eliminating the possibility of hash collisions entirely
By minimizing the impact of hash collisions on retrieval time