Which collision resolution technique involves using a second, independent hash function to compute the probe sequence?
Quadratic Probing
Double Hashing
Separate Chaining
Linear Probing
When choosing a collision resolution strategy for a hash table, which factors are essential to consider?
Programming language and hardware architecture
Size of the keys and values being stored
All of the above
Expected data distribution and load factor
How does an increasing load factor generally impact the performance of a hashmap?
It has no significant impact on performance.
It degrades performance due to a higher probability of collisions.
It depends on the specific hash function being used.
It improves performance by reducing memory usage.
What is a potential drawback of using double hashing for collision resolution compared to linear or quadratic probing?
Higher risk of primary clustering
Increased computational cost due to the second hash function
Not suitable for use with open addressing
Requires dynamic memory allocation for linked lists
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
Degraded performance due to chaining or open addressing for collision resolution
Increased memory usage due to the fixed size allocation
Complexity in implementing the hash function itself
How does universal hashing enhance the robustness of hash tables?
By eliminating the possibility of hash collisions entirely
By dynamically adjusting the hash function to the input data
By minimizing the impact of hash collisions on retrieval time
By ensuring a uniform distribution of keys across the hash table
How are deletions typically handled in a hashmap with open addressing to avoid creating 'holes' that disrupt search operations?
By marking the slot as "deleted" and implementing a mechanism to handle such markers during search and insertion.
Deletions are not allowed in hashmaps with open addressing.
By shifting all subsequent elements one position back to fill the gap.
By simply removing the element, leaving the slot empty.
What is the primary advantage of using a hashmap over a simple array for storing and retrieving data?
Hashmaps provide faster access to data based on a key, while arrays require linear search in some cases.
Hashmaps can store duplicate keys, while arrays cannot.
Hashmaps use less memory than arrays.
Hashmaps maintain data in sorted order, unlike arrays.
You are implementing an LRU (Least Recently Used) cache. Which data structure, in conjunction with a hashmap, is most suitable for tracking the usage order of cached items?
Doubly Linked List
Stack
Queue
Binary Tree
In the context of hash functions, what does the avalanche effect refer to?
Increased likelihood of hash collisions with larger datasets
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