How does universal hashing enhance the robustness of hash tables?
By dynamically adjusting the hash function to the input data
By minimizing the impact of hash collisions on retrieval time
By eliminating the possibility of hash collisions entirely
By ensuring a uniform distribution of keys across the hash table
What is the primary advantage of using a hashmap over a simple array for storing and retrieving data?
Hashmaps use less memory than arrays.
Hashmaps provide faster access to data based on a key, while arrays require linear search in some cases.
Hashmaps maintain data in sorted order, unlike arrays.
Hashmaps can store duplicate keys, while arrays cannot.
When does rehashing typically occur in a hashmap?
Every time a new key is inserted.
When the hash function is modified.
When the hashmap is cleared using the clear() method.
When the load factor exceeds a predetermined threshold.
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.
In the context of hash functions, what does the avalanche effect refer to?
Uneven distribution of keys within the hash table
A small change in input causing a significant change in output
Gradual degradation of hash performance over time
Increased likelihood of hash collisions with larger datasets
In a system where memory usage is a major concern, what trade-off should be considered when using a hashmap?
Using a complex hash function always reduces collisions and memory usage.
Collision resolution strategies have no impact on memory consumption.
A larger hash table size generally results in faster lookups but consumes more memory.
Hashmaps always use less memory than arrays for storing the same data.
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
Increased memory usage due to the fixed size allocation
Complexity in implementing the hash function itself
Degraded performance due to chaining or open addressing for collision resolution
How are deletions typically handled in a hashmap with open addressing to avoid creating 'holes' that disrupt search operations?
Deletions are not allowed in hashmaps with open addressing.
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.
What advantage does separate chaining have over open addressing techniques in hash table collision resolution?
Faster search times at high load factors
Simpler implementation
Handles load factors greater than 1 gracefully
Lower memory overhead
What is a potential drawback of using double hashing for collision resolution compared to linear or quadratic probing?
Higher risk of primary clustering
Not suitable for use with open addressing
Requires dynamic memory allocation for linked lists
Increased computational cost due to the second hash function