What is a significant disadvantage of using a fixed-size hash table in conjunction with a hash function prone to collisions?
Inability to store data that exceeds the pre-defined table size
Complexity in implementing the hash function itself
Increased memory usage due to the fixed size allocation
Degraded performance due to chaining or open addressing for collision resolution
When does rehashing typically occur in a hashmap?
Every time a new key is inserted.
When the hashmap is cleared using the clear() method.
When the load factor exceeds a predetermined threshold.
When the hash function is modified.
In the context of universal hashing, what makes a family of hash functions 'universal'?
Its ability to adapt to any data distribution
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
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
A hashmap where words are keys and their frequencies are values
Two arrays: one for storing words and one for storing their frequencies
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?
O(n log n)
O(1)
O(n)
O(log n)
How does quadratic probing aim to mitigate the clustering problem in open addressing?
By using a second hash function to determine the probe sequence
By probing with quadratically increasing intervals
By probing with exponentially increasing intervals
By probing linearly with a fixed step size
In a web server, which scenario is best suited for using a hashmap to optimize performance?
Maintaining a log of all incoming requests in chronological order
Storing and retrieving static website content like images and CSS files
Storing and retrieving user session data
Managing the order of user connections to ensure fairness
How does an increasing load factor generally impact the performance of a hashmap?
It has no significant impact on performance.
It depends on the specific hash function being used.
It degrades performance due to a higher probability of collisions.
It improves performance by reducing memory usage.
Which collision resolution technique involves using a second, independent hash function to compute the probe sequence?
Linear Probing
Double Hashing
Separate Chaining
Quadratic Probing
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 + 1) % m
(i + 4) % m
(i * 2) % m
(i + 2) % m