Hash Maps and Sets in Game State and Inventory Management Quiz

Test your knowledge on how hash maps and hash sets are used for fast entity lookups, inventory frequency counts, efficient collision deduplication, and understanding time-space trade-offs in gameplay state management. This quiz covers core concepts and practical scenarios for developers and enthusiasts interested in game systems optimization.

1. O(1) Entity Lookup

   Which data structure is most suitable for O(1) lookup of a player's position in a large world state?

   1. Hash map
   2. Array list
   3. Balanced tree
   4. Linked queue

   Explanation: Hash maps allow for constant time O(1) access by key, making them optimal for frequent, direct lookups such as a player's position using a unique identifier. Array lists require searching through elements, making lookups slower. Linked queues are designed for sequential access, not instant lookup. Balanced trees offer O(log n) time, which is slower than hash maps for this case.

2. Inventory Frequency Counts

   How can you efficiently count how many apples a player has in their inventory?

   1. Keep a running total in a queue
   2. Store each apple as a separate entry in an array
   3. Use a hash map mapping item names to counts
   4. Save all items in a single string

   Explanation: A hash map lets you map each item name, like 'apple', to its count, making frequency lookups efficient. Storing each apple as a separate array entry wastes space and requires linear searches for counts. Saving items in a single string is inefficient for updates or lookups. A queue is not designed for tallying or indexed access.

3. Deduplicating Collision Events

   In a physics simulation, what data structure best helps prevent duplicate reporting of collisions between the same pair of objects?

   1. Priority queue
   2. Sorted array
   3. Stack of events
   4. Hash set of collision pairs

   Explanation: A hash set is ideal for storing unique tuples of object pairs, ensuring collisions are not reported multiple times. Stacks are last-in-first-out and do not check for duplicates. Priority queues are for ordered processing, not for uniqueness. Sorted arrays can check for duplicates but at slower performance than hash sets.

4. O(1) Cooldown Tracking

   When tracking skill cooldowns per player for instant checks, which structure is most time efficient?

   1. Doubly linked list
   2. Heap
   3. Randomized queue
   4. Hash map from skill to timestamp

   Explanation: A hash map allows associating each skill with its last used time for quick O(1) lookups. Heaps are for managing priority, not direct access. Randomized queues do not provide quick key access. Doubly linked lists are for sequence traversal, not indexed lookups.

5. Set Membership for Power-Ups

   Which structure lets you rapidly check if a player has collected a specific power-up?

   1. Circular buffer
   2. Binary heap
   3. Hash set of power-ups collected
   4. Fixed-size queue

   Explanation: A hash set quickly tests for membership, so you can check if a power-up is present in constant time. Fixed-size queues and circular buffers are optimized for insertions and removals, not lookups. Binary heaps are used for maintaining order or priorities, not for quick membership tests.

6. Deduplicating Event Notifications

   How might a hash set help manage repeated event notifications sent to players in a single game tick?

   1. By storing already-notified event IDs
   2. By queuing up all events
   3. By mapping events to timestamps
   4. By sorting event times

   Explanation: A hash set can track which player-event pairs have already been notified in the current tick, avoiding duplicates. Queuing all events doesn't prevent repeats. Sorting by time doesn't filter unique notifications. Mapping to timestamps helps manage old events, not instant deduplication.

7. Time vs Space: Collision Tracking

   What is the primary time vs space trade-off when using a hash set to remember all recent collision events in fast-paced gameplay?

   1. Faster retrieval but only for a small number of events
   2. Slower event processing with minimal memory
   3. Faster deduplication at the cost of higher memory usage
   4. No trade-off; hash sets are universally optimal

   Explanation: Hash sets allow very fast duplicate checks but require storing all processed events, increasing memory needs. Using less memory by not storing events would force slower checks for duplicates. The statement about retrieval speed ignores hash set scalability. Claiming no trade-off is inaccurate, as every approach has some cost.

8. Unique Entity Identification

   In a multiplayer game, how can a hash map help associate each entity with its unique attributes?

   1. By storing only a single attribute per entity
   2. By appending all attributes into one long string
   3. By using entity IDs as keys mapping to attribute sets
   4. By placing attributes in a fixed queue

   Explanation: Hash maps efficiently relate each unique entity ID to all its attributes. Concatenating attributes in one string makes updates and retrievals inefficient. Storing only one attribute per entity is severely limiting. Fixed queues are designed for ordered processing, not key-value pairs.

9. Inventory Deduplication

   Why is a hash set suitable for representing a player's collection of unique badges in a game?

   1. It saves badge images directly
   2. It preserves the order badges were earned
   3. It allows fast sorted retrieval
   4. It ensures each badge is stored only once

   Explanation: A hash set only stores unique items, preventing duplicates, which is essential for badge lists. Order is not guaranteed in a set, so it can't preserve earning sequences. Fast sorted retrieval isn’t a property of a hash set. Hash sets store references, not images themselves.

10. Hash Collision Handling

    What happens when two distinct inventory items hash to the same index in a hash map used for item counts?

    1. Both items are deleted
    2. One item overwrites the other
    3. The hash map resolves the collision using chaining or probing
    4. Neither can be retrieved again

    Explanation: Hash maps use internal strategies like chaining (linked lists or lists at a slot) or probing (finding another spot) to resolve collisions. Overwriting or deleting both items would make the map unreliable. Proper implementation ensures both can still be found when needed.

11. Cooldown Key Structure

    For tracking cooldowns of multiple abilities for multiple characters, what is a suitable hash map key?

    1. A tuple of character and ability ID
    2. A single random integer
    3. No key needed; use an array
    4. An ability name string

    Explanation: A tuple or composite key lets you map each character-ability pair to a cooldown value, supporting many characters and abilities easily. Using just the ability name as a key wouldn't distinguish between characters. Random integers as keys are not meaningful. Arrays are not efficient for this key-based lookup.

12. Counting Loot Drop Frequency

    If you want to track how often each item drops in a randomized loot system, which approach is best?

    1. Record loot only if the count is above ten
    2. List all drops in chronological order
    3. Use a hash map from item names to drop counts
    4. Assign each item a fixed color

    Explanation: Hash maps give counts per item instantly, providing a clear frequency distribution. Chronological lists require manually tallying counts each time. Assigning colors is not related to tracking drops. Only recording drops sometimes loses valuable data and trends.

13. Removing Expired Events

    How should you efficiently remove outdated collision events from a hash set tracking recent events?

    1. Rely on automatic garbage collection to remove just old entries
    2. Ignore old events and let the set grow forever
    3. Periodically check timestamps and delete old entries
    4. Replace the entire set each frame

    Explanation: Checking timestamps and removing ovsolete entries maintains the set's size and relevance. Replacing the set is inefficient. Letting the set grow wastes memory. Garbage collection manages memory but cannot distinguish expiration within application logic.

14. Quick Entity Activity Checks

    What is the benefit of keeping active entity IDs in a hash set during real-time gameplay updates?

    1. Ensures entities remain in spawn order
    2. Automatically sorts entities by activity time
    3. Fast O(1) checks to see if an entity is active
    4. Prevents any entity from deactivating

    Explanation: Hash sets allow for instant membership queries, so the system quickly checks if an entity is currently active. Sets do not maintain order at all, so spawn order isn’t kept. Sorting is not provided by sets. They have no effect on deactivation logic.

15. Incorrect Use of Hash for Inventory

    Which use of a hash map is inappropriate for tracking a player's inventory?

    1. Mapping item types to rarity tiers
    2. Mapping item IDs to attributes
    3. Mapping item images to types
    4. Mapping item names to stack counts

    Explanation: Using images as keys is inefficient, as images are large objects and can lead to poor performance. Mapping names to counts, IDs to attributes, or types to rarity tiers all serve practical tracking purposes. Choosing data-heavy objects as keys is a suboptimal approach.

16. Space Cost of Hash Structures

    What is a potential disadvantage of using hash maps and sets for gameplay state?

    1. They use more memory than simple lists
    2. They always make the program slower
    3. They store fewer items than arrays
    4. They prevent data from being updated

    Explanation: Hash structures often allocate extra space for fast lookups and collision handling, increasing memory usage compared to basic lists. They are generally much faster for lookups, so slowing down the program is not common. They can store as many items as needed, not fewer than arrays. Hash structures fully support updates.

17. Hash Set for Fast Pickup Checks

    Why might a hash set be chosen for checking if a player already picked up a quest item?

    1. It guarantees the oldest item is removed first
    2. It saves more data than any other structure
    3. It allows for automatic sorting of item pickups
    4. You can instantly check for presence without searching

    Explanation: The hash set lets you test for an item’s existence in O(1) time, making it highly efficient for presence checks. Sorting is not a feature of hash sets. Oldest-first (FIFO) removal is a characteristic of queues, not sets. Hash sets do not store more data than all other structures.