In this lesson, you will learn how to decide between using a set or a dictionary based on the specific hashing requirements of your algorithm.
Choosing the Right Tool
While both set and dict rely on hash tables to provide O(1) average time complexity for lookups, they serve different purposes. The fundamental rule is: Use a set if you only care about membership, and use a dict if you need to associate data with a key.
When to use a set
A set is optimized for answering the question, "Have I seen this before?" Because sets only store the keys (the hashable elements), they are more memory-efficient than dictionaries when you don't need to store associated values.
Consider a task where you need to filter duplicates from a stream of incoming data:
def filter_duplicates(items):
seen = set() # Optimized for O(1) membership checks
unique_items = []
for item in items:
if item not in seen:
unique_items.append(item)
seen.add(item)
return unique_items
When to use a dict
A dict is essential when you need to map a key to a value. Internally, a dictionary maintains a more complex structure to store both the hash of the key and its corresponding value. If you find yourself writing code where you look up a key simply to retrieve an associated piece of data, a dictionary is your required structure.
Efficiency and Hashability
Remember that both structures impose the same constraint: keys must be hashable. If your data is mutable (like a list), you cannot use it as a key. If you are dealing with a large collection of items where you need to perform frequent lookups, check the hashing cost. If your objects have custom __hash__ methods, ensure they are efficient, as complex calculations will negate the O(1) speed benefits of these structures.
When choosing between them, ask yourself: "Do I need to retrieve a value attached to this key, or am I just checking for existence?" If it's the former, use a dict. If it's the latter, use a set to save memory and clarify your intent.
Key Takeaway: Choose set for high-speed membership testing and dict when you must map unique keys to associated values.