Hash Maps u0026 Sets: Foundations Quiz Quiz

Sharpen your fundamental understanding of hash maps and sets through scenarios involving key operations, properties, and typical use cases. This quiz covers core concepts behind efficient data retrieval, managing duplicates, and recognizing differences between these essential data structures.

1. Basic Functionality of Hash Maps

   In a hash map implementation, what happens if you insert a new key-value pair with a key that already exists, such as inserting ('cat', 5) after ('cat', 2)?

   1. An error is thrown due to duplicate keys
   2. Both pairs are stored and accessible
   3. The value for 'cat' is updated to 5
   4. The original pair ('cat', 2) is removed entirely

   Explanation: When a new key-value pair is added to a hash map with an existing key, the value associated with that key is simply updated, not duplicated. Both pairs cannot exist together, so 'Both pairs are stored and accessible' is incorrect. The pair is not removed without replacement, so 'The original pair is removed entirely' is inaccurate. Standard hash map behavior does not throw an error for duplicate keys, making 'An error is thrown' incorrect.

2. Set Property: Uniqueness

   If you attempt to add the value 7 multiple times to a set, such as adding 7 three times in a row, how many times will 7 appear in the set?

   1. Three times
   2. Once
   3. Twice
   4. It will not appear at all

   Explanation: A set is designed to hold only unique items, so adding the same value multiple times does not create duplicates; 7 will appear just once. 'Twice' and 'Three times' misunderstand the purpose of sets. 'It will not appear at all' is incorrect since 7 does get added, just not more than once.

3. Average Time Complexity

   What is the average time complexity for searching for a specific key in a well-designed hash map?

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

   Explanation: A well-designed hash map uses hashing to provide average-case constant time complexity, O(1), for key lookups. O(log n) applies to balanced trees, not typical hash maps, making it incorrect. O(n) and O(n log n) would be expected in less efficient or degenerate cases, but not the average scenario.

4. Difference Between Hash Map and Set

   Which key distinction correctly separates the role of a hash map from that of a set?

   1. A hash map cannot check for the existence of a value, only keys
   2. Both store only values with no associated keys
   3. A hash map stores key-value pairs, while a set stores only unique values
   4. A set preserves insertion order by default, but a hash map does not

   Explanation: Hash maps maintain associations between keys and values, while sets focus solely on the uniqueness of values. Both do not omit keys altogether, so 'Both store only values' is incorrect. Standard sets do not necessarily guarantee insertion order, and neither do hash maps, so 'A set preserves insertion order' is wrong. Hash maps can check for values by traversing, but they are optimized for key lookups; the statement 'cannot check the existence of a value' is misleading.

5. Handling Collisions

   When two distinct keys produce the same hash index in a hash map (a collision), what is a standard way for the hash map to resolve this?

   1. By using a linked list or chain at that index
   2. By throwing an exception for duplicate hashes
   3. By overwriting the existing value at that index
   4. By ignoring one of the entries entirely

   Explanation: The typical method for handling collisions in hash maps is to link multiple key-value pairs at the same index, often using a linked list or chain. Simply ignoring an entry would result in data loss, which is not acceptable. Overwriting would also cause loss of one key's data. Most implementations do not throw exceptions for collisions, as collisions are a normal part of hash map operations.