Search
5 results for “hash-tables”
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.
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.
What is the difference between a reserved/committed-use discount and a spot/preemptible instance, and when does each make sense?
A committed-use discount (reserved instances, savings plans) trades a usage commitment, a fixed amount of spend or capacity over a term, typically one or three years, for a significant price reduction on workloads you know will run continuously. Spot/preemptible instances offer a much steeper discount in exchange for the provider being able to reclaim the capacity with little notice, making them suitable only for interruption-tolerant workloads (batch jobs, stateless workers, CI runners) rather than anything requiring guaranteed uptime. Committed-use addresses predictable steady-state load; spot addresses flexible, interruption-tolerant load, using either for the wrong workload type either wastes the discount or causes outages.