You need to count the frequency of each word in a large text document. Which combination of data structures would be most efficient for this task?
A hashmap where words are keys and their frequencies are values
A sorted linked list where each node contains a word and its frequency
A binary tree where words are stored in the nodes and their frequencies are stored in the leaves
Two arrays: one for storing words and one for storing their frequencies
In a system where memory usage is a major concern, what trade-off should be considered when using a hashmap?
Collision resolution strategies have no impact on memory consumption.
A larger hash table size generally results in faster lookups but consumes more memory.
Hashmaps always use less memory than arrays for storing the same data.
Using a complex hash function always reduces collisions and memory usage.
Which of the following scenarios could potentially lead to collisions in a hashmap?
Hashing two different keys to the same index in the hash table
Using a hash function that distributes keys evenly across the hash table
Storing keys with a wide range of values
Having a hash table size much larger than the number of keys being stored
In the context of hash functions, what does the avalanche effect refer to?
A small change in input causing a significant change in output
Increased likelihood of hash collisions with larger datasets
Gradual degradation of hash performance over time
Uneven distribution of keys within the hash table
How does quadratic probing aim to mitigate the clustering problem in open addressing?
By probing linearly with a fixed step size
By using a second hash function to determine the probe sequence
By probing with quadratically increasing intervals
By probing with exponentially increasing intervals
Which collision resolution strategy is generally preferred for hash tables with open addressing when the load factor is low?
Linear Probing
Double Hashing
Separate Chaining
Quadratic Probing
Which collision resolution technique involves using a second, independent hash function to compute the probe sequence?
In the context of hashmaps, what does 'probing' refer to?
Finding an alternative slot for a key when a collision occurs.
Determining the load factor of the hashmap.
Searching for a specific key in the hashmap.
Resizing the underlying array to accommodate more keys.
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 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.
Hashmaps can store duplicate keys, while arrays cannot.
In the context of universal hashing, what makes a family of hash functions 'universal'?
The guarantee of zero collisions for any input set
Its use of a single, universally applicable hash function
The property that the probability of collision between any two keys is bounded
Its ability to adapt to any data distribution