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.