3 ms·
Another question is why do ints largely hash to themselves? Most hashing guides recommend hashes be far more distributed IIUC.
by daxfohl 2y ago
Another 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.)