Tim Peters <t...@python.org> added the comment:
> SeaHash seems to be designed for 64 bits.
Absolutely.
> I'm guessing that replacing the shifts by
>
> x ^= ((x >> 16) >> (x >> 29))
>
> would be what you'd do for a 32-bit hash.
My guess too. But "the prime" is a puzzle. As noted before, the 64-bit prime
is specially constructed to satisfy specific dispersion properties. While I
haven't triple-checked this, I believe it fails at two specific bit positions:
- Bit 2**16 doesn't propagate into the leading 4 bits at all.
- Bit 2**17 does propagate into bit 2**60, but _only_ into that bit among the
highest 4 bits. One of the criteria is that the prime shouldn't propagate a
lower-order bit into _only_ the least-significant of the 4 leading bits.
Repairing that would probably require adding a bit or two. But the prime
already has 35 bits set. The greater the imbalance between 0 and 1 bits, the
more multiply acts like a simpler sequence of shift-and-adds or
shift-and-subtracts (for example, at an extreme, consider the multiplier (1 <<
63) - 1).
Anyway, it seems the density of 1 bits would have to be even higher for a
32-bit multiplier to ensure all low-order bits directly propagated to at least
one of the topmost 3 bits, but not to the third-most significant alone.
Or I could search for a 31-bit prime - or just an odd integer - that got as
close as possible with 16 or 17 bits set. Or ...
> Alternatively, we could always compute the hash with
> 64 bits (using uint64_t) and then truncate at the end
> if needed.
Provided we continue to like it at all ;-) In which case I'd probably end it
with
32_bit_result = (32_bit_result_type)(x ^ (x >> 32));
instead.
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue34751>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
