You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
What guarantees do u32 Atom hash values offer? #224
This uses the phf* (perfect hash function) crates underneath, and if I understand correctly, phf offers guaranteed perfect, no collision, hash values for a compile time aggregated (static) set.
However as implemented here, these u64 hashes are shift-xor'd to u32 values:
Does this not reintroduce a risk of collision? Or does string_cache_codegen also include a guaruntee that the u32-bit hash doesn't collide for a static set? Or does string_cache not really need to care about such collisions?
Depending on the answer, I might be able to offer a doc PR.
The hash from phf is only perfect for strings that are in the static set. impl Hash for Atom makes no such guarantee, and may have collisions. Still, I think we can and should use 64 bits instead of 32. I’ll make a PR soon.
impl Hash for Atom using the hash we already have is an optimization to avoid a variable-length loop hashing the string bytes again.
Activity
devongovett commentedon Oct 5, 2021
We found two strings that collide: "rgb2hex" and "hex2rgb". Both are under the MAX_INLINE_LEN so hit this code path when hashing.
string-cache/src/atom.rs
Lines 144 to 148 in 0cf93bb
Should this not write the actual bytes to the hasher rather than only a u32?
string-cache/src/atom.rs
Line 183 in 0cf93bb
SimonSapin commentedon Aug 20, 2026
The hash from
phfis only perfect for strings that are in the static set.impl Hash for Atommakes no such guarantee, and may have collisions. Still, I think we can and should use 64 bits instead of 32. I’ll make a PR soon.impl Hash for Atomusing the hash we already have is an optimization to avoid a variable-length loop hashing the string bytes again.Assorted changes and prepare 0.11.0 release (#305)