Hash collision in Expression caching about qnet HOT 4 CLOSED

It turns out that the true culprit is defining equality based on the hash:

def __eq__(self, other):
    return hash(self) == hash(other)

This is not a good idea! While equal expression must have the same hash, the reverse is not true (and happens much more frequently than I had thought). Note that things like dicts are robust with respect to hash collisions, but only if equality is defined correctly.

from qnet.

Yeah, I was surprised by the way you guys talked about hash collisions as a bug. Frequent hash collisions should never result in incorrect behavior, only poor performance. The bug is in what @goerz just quoted, and any other statements that rely on the same assumption.

The contract is that a == b is true implies hash(a) == hash(b) is also true, not the other way around. For any questions and confusions of this kind, this page in the python documentation is a goldmine: https://docs.python.org/3/reference/datamodel.html

from qnet.

Wow, that's pretty crazy! Seems like hash collisions in Python happen very easily: https://stackoverflow.com/questions/32504977/hashing-different-tuples-in-python-give-identical-result

I'll look into whether hashlib can provide a better alternative.

from qnet.

Thanks for the clarifications! I didn't mean to imply that the hash collision was a bug itself, but only that real bugs such as a-a == a-2a seemed to arise from the hash collision. And as @goerz mentions, it comes from the current implementation of __eq__ (in Expression?), which precisely assumes/enforces hash(a) == hash(b) implies a == b. I'm glad to hear that Python dictionaries don't rely solely on hash, since this means we could directly compare the Expression and its operands instead for equality testing and caching.

from qnet.