# Dictionaries: Hash Tables in Practice — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/h-dict

> Understand how dict works and the hash/equality contract.

## Fast lookups by key

A **`dict`** is a **hash table**: each key's `hash()` chooses a slot, so lookup, insertion and deletion are **O(1) on average**. CPython uses **open addressing** with a compact layout: a sparse index table pointing into a dense array of entries, which saves memory and preserves **insertion order**, guaranteed by the language since Python 3.7. Tables resize when about two-thirds full, so inserts are amortised O(1). Worst-case operations are O(n) if many keys collide, which is why string hashing is **randomised per process** (hash randomisation) to resist collision attacks. Keys must be **hashable**: an object's hash must not change during its lifetime, and objects that compare **equal must have equal hashes**. When you define `__eq__` on a class, also define `__hash__` (or make it unhashable), and never mutate a key in a way that changes its hash. Useful operations: `get(key, default)`, `setdefault`, `pop`, `items()` views, dict comprehensions, merging with `|` and `|=` (Python 3.9+), and `dict.fromkeys`. Dict views (`keys()`, `items()`) are live and support set operations.

## A compact hash table

A sparse index array points into a dense, insertion-ordered entries array.

![A narrow column of index slots, some empty, with arrows pointing into a compact table of rows containing hash, key and value columns in insertion order.](assets/figures/data-structures-python/section-3-map.svg) — Figure 3.1 — How CPython dicts store entries.

## Counting, grouping and the hash contract

Dicts as indexes, and a class that is safe to use as a key.

```python
orders = [
    {"id": "o1", "city": "Pune", "total": 1200},
    {"id": "o2", "city": "Delhi", "total": 300},
    {"id": "o3", "city": "Pune", "total": 800},
]

by_id = {o["id"]: o for o in orders}           # index for O(1) lookups
print(by_id["o3"]["total"])                     # 800

revenue = {}
for o in orders:
    revenue[o["city"]] = revenue.get(o["city"], 0) + o["total"]
print(revenue)                                  # {'Pune': 2000, 'Delhi': 300} (insertion order)

defaults = {"currency": "INR", "gst": 18}
overrides = {"gst": 5}
print(defaults | overrides)                     # {'currency': 'INR', 'gst': 5}

class Sku:
    def __init__(self, code: str):
        self.code = code.upper()
    def __eq__(self, other):
        return isinstance(other, Sku) and self.code == other.code
    def __hash__(self):                         # equal objects must hash equally
        return hash(self.code)

stock = {Sku("pen"): 120}
print(stock[Sku("PEN")])                        # 120: equal key, same hash

print(revenue.keys() & {"Pune", "Mumbai"})      # {'Pune'}: views support set operations
```

## Do not mutate keys

If a key object's hash changes after insertion, the dict looks in the wrong slot and the entry becomes unreachable. Use immutable keys (strings, numbers, tuples, frozen dataclasses).

**Quiz:** Since which Python version is dict insertion order guaranteed by the language?

- [x] 3.7
- [ ] 2.7
- [ ] 3.5
- [ ] 3.12

*Answer:* 3.7. It was a CPython implementation detail in 3.6 and became a language guarantee in 3.7.