Why is hash(-1) == hash(-2) in Python?

https://omairmajid.com/posts/2021-07-16-why-is-hash-in-python/

by alexmolas • 2 years ago

103 91 2 years ago

Terr_• 2 years ago

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

kevinventullo• 2 years ago

We all know that types are not Pythonic.

(I’m only mostly joking)

folkrav• 2 years ago

Ackchyually, Python has pretty strong typing, as far as dynamic languages go.

kstrauser12• 2 years ago

Not really, I don’t think. Python code doesn’t ever really use hash() for anything where specific outputs are expected. Even if hash(a)==hash(b), it’s not implied that a==b or a is b.

TRiG_Ireland2• 2 years ago

Yes, but having result types would avoid the need for this special casing.

tmvphil• 2 years ago

But -2 seems like just a bad choice here. -1 and -2 are very "common" integers. Seems they could have just picked a quasi-random large integer to reduce the likelihood of collision. I expect hash functions to have collisions, but I expect it to be "unlikely" in a way that scales with the size of the hash.

nayuki4• 2 years ago

In other words, this is a case of https://en.wikipedia.org/wiki/In-band_signaling versus out-of-band signaling https://en.wikipedia.org/wiki/Signaling_(telecommunications)... .

EricRiese• 2 years ago

Clears throat the precise wiki page you're looking for is the Semipredicate Problem

https://en.wikipedia.org/wiki/Semipredicate_problem

kazinator5• 2 years ago

-1 is in-band signaling; but it steals a value.

kazinator5• 2 years ago

1. But, Python has exceptions! The underlying C language doesn't, but Python's run-time has them and can use them in the C code.

2. It may be an argument for ensuring that absolutely everything that is an object can hash: the object hasher must not have error states. Nobody wants the overhead of a simple hash code being wrapped in a result type.

kstrauser12• 2 years ago

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.”

Etheryte• 2 years ago

I 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.

kstrauser12• 2 years ago

But 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.

pmarreck2• 2 years ago

A better question might be, why are people still using OO dynamic languages without any typing?

kstrauser12• 2 years ago

Not sure. Is anyone using a language like that? Python certainly isn’t one.

worik3• 2 years 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

nayuki4• 2 years ago

without any typing?

    >>> "abc" + 321
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: can only concatenate str (not "int") to str

I rest my case.

homebrewer• 2 years ago

TaPL should be required reading for self proclaimed "engineers". Do untyped languages even exist, or could they? maybe something purely theoretical for ivory tower academics? Even POSIX shell and assembler type their values.

nayuki4• 2 years ago

Do untyped languages even exist, or could they? Even POSIX shell and assembler type their values.

I program in assembly language. Memory is just a big array of bytes. Values don't have types, but each instruction chooses what type to interpret memory as - e.g. uint8, int16, float32, x86 real-mode pointer, long-mode pointer, etc.

int_19h• 2 years ago

I think one can reasonably argue that, if the language only has a single type, it is effectively "untyped".

That would mean languages like Tcl. Or, for that matter, B.

tjalfi• 2 years ago

BCPL[0], BLISS[1], and Forth[2] are all untyped.

[0] https://en.wikipedia.org/wiki/BCPL

[1] https://en.wikipedia.org/wiki/BLISS

[2] https://en.wikipedia.org/wiki/Forth_(programming_language)

pmarreck2• 2 years ago

Bah, I meant strongly or statically typed, not just "typed"

ks2048• 2 years ago

The next k for which hash(k) != k: 2**61-1

    print(hash(2**61 - 2))
    2305843009213693950

    print(hash(2**61 - 1))
    0

TRiG_Ireland2• 2 years ago

I enjoyed this, because it seems to be written by an interested and interesting human, at a level that I could actually follow.

jiggawatts• 2 years ago

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.”

krab2• 2 years ago

I don't think so. This is true for people writing cpython. But if you implement custom `__hash__` method, you should be fine.

dagw2• 2 years ago

If 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.

dagw2• 2 years ago

interestingly 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.

intalentive• 2 years ago

>> d = {-2: None}
>> -1 in d

False

What gives?

krab2• 2 years ago

Because -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.

Arnavion• 2 years ago

If hashmaps only looked at hash(k1) == hash(k2) and not also k1 == k2 they would be quite useless as maps.

hyperpape• 2 years ago

Since 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.

nayuki4• 2 years 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.__...

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...

Galanwe• 2 years 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• 2 years ago

Out params are thing too.

kragen2• 2 years ago

Also you can longjmp().

sgerenser• 2 years ago

Functions 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• 2 years ago

You could always check errno and reset it to zero before any function call.

kazinator5• 2 years ago

There 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.

moralestapia• 2 years ago

it has to return that error as its return value.

This is the kind of crap ignorant C developers do and then pretend is the language's fault.

You can jump, you can return a reference to a complex type, a tuple, whatever.

snickerbockers• 2 years 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.

nneonneo2• 2 years ago

Naturally, this extends to custom types:

  >>> class X:
  ...     def __hash__(self): return -1
  ... 
  >>> hash(X())
  -2

daxfohl4• 2 years ago

Another question is why do ints largely hash to themselves? Most hashing guides recommend hashes be far more distributed IIUC.

woodruffw• 2 years ago

Python's `__hash__` used primarily for hash map bucketing. In that context, the identity of an integer is a perfectly cromulent bucketing value.

zarzavat• 2 years ago

If 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.

kazinator5• 2 years ago

There 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• 2 years ago

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.06s

binary1322• 2 years ago

The 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• 2 years ago

In 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.

binary1322• 2 years ago

What 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.

kazinator5• 2 years ago

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? :)

AEVL• 2 years ago

Why not instead have

hash(-1)=-2,

hash(-2)=-3,

hash(-3)=-4,

and so on?

Why is hash(-1) == hash(-2) in Python?

Related Stories