Which collision resolution technique involves using a second, independent hash function to compute the probe sequence?
Double Hashing
Separate Chaining
Linear Probing
Quadratic Probing
How does the choice of a hash function impact the performance of a hashmap?
A complex hash function guarantees a lower collision rate, improving performance.
A well-chosen hash function minimizes collisions, leading to faster lookups and insertions.
A simple hash function is always preferred as it reduces computational overhead.
The hash function has a negligible impact on performance compared to the data structure itself.
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
What advantage does separate chaining have over open addressing techniques in hash table collision resolution?
Simpler implementation
Lower memory overhead
Handles load factors greater than 1 gracefully
Faster search times at high load factors
In the context of hash functions, what does the avalanche effect refer to?
Gradual degradation of hash performance over time
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
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 use less memory than arrays.
Hashmaps can store duplicate keys, while arrays cannot.
Hashmaps maintain data in sorted order, unlike arrays.
In the context of universal hashing, what makes a family of hash functions 'universal'?
The property that the probability of collision between any two keys is bounded
The guarantee of zero collisions for any input set
Its use of a single, universally applicable hash function
Its ability to adapt to any data distribution
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 marking the slot as "deleted" and implementing a mechanism to handle such markers during search and insertion.
By simply removing the element, leaving the slot empty.
By shifting all subsequent elements one position back to fill the gap.
What is the purpose of dynamic resizing (rehashing) in a hashmap?
To improve the efficiency of key deletion operations.
To increase the size of the hash function's output range.
To reduce the number of keys stored in the hashmap.
To maintain a low load factor and prevent performance degradation.
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?
Stack
Queue
Doubly Linked List
Binary Tree