This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients eric.smith, jdemeyer, mark.dickinson, rhettinger, sir-sigurd, tim.peters
Date 2018-10-03.01:15:04
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
> SeaHash seems to be designed for 64 bits.


> 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));

Date User Action Args
2018-10-03 01:15:06tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, eric.smith, jdemeyer, sir-sigurd
2018-10-03 01:15:05tim.peterssetmessageid: <>
2018-10-03 01:15:05tim.peterslinkissue34751 messages
2018-10-03 01:15:04tim.peterscreate