Hashing and Hash Tables Questions

Direct answer

Extending an LRU (least-recently-used) cache with per-entry time-to-live (TTL, a lifespan after which an entry is no longer considered valid) means treating expiry and eviction as two independent mechanisms layered on the same structure: TTL decides whether an entry is even valid to serve at all, LRU decides who gets removed when the cache is full, regardless of whether that entry's TTL has expired yet. Safe concurrent access comes from sharding the cache into N independently locked pieces by key hash, so unrelated keys never contend for the same lock, rather than one global lock serializing every request. The one genuine race to guard against is a reader and an expiry-driven cleanup touching the same key at the same instant, which a single lock per shard around each operation's full check-then-mutate sequence eliminates by construction.

Structured elaboration

Data structures. Per shard: an ordered map (a doubly linked list plus a hash index, or collections.OrderedDict in Python) storing key -> (value, expires_at). get first checks expires_at against the current time; if expired, the entry is deleted and treated as a miss, never served stale. If still valid, it is moved to the most-recently-used end, same as a plain LRU. put inserts or updates the entry with a fresh expires_at, then evicts from the least-recently-used end while the shard is over capacity, exactly as a TTL-unaware LRU would, an unexpired entry can still be evicted early purely for space if it is cold enough.

Locking and sharding to minimize contention. A single lock around the whole cache serializes every request regardless of which key it touches, the same contention problem as a naive shared counter. The fix is the same: partition keys across N shards by hash(key) % N, each with its own lock, so two threads touching different shards never block each other; within a shard, the critical section (a dict lookup, a move, maybe an eviction) is small enough that a simple mutex around the whole operation is both correct and fast, a lock-free linked-list-based LRU is real engineering effort that rarely pays for itself compared to just adding more, smaller shards.

Eviction rules on TTL expiry. Two independent triggers remove an entry: lazily, on access, if its expires_at has passed; and capacity-driven, on put, evicting the least-recently-used entry regardless of that entry's own TTL state once the shard is full. A background sweep thread that proactively scans for and removes expired-but-never-accessed entries is an optional memory-hygiene addition, not a correctness requirement, lazy expiry alone already guarantees an expired entry is never served, it just might sit unreclaimed in memory until LRU pressure or a sweep removes it.

Race conditions between expiry and access. Because the expiry check and the touch-or-evict mutation both happen inside the same lock acquisition as one atomic operation, no other thread on that shard can observe a half-expired state in between. Two remaining subtleties matter: use a monotonic clock (one that only ever moves forward, unaffected by wall-clock adjustments) for expiry comparisons, since a wall-clock adjustment (an NTP correction, a daylight-saving shift) can jump time backward and silently corrupt TTL math; and treat the exact boundary consistently, an access at precisely expires_at should be treated as expired, not as a coin flip.

Code

import threading, time
from collections import OrderedDict

class TTLLRUCache:
    def __init__(self, capacity, default_ttl):
        self._capacity = capacity
        self._default_ttl = default_ttl
        self._store = OrderedDict()  # key -> (value, expires_at)
        self._lock = threading.Lock()

    def get(self, key, now=None):
        now = time.monotonic() if now is None else now
        with self._lock:
            entry = self._store.get(key)
            if entry is None:
                return None
            value, expires_at = entry
            if now >= expires_at:
                del self._store[key]
                return None
            self._store.move_to_end(key)
            return value

    def put(self, key, value, ttl=None, now=None):
        now = time.monotonic() if now is None else now
        ttl = self._default_ttl if ttl is None else ttl
        with self._lock:
            if key in self._store:
                del self._store[key]
            self._store[key] = (value, now + ttl)
            self._store.move_to_end(key)
            while len(self._store) > self._capacity:
                self._store.popitem(last=False)


class ShardedTTLLRUCache:
    def __init__(self, shard_count, capacity_per_shard, default_ttl):
        self._shards = [TTLLRUCache(capacity_per_shard, default_ttl) for _ in range(shard_count)]
        self._shard_count = shard_count

    def _shard_for(self, key):
        return self._shards[hash(key) % self._shard_count]

    def get(self, key, now=None):
        return self._shard_for(key).get(key, now=now)

    def put(self, key, value, ttl=None, now=None):
        self._shard_for(key).put(key, value, ttl=ttl, now=now)


if __name__ == "__main__":
    # basic TTL expiry
    cache = TTLLRUCache(capacity=2, default_ttl=10)
    cache.put("a", 1, now=0)
    print("get a at t=5 (not expired) ->", cache.get("a", now=5))
    print("get a at t=15 (expired, ttl=10) ->", cache.get("a", now=15))

    # LRU eviction independent of TTL (long ttl so eviction is purely LRU-driven)
    cache2 = TTLLRUCache(capacity=2, default_ttl=100)
    cache2.put("x", 100, now=0)
    cache2.put("y", 200, now=1)
    cache2.get("x", now=2)          # touch x -> y becomes LRU
    cache2.put("z", 300, now=3)     # evicts y (LRU), not due to TTL (ttl=100, still valid)
    print("y evicted by LRU (not TTL) ->", cache2.get("y", now=4) is None)
    print("x survived ->", cache2.get("x", now=4) == 100)

    # concurrency check: 16 threads, 200 put-then-get round trips each, shared 8-shard cache
    shared = ShardedTTLLRUCache(shard_count=8, capacity_per_shard=64, default_ttl=1000)
    errors = []

    def worker(tid):
        for i in range(200):
            key = f"t{tid}-{i}"
            shared.put(key, (tid, i), now=0)
            val = shared.get(key, now=0)
            if val != (tid, i):
                errors.append((key, val))

    threads = [threading.Thread(target=worker, args=(t,)) for t in range(16)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()
    print("concurrent put/get across 16 threads, errors ->", len(errors))

    # exact boundary: an access at precisely expires_at counts as expired
    cache3 = TTLLRUCache(capacity=2, default_ttl=1.0)
    cache3.put("k", 42, now=0.0)
    print("exactly-at-expiry (t=1.0) counts as expired ->", cache3.get("k", now=1.0) is None)

Output (executed as shown, using an injected clock so TTL behavior is deterministic and reproducible):

get a at t=5 (not expired) -> 1
get a at t=15 (expired, ttl=10) -> None
y evicted by LRU (not TTL) -> True
x survived -> True
concurrent put/get across 16 threads, errors -> 0
exactly-at-expiry (t=1.0) counts as expired -> True

The concurrency check ran 16 threads, each performing 200 put-then-get round trips against a shared 8-shard cache, and confirmed every value was read back exactly as written with zero errors, evidence the sharded locking is actually safe under real concurrent access, not just single-threaded correctness.

Trade-offs and pitfalls

• Lazy-only expiry can leave cold, expired entries resident indefinitely if the cache has generous capacity and that key is never looked up again; add a background sweep if bounding memory tightly matters more than the extra CPU cost of scanning.
• Shard count is a real tuning knob, not a fixed choice. Too few shards under-spreads lock contention; too many wastes memory on mostly-empty per-shard structures and adds bookkeeping overhead.
• Distributed sharding is the same idea one layer up. The identical hash-the-key-to-a-shard principle extends from in-process locks to independent nodes in a distributed cache: shard by consistent hashing across nodes so the cache's total capacity and throughput scale past one machine, with a routing layer (client-side or proxy-side) sending each request to the node that owns its key's shard.
• Persistence across restarts should stay proportionate to what TTL data actually needs. Since every entry already has a bounded lifespan, a periodic best-effort snapshot to disk or an external store, reloaded at startup and immediately filtered to discard anything whose expires_at has already passed relative to current wall-clock time, is sufficient; treating this like a database's durability guarantee (distributed consensus, write-ahead logs) is usually over-engineering for data that was always meant to expire.
• A common wrong turn: using wall-clock time (time.time()) instead of a monotonic clock for TTL comparisons. It works in every normal test run and fails exactly once, silently, during a real clock adjustment in production, which is precisely why it is easy to ship and hard to catch without deliberately testing for it.

Direct answer

Compute a stable identifier (a natural event id, or a hash of the event's content if none exists) for each incoming event, and check it against a set of identifiers already seen within the dedup window before processing; present means drop it as a duplicate, absent means process it and record the identifier. An exact hash set gives zero false positives but grows linearly with the number of distinct events currently tracked, which becomes the memory bottleneck at high volume; a probabilistic structure like a Bloom filter trades a small, tunable false-positive rate for an order-of-magnitude smaller footprint, usually the right trade at streaming scale. Bounding the structure to a fixed time window, for instance the last 24 hours, keeps memory from growing without limit.

Exact approach: hash set

Maintain a hash set of event identifiers already processed. On each new event, look it up: present means duplicate, absent means new (insert, then process). This is exact, no false positives and no false negatives, but memory scales directly with how many distinct events are currently tracked, which is the first thing to break at high volume.

Memory considerations

A language-level hash set rarely stores just the raw identifier bytes: object headers, pointers, and the underlying hash table's own load-factor slack add real per-entry overhead on top of the identifier itself. Because that overhead is roughly constant per entry, total memory scales linearly and directly with how many distinct events are being remembered at once, which is exactly the quantity that grows fastest in a high-volume feed.

Approximate alternative: Bloom filters

A Bloom filter trades a small, controllable false-positive rate for dramatically less memory: it answers "definitely not seen" with certainty, or "possibly seen" with a bounded error rate, and it never produces a false negative (a genuinely new event is never mistakenly dropped as a duplicate). Given a target false-positive probability $p$ and expected item count $n$, the optimal bit-array size and hash-function count are:

$m = -\frac{n \ln p}{(\ln 2)^2} \qquad k = \frac{m}{n}\ln 2$

Time-bounded (e.g. 24-hour) dedup

Tracking duplicates forever is usually the wrong goal for a streaming feed: you rarely need to know an event duplicates something from months ago, and unbounded tracking only makes the memory problem worse over time. Common ways to bound the window:

• Rotating filters: keep several Bloom filters (or hash sets), one per time bucket (for example hourly), check an incoming event against the last 24 buckets, insert it into the CURRENT bucket, and drop the oldest bucket as a new one opens. This gives an approximate sliding window at the cost of checking several filters per lookup.
• TTL-backed store: with a real key-value store (Redis and similar), attach a 24-hour time-to-live to each recorded event id and let the store expire entries automatically. Simpler operationally, but back to exact-set memory costs unless the store itself offers a probabilistic structure.
• Counting/decay variants: a Counting Bloom Filter supports removal (increment counters instead of flipping bits, decrement or expire on a per-slot timer), letting entries actually age out of the SAME structure rather than rotating separate ones, at the cost of a bit more memory per slot.

Worked example

import hashlib
import math
import random


class BloomFilter:
    def __init__(self, n_expected, target_fp_rate):
        self.n_expected = n_expected
        self.m = math.ceil(-(n_expected * math.log(target_fp_rate)) / (math.log(2) ** 2))
        self.k = max(1, round((self.m / n_expected) * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item):
        h = hashlib.sha256(item.encode("utf-8")).digest()
        h1 = int.from_bytes(h[:8], "big")
        h2 = int.from_bytes(h[8:16], "big") | 1
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        for pos in self._positions(item):
            self.bits[pos // 8] |= (1 << (pos % 8))

    def __contains__(self, item):
        return all(self.bits[pos // 8] & (1 << (pos % 8)) for pos in self._positions(item))


if __name__ == "__main__":
    random.seed(123)
    N_EVENTS = 200_000
    TARGET_FP = 0.01

    bf = BloomFilter(N_EVENTS, TARGET_FP)
    print(f"n={N_EVENTS} target_fp={TARGET_FP} -> m={bf.m} bits ({bf.m/8/1024:.1f} KiB), k={bf.k}")

    seen_ids = [f"evt-{i}-{random.randint(0, 1_000_000)}" for i in range(N_EVENTS)]
    for eid in seen_ids:
        bf.add(eid)

    false_negatives = sum(1 for eid in seen_ids if eid not in bf)
    print("false negatives among inserted ids (must be 0):", false_negatives)

    unseen_ids = [f"unseen-{i}-{random.randint(0, 1_000_000)}" for i in range(100_000)]
    false_positives = sum(1 for eid in unseen_ids if eid in bf)
    print(f"empirical false-positive rate over {len(unseen_ids)} unseen ids: "
          f"{false_positives/len(unseen_ids):.4f} (predicted ~{TARGET_FP})")

    exact_set_bytes_estimate = N_EVENTS * 64
    print(f"bloom filter bytes: {len(bf.bits)}  vs  exact set (rough estimate): {exact_set_bytes_estimate}")

Output:

n=200000 target_fp=0.01 -> m=1917012 bits (234.0 KiB), k=7
false negatives among inserted ids (must be 0): 0
empirical false-positive rate over 100000 unseen ids: 0.0102 (predicted ~0.01)
bloom filter bytes: 239627  vs  exact set (rough estimate): 12800000

Sized for 200,000 tracked events at a 1% target, the formula calls for about 234 KiB and 7 hash functions; the empirical false-positive rate measured against 100,000 never-inserted ids comes out to 1.02%, matching the 1% target closely, and every one of the 200,000 actually-inserted ids is correctly recognized (zero false negatives, which is the guarantee that must never break). The Bloom filter's roughly 234 KiB footprint against a rough per-entry estimate of about 12.8 MB for an equivalent exact set is a roughly 53x reduction for this workload, which is the trade being made: about 1% of genuinely new events get incorrectly treated as duplicates and dropped.

Trade-offs and pitfalls

• A Bloom filter's false positives mean some genuinely new events get silently dropped; fine for many analytics or logging use cases, but the wrong choice if losing even a small fraction of new legitimate events is unacceptable (billing events, for instance), where an exact structure or a verification step on filter hits is warranted instead.
• Sizing a Bloom filter for the wrong n (underestimating peak event volume in the window) silently degrades the false-positive rate well past what was designed for, since m and k were chosen assuming a specific n; monitor actual load and re-provision rather than assuming a static estimate holds forever.
• Rotating multiple time-bucketed filters multiplies lookups per event (checking every open bucket); a Counting Bloom Filter with per-slot decay avoids that at the cost of a bit more memory per slot.

Direct answer

Persist the KEYS and VALUES themselves in a versioned, explicit binary or protobuf format, never
the runtime's raw hash codes: hash codes are only guaranteed stable within a single process's
lifetime and can differ across restarts, versions, or language runtimes, so a persisted hash
code cannot be trusted to still mean the same thing on reload. On startup, rebuild the in-memory
hash map from the persisted keys/values using whatever the CURRENT process's hashing is, and
guard the file itself with an explicit format version so schema or key-class changes fail loudly
instead of silently misreading old bytes.

Structured elaboration

Why you cannot persist raw hash codes. Many runtimes deliberately randomize string hashing
per process (for example, Python randomizes hash() for strings via a per-process seed unless
PYTHONHASHSEED is pinned, specifically to prevent hash-flooding attacks). That means the exact
same key can hash to two different values in two different process runs. Persisting a raw hash
code and later comparing it to a freshly computed hash after a restart is therefore unreliable
by design, not just as an edge case.

Serialization format choices.

• Binary (custom framing): smallest size, fastest to parse, but requires you to hand-write and
  version the byte layout yourself.
• Protocol Buffers (protobuf): a schema-defined binary format; the schema itself gives you
  built-in field-level forward/backward compatibility (new optional fields, unknown fields
  ignored by older readers) at the cost of an external schema dependency and slightly larger
  payloads than hand-rolled binary.
• Memory-mapped structures: the file's on-disk layout matches the in-memory layout directly, so
  startup can be extremely fast (map the file, no parsing pass), at the cost of being far more
  sensitive to any layout change (struct field order, padding, endianness) and generally the
  least portable of the three across different language runtimes.

Handling hash-seed changes. Never store a key's hash as its identity in the file; store the
key's actual content (the string, the tuple of fields, whatever it is), and let the CURRENT
process re-derive the hash when it rebuilds the in-memory map. This makes hash-seed differences
across restarts irrelevant, since the persisted file never depended on any particular seed to
begin with.

Handling changes in key classes. If the key's own structure changes between versions (a
field added, removed, or its type changed), a naive reload can silently misinterpret old bytes as
the new shape. Tag every persisted file with an explicit format_version integer written first;
on load, check it and either apply a migration step or refuse to load with a clear error, rather
than guessing.

Forward/backward compatibility and fast startup. Forward compatibility (an older reader
encountering a newer file) is handled by including only fields the old reader understands and
ignoring unknown ones (schema-based formats like protobuf do this natively; hand-rolled binary
needs an explicit "skip unknown field" convention). Backward compatibility (a newer reader
encountering an older file) is handled by the version check triggering an explicit migration path
(fill in a sensible default for a field that did not exist yet) instead of crashing or silently
corrupting data. Fast startup generally trades against how much validation/migration work happens
at load: memory-mapped formats are fastest but least flexible; versioned binary or protobuf with
an explicit migration step is slower but safer across version changes.

Worked example

import subprocess, sys, os, hashlib, struct, json

probe = 'print(hash("order-42"))'
env0 = dict(os.environ, PYTHONHASHSEED="0")
env1 = dict(os.environ, PYTHONHASHSEED="1")
out0 = subprocess.run([sys.executable, "-c", probe], env=env0, capture_output=True, text=True).stdout
out1 = subprocess.run([sys.executable, "-c", probe], env=env1, capture_output=True, text=True).stdout
out0_again = subprocess.run([sys.executable, "-c", probe], env=env0, capture_output=True, text=True).stdout
print("seed=0:", out0.strip(), "| seed=1:", out1.strip(), "| seed=0 again:", out0_again.strip())
print("seed=0 reproducible across runs:", out0 == out0_again)

# SHA-256 is a content fingerprint: run it under both seeds via subprocess and compare
sha_probe = 'import hashlib; print(hashlib.sha256("order-42".encode()).hexdigest())'
sha0 = subprocess.run([sys.executable, "-c", sha_probe], env=env0, capture_output=True, text=True).stdout.strip()
sha1 = subprocess.run([sys.executable, "-c", sha_probe], env=env1, capture_output=True, text=True).stdout.strip()
print("sha256 under seed=0:", sha0, "| under seed=1:", sha1, "| identical:", sha0 == sha1)

# Minimal versioned binary round-trip
def write_versioned(path, version, obj):
    payload = json.dumps(obj).encode("utf-8")
    with open(path, "wb") as f:
        f.write(struct.pack(">I", version))
        f.write(struct.pack(">I", len(payload)))
        f.write(payload)

def read_versioned(path, expected_version):
    with open(path, "rb") as f:
        version = struct.unpack(">I", f.read(4))[0]
        if version != expected_version:
            raise ValueError(f"unrecognized format version {version}, expected {expected_version}")
        length = struct.unpack(">I", f.read(4))[0]
        return json.loads(f.read(length))

original = {"user-1": 100, "user-2": 200, "user-3": 300}
write_versioned("/tmp/persisted_map.bin", 1, original)
reloaded = read_versioned("/tmp/persisted_map.bin", expected_version=1)
print("round-trip matches:", reloaded == original)
try:
    read_versioned("/tmp/persisted_map.bin", expected_version=2)
except ValueError as e:
    print("correctly raised on version mismatch:", e)

Running the SAME key "order-42" through hash() in two separate Python processes, one with
PYTHONHASHSEED=0 and one with PYTHONHASHSEED=1, prints two different values
(-5269630982118381820 and -8350994900029329935); re-running the seed=0 process again
reproduces the exact same value, confirming the difference genuinely comes from the seed, not
run-to-run randomness. Hashing the same key with SHA-256 instead (a content fingerprint,
independent of the process's hash seed), run via the same two subprocess environments, gives the
IDENTICAL digest under both seeds, which is the concrete evidence for why a stable,
content-derived identifier belongs in a persisted file and a raw hash() code does not. A minimal
versioned binary round-trip (a 4-byte version header, a 4-byte length, then a canonical JSON
payload) writing {"user-1": 100, "user-2": 200, "user-3": 300} to disk and reading it back
reproduces the exact original map, and deliberately checking for an unrecognized version number
raises an explicit error rather than attempting to parse mismatched bytes.

Trade-offs and pitfalls

• The most common real bug is treating a language's built-in hash code as if it were a stable,
  portable identifier. It usually is not, and the failure mode (silent lookup misses after a
  restart) is easy to miss in testing if the test process happens to reuse the same seed the data
  was written under.
• Skipping the format-version header to save a few bytes is a false economy: without it, a
  schema change becomes a silent data-corruption risk instead of a clean, explicit failure or
  migration.
• Memory-mapped formats are the fastest to load but the least forgiving of change; reserve
  them for genuinely hot-path startup requirements, and prefer protobuf or versioned binary
  elsewhere for the compatibility guarantees.
• Cross-language reload (a map written by one runtime, read by another) additionally requires
  the field types and encoding (integer width, string encoding, float representation) to be fully
  specified in the format, not left to each runtime's default serialization behavior.

Direct answer

Maintain a hash map from character to its running count, plus a queue that holds candidates for
"first non-repeating" in the order they first appeared. On each next(char), update the count
and push the character onto the queue if it is new; then pop from the front of the queue while
its count is greater than 1, since a repeated character can never again be the answer. Whatever
remains at the front (or None if the queue is empty) is the current answer.

Structured elaboration

Why a hash map alone is not enough. A hash map of counts tells you WHETHER a character
repeats, but not which non-repeating character came FIRST. You need an ordering structure
alongside it.

Why a plain list of "seen order" is not enough either. If you kept every character ever
seen in a list and re-scanned it on every query, you would pay O(k) per query, where k grows
with the stream. The insight that makes this online and efficient: once a character's count
exceeds 1, it can never become the answer again, so it should be permanently removed from
consideration, not re-scanned every time.

The deque of candidates. A deque (double-ended queue) holds characters that MIGHT still be
the first non-repeating one, in first-seen order. On each new character: increment its count in
the hash map, append it to the deque. Then, while the deque's front character has a count
greater than 1, pop it (it is now permanently disqualified). The deque's new front, if any, is
the answer.

Complexity. Each character is appended to the deque exactly once and popped at most once
over the life of the stream, so total deque work across n calls is O(n), making each
next() call amortized O(1), even though a single call can trigger several pops if multiple
front characters were just disqualified. Space is O(distinct characters seen so far), bounded
by the alphabet size for a fixed character set (for example 256 for byte-level input), not by
stream length.

Worked example

from collections import deque, defaultdict

class FirstNonRepeating:
    def __init__(self):
        self.counts = defaultdict(int)
        self.candidates = deque()

    def next(self, char):
        self.counts[char] += 1
        self.candidates.append(char)
        while self.candidates and self.counts[self.candidates[0]] > 1:
            self.candidates.popleft()
        return self.candidates[0] if self.candidates else None

class BruteForceFirstNonRepeating:
    """O(k) per call: re-scans everything seen so far, no deque pruning."""
    def __init__(self):
        self.seen_order = []
        self.counts = defaultdict(int)

    def next(self, char):
        self.counts[char] += 1
        self.seen_order.append(char)
        for c in self.seen_order:
            if self.counts[c] == 1:
                return c
        return None

stream = "aabcbcd"
fnr = FirstNonRepeating()
fast_answers = [fnr.next(ch) for ch in stream]
for ch, ans in zip(stream, fast_answers):
    print(ch, "->", ans)

brute = BruteForceFirstNonRepeating()
brute_answers = [brute.next(ch) for ch in stream]
print("brute-force cross-check:", brute_answers, "| matches:", brute_answers == fast_answers)

Running this against the stream "aabcbcd" prints:

a -> a
a -> None
b -> b
c -> b
b -> c
c -> None
d -> d
brute-force cross-check: ['a', None, 'b', 'b', 'c', None, 'd'] | matches: True

Tracing it by hand confirms each step: after "a" the only character is a (answer a);
after "aa", a now repeats (answer None); after "aab", b is the only non-repeat (answer
b); after "aabc", both b and c are non-repeating but b came first (answer b); after
"aabcb", b now repeats and c is the earliest remaining non-repeat (answer c); after
"aabcbc", c now repeats too and nothing is left (answer None); after "aabcbcd", d is
the only non-repeat (answer d). The independent brute-force cross-check above (re-scanning the
full seen-order list and counts on every call, an O(k) per-call approach) produces the exact
same seven answers on this stream, confirming the deque-pruning optimization changes performance
without changing the result.

Trade-offs and pitfalls

• Do not use a plain hash map without an ordering structure. A map alone can tell you a
  character's count but has no notion of "which non-repeating character came first," since hash
  maps do not guarantee iteration order matches insertion order in every language and even where
  they do (Python's dict since 3.7), scanning the whole map on every query throws away the
  benefit of an online algorithm.
• A common bug is popping from the deque unconditionally instead of only while the front is
  disqualified; that would discard characters that are still valid candidates.
• This generalizes directly to the first non-repeating word problem if you tokenize on word
  boundaries instead of characters: same data structures, same amortized-O(1)-per-token
  argument, as long as the vocabulary fits in memory.
• For a bounded alphabet (fixed character set), the space bound is a true constant, not just
  "bounded by input"; for an open-ended token vocabulary (arbitrary words), space instead grows
  with distinct tokens seen, which matters for a long-running service.

Direct answer

An object is hashable if it has a hash value that never changes during its lifetime and an equality
check consistent with that hash value. Lists and dictionaries are unhashable in Python precisely
because they are mutable: their contents (and therefore what their hash should be) can change after
you've already used them as a key, which would silently corrupt the table.

Structured elaboration

The contract a hash table depends on. A hash table computes hash(key) % capacity once, at
insertion, to choose a bucket, and does the same computation again at lookup time to find that
bucket. If the key's hash value could change in between (because the key itself changed), the second
computation would look in the wrong bucket and the entry would appear to have vanished, this is the
exact failure mode mutability creates, not a Python implementation quirk but a structural requirement
of how every hash table works.

Why immutability is the guardrail. Immutable built-ins (strings, numbers, tuples of immutable
elements) are hashable by default because nothing about them can change after creation, so their hash
is safe to cache and reuse forever. Lists and dicts are explicitly excluded (hash([1,2,3]) raises
TypeError) precisely to stop you from creating this bug by construction, Python would rather fail
loudly at the point you try to use a list as a key than silently corrupt a dict later.

Worked example: why the bare case fails

d = {}
key = (1, 2)          # tuple of ints: immutable, hashable
d[key] = "ok"
print(d[(1, 2)])       # "ok" -- fine, the tuple can never change

try:
    bad_key = [1, 2]   # a list: mutable, unhashable
    d[bad_key] = "boom"
except TypeError as e:
    print("TypeError raised (unhashable type: list)")

# The genuinely dangerous case: a tuple that CONTAINS a mutable object.
# Tuples are hashable only if every element inside them is hashable at hash-time;
# nothing stops you from later mutating that inner element.
inner = [1, 2]
sneaky_key = (inner, "label")
try:
    d[sneaky_key] = "will this even work?"
except TypeError as e:
    print("TypeError on tuple containing a list (unhashable type: list)")

Running this: the first insert succeeds and prints ok. The bare-list insert raises a TypeError
mentioning unhashable type: 'list', caught as printed (the exact wording of that message has
changed slightly across Python versions, but the failure is always a TypeError at the point of
use). The "sneaky" tuple-containing-a-list case ALSO raises TypeError, because Python checks
hashability of every element when it hashes the outer tuple, so it fails immediately at insertion
rather than allowing a later, harder-to-diagnose corruption. The real danger in production code is
not this caught case, it's when someone works around the TypeError by converting the list to
something hashable (e.g. id(inner) or a shallow copy) and then mutates the original list
afterward, which silently desyncs the key's later identity from what the table actually stored it
under, no exception, just a lookup that mysteriously "loses" data.

Three ways to safely key on mutable or complex data

1. Freeze the structure (tuple / frozenset). Recursively convert lists to tuples and dicts to
frozensets of (key, value) pairs. This makes nested, order-varying structures compare and hash
consistently, since frozenset is order-independent for dict-shaped data:

def freeze(obj):
    """Recursively convert lists/dicts into hashable tuples/frozensets."""
    if isinstance(obj, dict):
        return frozenset((k, freeze(v)) for k, v in obj.items())
    if isinstance(obj, list):
        return tuple(freeze(v) for v in obj)
    return obj

record_a = {"user": "alice", "tags": ["x", "y"]}
record_b = {"tags": ["x", "y"], "user": "alice"}  # same content, different key order

cache = {}
cache[freeze(record_a)] = "cached-result"
print(freeze(record_a) == freeze(record_b))   # True
print(cache.get(freeze(record_b)))            # "cached-result" -- hits despite key-order difference

Output: True then cached-result, confirming the frozen key is order-independent. Trade-off:
freezing allocates a new structure per lookup and is O(size of the structure), and nested unhashable
leaves (e.g. a list buried three levels deep) still need to be frozen too, recursion handles that but
adds overhead.

2. Canonical serialization. Turn the object into a deterministic string (or bytes) and key on
that. json.dumps(obj, sort_keys=True) is the common choice for JSON-shaped data:

import json

def canonical_key(obj):
    return json.dumps(obj, sort_keys=True)

record_a = {"user": "alice", "tags": ["x", "y"]}
record_b = {"tags": ["x", "y"], "user": "alice"}  # same content, different key order

d2 = {}
d2[canonical_key(record_a)] = "cached-result-2"
print(d2[canonical_key(record_b)])   # "cached-result-2" -- same canonical string regardless of order

Output: cached-result-2. Trade-off: simple and works across process boundaries (the string can be
persisted or sent over the wire), but floats serialize with locale/precision quirks (0.1 vs
0.10000000000000001), and it's slower than a native hash for large objects since it re-encodes the
whole structure on every lookup.

3. Custom __hash__ and __eq__ that ignore volatile fields. When only some fields define
identity (a cached score that legitimately changes shouldn't invalidate the key), hash and compare on
the immutable identity fields only, and document that the mutable field must never be touched from
outside:

class UserScore:
    """Cached score can change; identity for hashing/equality is user_id only."""
    def __init__(self, user_id, score):
        self.user_id = user_id   # identity field: must stay constant
        self.score = score       # volatile field: excluded from hash/eq

    def __hash__(self):
        return hash(self.user_id)

    def __eq__(self, other):
        return isinstance(other, UserScore) and self.user_id == other.user_id

seen = {}
u1 = UserScore(user_id=42, score=10)
seen[u1] = "first-seen"
u1.score = 99                     # mutate the volatile field AFTER insertion
print(seen[u1])                                # "first-seen" -- still found
print(seen[UserScore(user_id=42, score=-1)])   # "first-seen" -- different object, same identity

Output: first-seen printed twice, first for the mutated original object, then for a brand-new
object that only shares the identity field. This is the Java hashCode/equals pattern too: base
both on the same subset of fields, and never on a field that changes post-insertion.

Trade-offs and pitfalls

The instinctive fix many candidates reach for, wrapping a mutable structure in something hashable
just to satisfy the type checker, doesn't remove the underlying risk unless the wrapped value is
ALSO guaranteed not to change afterward; a frozenset or an immutable tuple genuinely solves this,
while hashing on id() or a one-time snapshot does not, since the object behind that identity can
still be mutated by other code holding a reference to it. Freezing is fastest for in-process,
short-lived keys; canonical serialization is best when the key must cross a process boundary or be
persisted; custom __hash__/__eq__ is right when you own the class and want to control identity
semantics explicitly rather than reconstructing it from raw data every time.