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(log n)
O(n log n)
O(1)
O(n)
Which of the following statements accurately describes a key difference in the behavior of Python dictionaries and Java HashMaps?
Java HashMaps allow null keys and values, while Python dictionaries do not.
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 are synchronized and thread-safe, whereas Python dictionaries are not.
Why is it generally recommended to avoid using mutable objects as keys in hash tables?
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.
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 Python, what is the purpose of the __hash__ method when used in conjunction with dictionaries?
__hash__
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.
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.
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?
Linear Probing
Double Hashing
Separate Chaining
Quadratic Probing
Which collision resolution strategy generally performs better in terms of cache locality?
Open Addressing
Both perform equally well
Cache locality is irrelevant to hash tables
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?
In the context of hashmaps, what is a 'universal hash function' primarily designed to protect against?
Denial-of-service attacks caused by hash flooding.
Data corruption caused by accidental hash collisions between legitimate inputs.
Attempts to guess the keys used in the hashmap by analyzing the distribution of hashed values.
Collisions caused by malicious input specifically crafted to exploit a known hash function.
What is a common disadvantage of using a hashmap with a poorly chosen hash function?
Inability to handle duplicate keys
Slow key generation
Frequent hash collisions
Increased memory usage
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 guarantees constant-time search, insertion, and deletion in the worst case.
It eliminates the need for collision handling.
It allows for faster key insertions.