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)
O(n log n)
O(log n)
O(1)
Which collision resolution strategy generally performs better in terms of cache locality?
Cache locality is irrelevant to hash tables
Separate Chaining
Both perform equally well
Open Addressing
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 encrypts the data stored in the hashmap, making it unreadable without the decryption key.
It makes it significantly harder for attackers to perform rainbow table attacks.
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 time complexity of an operation when the hash table is full.
The average time complexity of an operation over a sequence of operations.
The worst-case time complexity of an operation.
The best-case time complexity of an operation.
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
Linear Probing
Quadratic Probing
In the context of hash tables, what does a high load factor indicate?
Faster insertion operations.
A more efficient hash function is being used.
Lower memory usage.
A higher probability of collisions.
What mechanism does Java's ConcurrentHashMap employ to allow for concurrent reads and updates while maintaining thread safety?
Read-write locks separating readers and writers
A single global lock for all operations
Lock-free data structures using atomic operations
Fine-grained locking at the bucket level
What is the primary reason for using a prime number as the size of a hash table in many implementations?
To make the implementation of the hash table simpler.
To increase the speed of hash function computation.
To minimize the memory usage of the hash table.
To ensure an even distribution of keys across the hash table, reducing collisions.
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?
Hashmap + Doubly Linked List
Hashmap + Stack
Array + Queue
Binary Search Tree + Heap
Which of the following statements accurately describes a key difference in the behavior of Python dictionaries and Java HashMaps?
Java HashMaps are synchronized and thread-safe, whereas Python dictionaries are 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 allow null keys and values, while Python dictionaries do not.