Skip to content

What guarantees do u32 Atom hash values offer? #224

Closed

Description

@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:

// 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.

Activity

  1. devongovett commented on Oct 5, 2021

    @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?

    state.write_u32(self.get_hash())

  2. SimonSapin commented on Aug 20, 2026

    @SimonSapin
    Member

    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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions