Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: b420bd34107467e3dcf8e9e5c05d2a042b97cfdb
https://github.com/WebKit/WebKit/commit/b420bd34107467e3dcf8e9e5c05d2a042b97cfdb
Author: Chris Dumez <[email protected]>
Date: 2026-07-13 (Mon, 13 Jul 2026)
Changed paths:
M Source/WTF/wtf/HashFunctions.h
Log Message:
-----------
pairIntHash extracts the wrong bits of the 64-bit product, degrading hash
distribution
https://bugs.webkit.org/show_bug.cgi?id=319230
Reviewed by Darin Adler and Yusuke Suzuki.
pairIntHash() implements the multiplicative hashing scheme from
opendatastructures.org, whose final step folds the 2w-bit product down
to the high w bits (w = 32, the width of unsigned). It did this with:
```
product >> (sizeof(uint64_t) - sizeof(unsigned))
```
sizeof() returns a byte count, but >> shifts by bits, so this evaluated
to `product >> 4` rather than the intended `product >> 32`. The result
(named highBits) was therefore bits [4, 36) of the product -- mostly the
poorly-mixed low bits that multiplicative hashing deliberately discards,
instead of the well-mixed high 32 bits [32, 64).
This does not affect correctness: the hash remains deterministic, so
HashMap/HashSet stay correct. But it worsens bit-mixing and raises
collision rates for tables keyed on integer std::pair/tuple values
(PairHash, and the DefaultHash for std::pair), which is especially
noticeable for clustered small-integer keys.
Multiply the byte-width difference by 8 to shift by the correct number
of bits.
* Source/WTF/wtf/HashFunctions.h:
(WTF::pairIntHash):
Canonical link: https://commits.webkit.org/317095@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
