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 binary tree where words are stored in the nodes and their frequencies are stored in the leaves
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
How does universal hashing enhance the robustness of hash tables?
By minimizing the impact of hash collisions on retrieval time
By ensuring a uniform distribution of keys across the hash table
By eliminating the possibility of hash collisions entirely
By dynamically adjusting the hash function to the input data
What is the primary advantage of using a hashmap over a simple array for storing and retrieving data?
Hashmaps maintain data in sorted order, unlike arrays.
Hashmaps use less memory than arrays.
Hashmaps can store duplicate keys, while arrays cannot.
Hashmaps provide faster access to data based on a key, while arrays require linear search in some cases.
What is a potential drawback of using double hashing for collision resolution compared to linear or quadratic probing?
Increased computational cost due to the second hash function
Requires dynamic memory allocation for linked lists
Not suitable for use with open addressing
Higher risk of primary clustering
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
What is the primary motivation behind designing hash functions with a uniform distribution property?
To simplify the implementation of the hash function itself
To reduce the memory footprint of the hash table
To maximize the amount of data that can be stored in the hash table
To minimize the occurrence of hash collisions and improve efficiency
You need to identify the first non-repeating character in a string. How can a hashmap be utilized to solve this problem efficiently?
Store the characters of the string as keys in the hashmap, and their positions as values. The first character with the lowest position value is the first non-repeating character.
Store the frequency of each character in the hashmap, then iterate through the string and return the first character with a frequency of 1.
Use the hashmap to store the unique characters of the string, then iterate through the hashmap to find the first non-repeating character.
A hashmap cannot be used efficiently for this problem.
How does quadratic probing aim to mitigate the clustering problem in open addressing?
By probing with exponentially increasing intervals
By probing with quadratically increasing intervals
By using a second hash function to determine the probe sequence
By probing linearly with a fixed step size
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 hash functions, what does the avalanche effect refer to?
A small change in input causing a significant change in output
Increased likelihood of hash collisions with larger datasets
Gradual degradation of hash performance over time
Uneven distribution of keys within the hash table