You are implementing an LRU (Least Recently Used) cache with a fixed capacity. Which data structure combination would be most suitable for efficiently managing the cache?
Binary Search Tree + Heap
Array + Queue
Hashmap + Doubly Linked List
Hashmap + Stack
In a web server implemented using a hashmap to store cached web pages, which collision resolution strategy is generally preferred for its performance in handling a high volume of concurrent requests?
Double Hashing
Separate Chaining with balanced binary search trees
Open Addressing with linear probing
Separate Chaining with linked lists
In a hash table using double hashing, the second hash function is used to:
Calculate the size of the hash table.
Determine the step size for probing in case of a collision.
Determine the initial index to store the key.
Generate a new key if a collision occurs.
In a hashmap implementation using open addressing with linear probing, what is the worst-case time complexity for searching for a key if the hash table is nearly full?
O(1)
O(n)
O(n log n)
O(log n)
How does using a cryptographic hash function with a random salt improve the security of a hashmap storing user credentials?
It prevents unauthorized users from accessing the hashmap's keys.
It makes it significantly harder for attackers to perform rainbow table attacks.
It encrypts the data stored in the hashmap, making it unreadable without the decryption key.
It eliminates the possibility of hash collisions.
In the context of amortized analysis of hash table operations, what does the term "amortized" refer to?
The best-case time complexity of an operation.
The average time complexity of an operation over a sequence of operations.
The time complexity of an operation when the hash table is full.
The worst-case time complexity of an operation.
Python dictionaries use open addressing for collision resolution. Which of the following techniques helps mitigate the performance degradation caused by clustering in open addressing?
Using a cryptographic hash function
Separate Chaining
Linear Probing with a prime step size
Robin Hood Hashing
Why is it generally recommended to avoid using mutable objects as keys in hash tables?
Hash tables cannot store mutable objects as keys; only immutable objects are allowed.
Mutable keys make the implementation of the hash table significantly more complex.
Using mutable keys increases the memory overhead of the hash table.
Mutable keys can lead to inconsistent state if their values are modified after being inserted into the hash table.
In the context of hashmaps, what is a 'universal hash function' primarily designed to protect against?
Attempts to guess the keys used in the hashmap by analyzing the distribution of hashed values.
Data corruption caused by accidental hash collisions between legitimate inputs.
Denial-of-service attacks caused by hash flooding.
Collisions caused by malicious input specifically crafted to exploit a known hash function.
Which collision resolution strategy generally performs better in terms of cache locality?
Cache locality is irrelevant to hash tables
Open Addressing
Both perform equally well