rag/knowledge_base/hash_set_vs_hash_map.txt

TOPIC: Hash Set vs Hash Map

DEFINITION: 
A hash set and a hash map are two fundamental data structures used for storing and retrieving data efficiently. The primary difference between them lies in their purpose: a hash set is used to store unique elements, whereas a hash map stores key-value pairs. This distinction makes them suitable for solving different problems, such as keeping track of unique items versus storing and retrieving data by a specific key.

TIME_COMPLEXITY: 
The average time complexity for both hash sets and hash maps is O(1) for basic operations like insertion, deletion, and search, assuming a good hash function is used. However, in the worst-case scenario, it can degrade to O(n) if there are many collisions.

SPACE_COMPLEXITY: 
The space complexity for both data structures is O(n), where n is the number of elements stored, as each element requires a certain amount of space to store.

USE_WHEN: 
Use a hash set when you need to store a collection of unique items and quickly check for membership, such as in a spell checker to store unique words. Use a hash map when you need to associate each item with additional data, such as in a phonebook to store names and phone numbers.

AVOID_WHEN: 
Avoid using a hash set when you need to store key-value pairs or when order matters, as hash sets do not maintain any particular order and do not support key-value pairs. Instead, use a hash map or other data structures like a tree map or a linked hash map.

EXAMPLE: 
Consider adding unique names to a hash set: 
  - Start with an empty set: []
  - Add "John": ["John"]
  - Add "Alice": ["John", "Alice"]
  - Add "John" again: still ["John", "Alice"] because duplicates are ignored
  - Check if "Bob" is in the set: no, because it was never added 
  Result: ["John", "Alice"] 

REAL_WORLD_ANALOGY: 
A hash set is like a list of unique attendees at a party, where each name is recorded only once. A hash map is like a phonebook where each name is associated with a phone number, allowing you to look up the number by the name.

SOURCE_NOTE: 
Concepts referenced from general knowledge of data structures and algorithms.