hash-vs-tree

name	hash-vs-tree
description	Choose between hash tables and tree structures for lookups, counting, and grouping. Use when deciding between O(1) hash operations and O(log n) ordered operations.
topic	Data Structure Choice
token_cost	90
related	["sorting-choice","two-pointers","binary-search"]
keywords	["lookup","dictionary","dict","set","hash","hashtable","map","frequency","count","unique","duplicate","ordered","sorted","tree","counter","defaultdict","collections"]

When to use

Use dict/set (hash table, O(1) avg lookup) for: membership testing, frequency counting, deduplication, grouping by key.

Rules

• Use collections.Counter for frequency counts, defaultdict(list) for grouping
• When you need ordered keys or range queries, use sorted containers or bisect on a sorted list
• For "find if X exists" or "count occurrences," ALWAYS reach for a set or dict first
• NEVER scan a list repeatedly when a set/dict would work
• If the problem involves pairs summing to a target, use a set to check complements in O(n) instead of O(n^2) nested loops

Complexity

Hash table: O(1) avg lookup. Sorted containers: O(log n) lookup.

Example

"Two sum" → store complements in a set: for x in nums: if target - x in seen: return True; seen.add(x). O(n) vs O(n²) nested loops.