What guarantees do u32 Atom hash values offer?

[dekellum]

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:

string-cache/src/atom.rs

Line 259 in 51b58ce

// This may or may not be great...

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.

[devongovett]

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

	INLINE_TAG => {
	let data = self.unsafe_data.get();
	// This may or may not be great...
	((data >> 32) ^ data) as u32
	}

Should this not write the actual bytes to the hasher rather than only a u32?

string-cache/src/atom.rs

Line 183 in 0cf93bb

state.write_u32(self.get_hash())

[SimonSapin]

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.