Python dictionaries use open addressing for collision resolution. Which of the following techniques helps mitigate the performance degradation caused by clustering in open addressing?
Linear Probing with a prime step size
Separate Chaining
Robin Hood Hashing
Using a cryptographic hash function
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
Hashmap + Doubly Linked List
Array + Queue
Hashmap + Stack
In a hash table with open addressing using linear probing, suppose we perform a sequence of insertions where each key hashes to the same index. What is the time complexity of the nth insertion in the worst case?
O(1)
O(n log n)
O(n)
O(log n)
Which of these data structures can provide a more secure and performant alternative to a hashmap when handling user authentication data, especially in scenarios prone to hash flooding attacks?
Linked list
Array
Queue
Tree
You are designing a system to store and retrieve frequently accessed data with high performance. Which of the following hash table collision resolution strategies would generally offer the BEST performance under high load factors?
Double Hashing
Quadratic Probing
Linear Probing
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.
Generate a new key if a collision occurs.
Determine the initial index to store the key.
In the context of hashmaps, what is a 'universal hash function' primarily designed to protect against?
Collisions caused by malicious input specifically crafted to exploit a known hash function.
Attempts to guess the keys used in the hashmap by analyzing the distribution of hashed values.
Denial-of-service attacks caused by hash flooding.
Data corruption caused by accidental hash collisions between legitimate inputs.
Why is it generally recommended to avoid using mutable objects as keys in hash tables?
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.
Mutable keys make the implementation of the hash table significantly more complex.
Hash tables cannot store mutable objects as keys; only immutable objects are allowed.
How does using a cryptographic hash function with a random salt improve the security of a hashmap storing user credentials?
It encrypts the data stored in the hashmap, making it unreadable without the decryption key.
It prevents unauthorized users from accessing the hashmap's keys.
It eliminates the possibility of hash collisions.
It makes it significantly harder for attackers to perform rainbow table attacks.
Which of these statements best describes the advantage of using a perfect hash function over a regular hash function?
It reduces the memory used by the hash table.
It allows for faster key insertions.
It guarantees constant-time search, insertion, and deletion in the worst case.
It eliminates the need for collision handling.