In a hash table using open addressing with quadratic probing, if the initial hash function maps a key to index 'i', and a collision occurs, what is the index probed in the second attempt (assuming table size 'm')?
(i + 4) % m
(i + 1) % m
(i + 2) % m
(i * 2) % m
You are implementing an LRU (Least Recently Used) cache. Which data structure, in conjunction with a hashmap, is most suitable for tracking the usage order of cached items?
Doubly Linked List
Binary Tree
Stack
Queue
What is the primary motivation behind designing hash functions with a uniform distribution property?
To minimize the occurrence of hash collisions and improve efficiency
To simplify the implementation of the hash function itself
To maximize the amount of data that can be stored in the hash table
To reduce the memory footprint of the hash table
How does an increasing load factor generally impact the performance of a hashmap?
It has no significant impact on performance.
It degrades performance due to a higher probability of collisions.
It improves performance by reducing memory usage.
It depends on the specific hash function being used.
In a system where memory usage is a major concern, what trade-off should be considered when using a hashmap?
Hashmaps always use less memory than arrays for storing the same data.
Collision resolution strategies have no impact on memory consumption.
A larger hash table size generally results in faster lookups but consumes more memory.
Using a complex hash function always reduces collisions and memory usage.
What is a potential drawback of using double hashing for collision resolution compared to linear or quadratic probing?
Not suitable for use with open addressing
Increased computational cost due to the second hash function
Requires dynamic memory allocation for linked lists
Higher risk of primary clustering
What is the primary advantage of using a hashmap over a simple array for storing and retrieving data?
Hashmaps use less memory than arrays.
Hashmaps can store duplicate keys, while arrays cannot.
Hashmaps provide faster access to data based on a key, while arrays require linear search in some cases.
Hashmaps maintain data in sorted order, unlike arrays.
What is a primary disadvantage of using linear probing for collision resolution in a hash table?
Increased potential for primary clustering
Not suitable for open addressing
Complex implementation
Higher memory overhead compared to chaining
In a hash table using separate chaining for collision resolution, what is the worst-case time complexity for searching for an element?
O(1)
O(n)
O(log n)
O(n log n)
What is a significant disadvantage of using a fixed-size hash table in conjunction with a hash function prone to collisions?
Inability to store data that exceeds the pre-defined table size
Complexity in implementing the hash function itself
Increased memory usage due to the fixed size allocation
Degraded performance due to chaining or open addressing for collision resolution