Somewhat related, hash() returns a result % sys.hash_info.modulus, so if you build a set or a dict with keys multiple of sys.hash_info.modulus, you run into quadratic behavior.
>>> {i * sys.hash_info.modulus for i in range(5000)}
0.40s
>>> {i * sys.hash_info.modulus for i in range(50000)}
29.34s
>>> {i for i in range(50000)}
0.06sNaturally, this extends to custom types:
>>> class X:
... def __hash__(self): return -1
...
>>> hash(X())
-2The next k for which hash(k) != k: 2**61-1
print(hash(2**61 - 2))
2305843009213693950
print(hash(2**61 - 1))
0The fact that a C function really only has its return value for communicating success or error status is why most fallible C functions use mutable parameters, also known as output arguments, for their result value or values. This is like, elementary C program design.
Another question is why do ints largely hash to themselves? Most hashing guides recommend hashes be far more distributed IIUC.
> So, in C, when you design a function, and you want your function to be able to indicate “there was an error”, it has to return that error as its return value.
Well, you can also use an errno-like system. It has its own set of drawbacks as well, but it removes the "I need to reserve a sentinel value" problem.
I enjoyed this, because it seems to be written by an interested and interesting human, at a level that I could actually follow.
Object hashes that can fail or be unimplemented, where lower-level hashes have to be aware of this and stay away from the value that the parent uses for error signaling?
What else is unmitigated shit in Python? :)
Why not instead have
hash(-1)=-2,
hash(-2)=-3,
hash(-3)=-4,
and so on?
>CPython is written in C, and unlike Python, C doesn’t have exceptions. So, in C, when you design a function, and you want your function to be able to indicate “there was an error”, it has to return that error as its return value
This is just wrong. C doesn't feature 'error handling' as a dedicated form of branching the way many higher level languages do and you're in no way required to use return codes as an error signal. This is a case of bad API design and is entirely python's fault.
>>> d = {-2: None}
>>> -1 in d
False
What gives?
Because the hash function is only reliably useful for laying out dict keys, and its outputs are totally opaque and coincidental.
The pigeonhole principle says there are an infinite number of inputs with the same hash output. Trying to figure out how that happens can be fun and enlightening, but why? “Because it just does, that’s all.”
This seems like a loaded footgun: anyone writing a custome hash function has to know about -1 being treated like an error and handle it in a similar way.
I can’t think of any other language where this kind of thing happens, which means other developers won’t expect it either.
I can see the bug report now: “certain records cause errors, occurs only for about one in a few billion.”
A better question might be, why are people still using OO dynamic languages without any typing?
In a way this is an argument for languages where it's normal to have result-types [0] or exceptions, instead of -1 etc. It just feels wrong to have any potential collision or confusion between normal results and error results.
[0] https://en.wikipedia.org/wiki/Result_type