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?
Queue
Doubly Linked List
Stack
Binary Tree
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 + 4) % m
(i + 2) % m
What is the primary advantage of using a hashmap over a simple array for storing and retrieving data?
Hashmaps can store duplicate keys, while arrays cannot.
Hashmaps maintain data in sorted order, unlike arrays.
Hashmaps use less memory than arrays.
Hashmaps provide faster access to data based on a key, while arrays require linear search in some cases.
In the context of hashmaps, what does 'probing' refer to?
Determining the load factor of the hashmap.
Finding an alternative slot for a key when a collision occurs.
Resizing the underlying array to accommodate more keys.
Searching for a specific key in the hashmap.
In a web server, which scenario is best suited for using a hashmap to optimize performance?
Managing the order of user connections to ensure fairness
Storing and retrieving user session data
Maintaining a log of all incoming requests in chronological order
Storing and retrieving static website content like images and CSS files
How does the choice of a hash function impact the performance of a hashmap?
A well-chosen hash function minimizes collisions, leading to faster lookups and insertions.
A complex hash function guarantees a lower collision rate, improving performance.
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?
Double Hashing
Linear Probing
Separate Chaining
Quadratic Probing
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
Increased computational cost due to the second hash function
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?
Complexity in implementing the hash function itself
Degraded performance due to chaining or open addressing for collision resolution
Inability to store data that exceeds the pre-defined table size
Increased memory usage due to the fixed size allocation
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 maintain a low load factor and prevent performance degradation.
To reduce the number of keys stored in the hashmap.