Hash Maps and Sets: Lookup and Frequency Fundamentals Quiz

Test your understanding of hash maps and hash sets, focusing on fast lookups and frequency counting. This quiz challenges your knowledge of core concepts and practical uses related to key-value pair storage and efficient membership checks.

1. Lookup Efficiency in Hash Maps

   What is the average-case time complexity for retrieving a value by its key in a hash map?

   1. O(n^2)
   2. O(1)
   3. O(log n)
   4. O(n)

   Explanation: Retrieving a value by key in a hash map is typically O(1) on average, thanks to direct addressing via the hash function. The option O(n) suggests linear search, which only happens in worst-case scenarios like excessive collisions. O(log n) is characteristic of balanced trees, not hash maps. O(n^2) is much slower than hash map lookups and applies to some naive algorithms but not hash maps.

2. Hash Set Membership

   Which operation can a hash set perform most efficiently compared to a list: checking if an item already exists?

   1. Concatenation
   2. Iterating in order
   3. Membership test
   4. Sorting elements

   Explanation: A hash set is specifically designed for efficient membership testing, usually in constant time. Sorting elements is not a feature of sets since they are unordered. Iterating in order is not guaranteed in sets. Concatenation is a list operation, not applicable to sets.

3. Frequency Counting with a Hash Map

   How would you most effectively count how many times each word appears in a list of words?

   1. Store every word in a hash set
   2. Sort the list and count runs manually
   3. Calculate the average word length
   4. Use a hash map with words as keys and counts as values

   Explanation: A hash map allows efficient tracking of word counts by incrementing values associated with each word key. Sorting and counting runs is less efficient and more complicated. Using a hash set only answers membership, not frequency. Calculating average word length doesn’t address frequency at all.

4. Unique Elements Using Sets

   If you need to quickly find all unique numbers in a large list of integers, which data structure should you use?

   1. Queue
   2. Stack
   3. Hash set
   4. Linked list

   Explanation: A hash set naturally removes duplicates by only allowing unique elements, making it ideal for this task. A stack, queue, or linked list all allow duplicate values and wouldn't efficiently provide unique elements.

5. Duplicate Detection

   What is the most efficient way to check if a list contains any duplicate elements?

   1. Compute the average of all elements
   2. Insert elements into a hash set and check for repeated entries
   3. Iterate through the list twice for each pair
   4. Sort the list, then check consecutive elements

   Explanation: Adding elements to a hash set and checking for repeats offers a fast, efficient way to detect duplicates. Double iteration is possible but much slower (O(n^2)). Sorting then checking consecutive pairs works, but requires extra time for sorting. Computing an average doesn't help detect duplicates.

6. Hash Function Role

   What is the primary purpose of a hash function in a hash map?

   1. To order keys alphabetically
   2. To map a key to a specific slot or bucket
   3. To compare two values for equality
   4. To compress data to save space

   Explanation: The hash function maps a key to a bucket where the value is stored, enabling quick access. Ordering keys alphabetically is unrelated to hashing. Data compression is not performed by hash functions. Comparing for equality checks values directly, not via hashing.

7. Handling Collisions

   What happens in a hash map when two different keys produce the same hash value?

   1. An error stops the storage process
   2. One key is overwritten by the other
   3. A collision occurs, and both keys are stored in the same bucket
   4. Both keys are ignored and not stored

   Explanation: A collision means two distinct keys land in the same bucket, so both must be managed, often by chaining or another technique. Overwriting would lose data, which hash maps avoid. Errors do not usually occur on collision; instead, they are handled internally. Ignoring both keys would fail to store important data.

8. Hash Set vs. Hash Map

   What distinguishes a hash set from a hash map?

   1. A hash map must be ordered, but a hash set is not
   2. A hash set stores only numeric keys, while a hash map stores any type
   3. A hash set stores only keys, with no values; a hash map stores key-value pairs
   4. A hash set can store duplicate keys; a hash map cannot

   Explanation: Hash sets are collections of unique keys with no associated values, while hash maps store key-value pairs. Neither data structure is necessarily ordered, so that option is incorrect. Both structures generally prevent duplicate keys. Both can store various key types, so type restriction is incorrect.

9. Empty Hash Map Lookup

   What result should you expect if you attempt to look up a key in an empty hash map?

   1. An infinite loop occurs
   2. The key is automatically added with value zero
   3. No value is found and a null or default result is returned
   4. The lookup returns a random entry

   Explanation: If the hash map has no entries, the key can't be found and a null, none, or default is returned, depending on the implementation. Returning a random entry would be incorrect. Infinite loops do not occur with basic lookup. Automatically adding the key with a default value is not standard behavior in most implementations.

10. Hash Set Use Case

    In which situation would using a hash set be preferable to using a list?

    1. When you need to access elements by index
    2. When you want to store duplicate values
    3. When you need to maintain the order of elements
    4. When you need to check membership quickly and ensure uniqueness

    Explanation: Hash sets are best for ensuring all entries are unique and for fast membership checking. Maintaining order or accessing by index isn't supported by hash sets. Lists allow duplicates and provide indexing, but are not as efficient for membership testing.