8 ms·
Why is hash(-1) == hash(-2) in Python?
- kstrauser 2y agoBecause 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.”
- Etheryte 2y agoI think this is not constructive criticism. There's a good, clear cut reason for this specific overlap (error handling), saying it collides just because is not really useful.
- kstrauser 2y agoBut even that’s an implementation detail that happens to be true today, but could easily disappear tomorrow. There’s nothing in the docs saying it has to be that way, or that you can infer anything from a hash output other than that it’s going to be consistent within a single execution of that Python program.
- tooltower 2y agoThis article is not about the API contract of the hash function, or the abstraction it provides. If you are just trying to hash things, you don't need any info here. It's very much trying to go _under_ the abstraction layer to investigate its behavior. Because it's interesting. This is very similar to how people investigate performance quirks or security issues.
- kstrauser 2y agoI read the article and it's interesting! I learned something from it. From an end user POV it explains the mechanism behind how hash(-1)==hash(-2), which is neat. There's not really a why behind it, though. It wasn't really planned or designed for -1 to have an unexpected hash value. That's just the value the devs randomly picked as a flag. It could've been -837 just as easily.
- sedatk 2y agoIt could have been a bug. There's nothing wrong with the question and seeking answers to it. It was an interesting read too.
- alain94040 2y agoIf the article title had been "why does the hash function never return -1", you would agree it's not a random behavior and serves a very clear purpose. It just so happens that the original author didn't know that until they did all the digging (nice job by the way).
- pmarreck 2y agoA better question might be, why are people still using OO dynamic languages without any typing?
- kstrauser 2y agoNot sure. Is anyone using a language like that? Python certainly isn’t one.
- worik 2y ago> Python certainly isn’t one. I am not a Python expert, but... Python is described as OO and I thought is is dynamically typed Not quite "without any typing" but close
- kstrauser 2y agoNot really. Python's strongly typed, but dynamically. You can think of Python variables as untyped references to strongly typed values: the values are typed, but their names are not.
- Dylan16807 2y agoI agree with your last sentence, but I think we shouldn't say python itself is "strongly typed".
- kstrauser 2y agoWhy, specifically? It's commonly described as strongly typed and I'm not aware of an argument against that.
- Dylan16807 2y agoIs the specific reason not clear? You just said it. The variables are untyped. Strong versus weak is not super solidly defined as referring only to values and not variables.
- ks2048 2y agoThe next k for which hash(k) != k: 2**61-1 print(hash(2**61 - 2)) 2305843009213693950 print(hash(2**61 - 1)) 0
- TRiG_Ireland 2y agoI enjoyed this, because it seems to be written by an interested and interesting human, at a level that I could actually follow.
- jiggawatts 2y agoThis 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.”
- krab 2y agoI don't think so. This is true for people writing cpython. But if you implement custom `__hash__` method, you should be fine.
- dagw 2y agoIf you're writing a custom hash function in python for a custom python class, then this won't affect you since it's only treated as an error in the underlying C code. If you're adding a new type to the core python language then you have to be aware of this, but if you're hacking the C implementation to change the core language then you're probably pretty well versed in the cpython internals, or at least surrounded by people that are.
- dagw 2y agointerestingly enough though, it doesn't seem to be possible to write a custom hash function that returns -1 >>> class Foo: def __hash__(self): return -1 >>> f = Foo() >>> print(hash(f)) -2 So if you're doing something where you have a custom __hash__ function that you're expecting to return -1 for a certain value and then are testing for value of the hash of an object rather than testing the property of the object directly, then this might bite you. But I cannot think of any reasonable case where you might want to do that.
- omoikane 2y agoPerhaps the worry was that because the observed behavior up until now was that hash never returns -1, if it were possible possible to write a custom hash function that returns -1, that might break some unsuspecting code due to Hyrum's Law.
- intalentive 2y ago>>> d = {-2: None} >>> -1 in d False What gives?
- krab 2y agoBecause -1 is not equal to -2. They will fall into the same bucket of the hash map, but the hash collisions are expected and must be accounted for.
- deleted 2y ago[deleted]
- Arnavion 2y agoIf hashmaps only looked at hash(k1) == hash(k2) and not also k1 == k2 they would be quite useless as maps.
- hyperpape 2y agoSince hashes aren't guaranteed to be unique, a dictionary should use equality to actually confirm that the object with the given hash matches the key present in the dictionary.
- nayuki 2y ago> The __hash__() method should return an integer. The only required property is that objects which compare equal have the same hash value; it is advised to mix together the hash values of the components of the object that also play a part in comparison of objects ... -- https://docs.python.org/3/reference/datamodel.html#object.__hash__ https://docs.python.org/3/reference/datamodel.html#object.__... > The general contract of hashCode is: > * If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result. > * It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables. -- https://docs.oracle.com/en/java/javase/23/docs/api/java.base/java/lang/Object.html#hashCode%28%29 https://docs.oracle.com/en/java/javase/23/docs/api/java.base...
- Galanwe 2y ago> 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.
- secondcoming 2y agoOut params are thing too.
- kragen 2y agoAlso you can longjmp().
- sgerenser 2y agoFunctions using errno typically still use a return value of -1 to indicate an error has occurred, then errno just stores the specific error code. Otherwise, how do you even know that you need to check errno?
- BenjiWiebe 2y agoYou could always check errno and reset it to zero before any function call.
- kazinator 2y agoThere are examples of such an ambiguity in the ISO C library itself. In those situations, the application must begin by clearing errno to zero. Then, it checks for a certain error value or values from the function which are ambiguous: they could be legit or indicate an error. If one of those values occurs, and if errno is nonzero, then the error occurred. This is how you deal with, for instance the strtol (string to long int) function. If there is a range error, strtol returns LONG_MIN or LONG_MAX. Those are also valid values in the range of long, but when no error has occurred, they are produced without errno being touched. strtol can also return 0 in another error case, when the input is such that no conversion can be performed. ISO C doesn't require errno to be set to anything in this case, unfortunately. The case is distinguished from a legitimate zero by the original pointer to the string being stored in *endptr (if the caller specifies endptr that is not null). ISO C and POSIX library functions do not reset errno to zero. They either leave it alone or set it to a nonzero value. If you need to use the above trick and are working inside a C library function, you have to save the original errno value before storing a zero in it, and then put that value back if no error has happened.
- snickerbockers 2y ago>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.
- nneonneo 2y agoNaturally, this extends to custom types: >>> class X: ... def __hash__(self): return -1 ... >>> hash(X()) -2
- daxfohl 2y agoAnother question is why do ints largely hash to themselves? Most hashing guides recommend hashes be far more distributed IIUC.
- woodruffw 2y agoPython's `__hash__` used primarily for hash map bucketing. In that context, the identity of an integer is a perfectly cromulent bucketing value.
- zarzavat 2y agoIf your keys are multiples of the table size then all your keys will hash to the same bucket, in a naive hash table at least.
- daxfohl 2y agoMore explicitly, since buckets in Python's Set implementation are the bottom N bits of the hash (where N depends on set size), this ensures linear sequences of ints (which are the most common type of int set) are all in different buckets, so zero collisions. This is the case except when the differences between integers in the set are multiples of powers of 2. But even then, the way Set is implemented, you don't see perf start to regress until like 2**20 or so. If everything in the set is multiples of 2**20, then they start to underperform better-distributed hashes. But it never gets more than like twice as slow. So, it ends up being a matter of optimizing for the common case, but still being reasonably performant for the worst case.
- deleted 2y ago[deleted]
- kazinator 2y agoThere could be an issue whereby some attacker controls the hash inputs which happen to be integers, and chooses a sequence which collides to the same hash value. It would be easy to identify such a sequence. It just doesn't seem to have been identified as a real isssue, probably because the most commonly hashed external data is character strings. (For those, there are countermeasures like a properly scrambled hashing function, modified by a seed that can be randomized.)
- vhcr 2y agoSomewhat 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.06s
- binary132 2y agoThe 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.
- lifthrasiir 2y agoIn this case however it can be partly justified as a space saving mechanism, as that hash has to be also cached in the object. It's like Rust's `Option<NonZeroU64>` done manually.
- binary132 2y agoWhat I’m saying is either the value or the error can be discarded. If it was an error, the exception mechanism can be used since at that point you’re in the Python wrapper. It would probably be a little slower though, but Python is already slow. That way the error doesn’t need to be in the API at all.
- kazinator 2y agoObject 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? :)
- Terr_ 2y agoIn 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 https://en.wikipedia.org/wiki/Result_type
- kevinventullo 2y agoWe all know that types are not Pythonic. (I’m only mostly joking)
- folkrav 2y agoAckchyually, Python has pretty strong typing, as far as dynamic languages go.
- bhickey 2y agoSure. Everything is a PyObject.
- nas 2y agoEvery PyObject structure has a ob_type pointer.
- ackfoobar 2y agoEvery Object in Java has a getClass method. If we changed all the static type information in Java to the `Object` type, that'd be pretty close to Python's case. GP's post is probably the "unityped" critique of dynamically typed languages by Robert Harper: https://existentialtype.wordpress.com/2011/03/19/dynamic-languages-are-static-languages/ https://existentialtype.wordpress.com/2011/03/19/dynamic-lan...
- bhickey 2y agoThank you for sharing. I hadn't read that critique but I am in wholehearted agreement. Dynamic typing imposes significant cognitive overhead in exchange the privilege of letting you writing incorrect programs.
- AEVL 2y agoWhy not instead have hash(-1)=-2, hash(-2)=-3, hash(-3)=-4, and so on?