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?
Binary Tree
Stack
Doubly Linked List
Queue
In a hash table using separate chaining for collision resolution, what is the worst-case time complexity for searching for an element?
O(n log n)
O(n)
O(log n)
O(1)
In the worst-case scenario, what is the time complexity of searching for a key in a hashmap?
What advantage does separate chaining have over open addressing techniques in hash table collision resolution?
Lower memory overhead
Simpler implementation
Handles load factors greater than 1 gracefully
Faster search times at high load factors
In a system where memory usage is a major concern, what trade-off should be considered when using a hashmap?
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.
Using a complex hash function always reduces collisions and memory usage.
Collision resolution strategies have no impact on memory consumption.
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 * 2) % m
(i + 2) % m
(i + 4) % m
How does universal hashing enhance the robustness of hash tables?
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
By minimizing the impact of hash collisions on retrieval time
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.
Which collision resolution strategy is generally preferred for hash tables with open addressing when the load factor is low?
Separate Chaining
Linear Probing
Double Hashing
Quadratic Probing
In the context of hash functions, what does the avalanche effect refer to?
Gradual degradation of hash performance over time
Uneven distribution of keys within the hash table
Increased likelihood of hash collisions with larger datasets
A small change in input causing a significant change in output