Search
8 results for “data-structures”
Search results
Hash Tables & the Hash/Equality Contract
Why two objects that compare equal but hash differently don't raise an error when used as a dict key, they just silently fail to find each other, and why that makes the __eq__/__hash__ contract one of the most dangerous ones to get wrong.
Python Data Structures
When to reach for a list, tuple, dict, or set based on what operations you actually need fast, and why choosing the wrong one is a common hidden performance bug.
What is the required contract between equality and hashing for an object used as a dictionary key, and why does the hash table need it specifically?
The contract is one-directional but strict: if two objects compare equal, they must produce the same hash value. A hash table uses an object's hash to pick which bucket to look in, then uses equality only to confirm the exact match within that bucket, so if two equal objects hashed differently, a lookup for one would search the wrong bucket entirely and never even reach the equality check that would have confirmed the match. The hash doesn't have to be unique across unequal objects (collisions are expected and handled), it just has to agree for anything that compares equal, that's the one property the whole lookup mechanism depends on.
A custom class defines __eq__ based on a value field but leaves __hash__ using default identity-based hashing. What actually goes wrong when you use an instance as a dict key?
In Python 3, simply defining `__eq__` without touching `__hash__` doesn't leave the old identity-based hash in place, Python automatically sets `__hash__` to `None` on that class, making instances unhashable, so using one as a dict key raises `TypeError` immediately rather than corrupting anything. This happens even if a parent class defines `__hash__`: overriding `__eq__` in a subclass sets that subclass's `__hash__` to `None` regardless of what the parent provides, ordinary inheritance does not carry the parent's hash forward. The silent, no-exception version of this bug only happens if the class explicitly keeps or re-supplies an identity-based `__hash__` alongside the value-based `__eq__` (e.g. `__hash__ = object.__hash__`, or, to retain a parent's hash on purpose, `__hash__ = Parent.__hash__`). In that case, two instances with the same value compare equal (`a == b` is `True`) but hash differently, and inserting under key `a` then looking up with an equal-but-distinct key `b` lands in the wrong hash bucket and returns nothing, because the hash mismatch never gave the lookup a chance to even check equality against the right entry.
Why does Python's documentation say a class defining mutable objects with a custom __eq__ should not implement __hash__ at all?
If an object's hash is derived from fields that can change after the object is already stored as a dict key, mutating it changes its hash value, but the object stays in whatever bucket it was originally placed in based on the old hash, so a subsequent lookup computes the new hash, looks in the new (wrong) bucket, and fails to find an object that is, in fact, still in the dictionary. Making a mutable object unhashable by default (which not defining `__hash__` effectively signals) prevents this specific class of bug entirely, at the cost of not being able to use that object as a dict key or set member at all, a deliberate, documented trade-off favoring correctness over convenience.
Why is checking membership with `in` fast on a set or dict but slow on a list?
Sets and dicts are implemented as hash tables, checking whether a value exists means computing its hash and looking up that bucket directly, an O(1) average-case operation regardless of how many items are stored. A list has no such index; checking membership means scanning entries one by one until a match is found or the list ends, an O(n) operation that gets slower as the list grows. For any code doing repeated membership checks against a growing collection, using a set instead of a list is often the single biggest easy performance fix available.
What is the practical difference between a list and a tuple, beyond mutability?
The most visible difference is that lists are mutable (items can be added, removed, or changed after creation) and tuples are immutable (fixed once created). That immutability has real consequences: tuples can be used as dictionary keys or set members because they're hashable, while lists cannot. Tuples also communicate intent, a fixed-size, heterogeneous grouping (like a coordinate pair) is usually a better fit for a tuple, while a variable-length, homogeneous collection is usually a better fit for a list, independent of whether mutation is actually needed.
Why can a list not be used as a dictionary key, but a tuple can?
Dictionary keys must be hashable, and hashability requires that an object's hash value never changes for the lifetime of the object, which in turn requires immutability, because a mutable object's contents (and therefore its logical value) could change after being used as a key, silently breaking the hash table's internal bucket placement. Lists are mutable, so Python makes them explicitly unhashable to prevent that class of bug. Tuples are immutable, so as long as every element they contain is also hashable, the tuple itself is hashable and safe to use as a dictionary key or set member.