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?
Quadratic Probing
Linear Probing
Separate Chaining
Double Hashing
Hopscotch hashing aims to improve the performance of open addressing by:
Limiting the maximum distance a key can be placed from its original hash index.
Using multiple hash tables to store keys with different hash values.
Employing a binary search tree for efficient collision resolution.
Using a dynamic array to resize the table when the load factor gets high.
In the context of hashmaps, what is a 'universal hash function' primarily designed to protect against?
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.
Attempts to guess the keys used in the hashmap by analyzing the distribution of hashed values.
Which of the following is NOT a valid mitigation strategy against hash flooding attacks?
Using a fixed-size hashmap to limit the maximum number of collisions.
Employing a bloom filter to quickly identify and discard potentially malicious input.
Implementing a random salt value in the hash function to make collisions unpredictable.
Switching to a different data structure like a tree-based map that offers consistent performance.
In cuckoo hashing, how many hash functions are typically used?
1
It depends on the size of the hash table.
2
3
In the context of amortized analysis of hash table operations, what does the term "amortized" refer to?
The worst-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 best-case time complexity of an operation.
What is a common disadvantage of using a hashmap with a poorly chosen hash function?
Frequent hash collisions
Increased memory usage
Slow key generation
Inability to handle duplicate keys
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(log n)
O(n)
O(n log n)
O(1)
What is the primary advantage of using a universal hash function?
It provides better performance than any single, fixed hash function.
It eliminates the possibility of collisions entirely.
It makes the hash table resistant to attacks that exploit patterns in the hash function.
It ensures constant-time performance for all operations.
In Python, what is the purpose of the __hash__ method when used in conjunction with dictionaries?
__hash__
To determine the maximum number of elements that can be stored in the dictionary before resizing.
To provide a mechanism for iterating over the key-value pairs in the dictionary.
To specify how a custom object should be converted into a hash value for use as a key.
To define a custom sorting order for keys in the dictionary.