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(n log n)
O(1)
O(log n)
O(n)
In the context of amortized analysis of hash table operations, what does the term "amortized" refer to?
The time complexity of an operation when the hash table is full.
The average time complexity of an operation over a sequence of operations.
The best-case time complexity of an operation.
The worst-case time complexity of an operation.
How can a hash flooding attack impact the performance of a web server using a hashmap to store session data?
It can cause a denial-of-service by forcing the server to handle a large number of collisions.
It has no impact on performance, as hash flooding attacks only target data integrity.
It can improve the efficiency of the hashmap by distributing data more evenly.
It can lead to increased memory usage and faster response times.
Which of the following statements accurately describes a key difference in the behavior of Python dictionaries and Java HashMaps?
Python dictionaries maintain insertion order, while Java HashMaps do not guarantee any specific order.
Python dictionaries use separate chaining for collision resolution, while Java HashMaps employ open addressing.
Java HashMaps allow null keys and values, while Python dictionaries do not.
Java HashMaps are synchronized and thread-safe, whereas Python dictionaries are not.
What is the primary advantage of using a universal 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 provides better performance than any single, fixed hash function.
It ensures constant-time performance for all operations.
In cuckoo hashing, how many hash functions are typically used?
It depends on the size of the hash table.
3
2
1
In Python, what is the purpose of the __hash__ method when used in conjunction with dictionaries?
__hash__
To define a custom sorting order for keys in the dictionary.
To provide a mechanism for iterating over the key-value pairs in the dictionary.
To determine the maximum number of elements that can be stored in the dictionary before resizing.
To specify how a custom object should be converted into a hash value for use as a key.
What is a common disadvantage of using a hashmap with a poorly chosen hash function?
Slow key generation
Inability to handle duplicate keys
Increased memory usage
Frequent hash collisions
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
Robin Hood Hashing
Linear Probing with a prime step size
Separate Chaining
Which of the following is NOT a valid mitigation strategy against hash flooding attacks?
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.
Employing a bloom filter to quickly identify and discard potentially malicious input.
Using a fixed-size hashmap to limit the maximum number of collisions.