Guidance on hash collisions between different key types

[reinerp]

Hi,

I'd like to use ahash to hash my particular encoding of strings. In my application I store strings in one of the following three layouts, depending on string length:

1. If len<=8, I zero-pad to 8 bytes.
2. If len > 8 && len<=24, I zero-pad to 24 bytes.
3. Otherwise, I use the exact length of the string.
   In all cases, length is stored elsewhere.

I'd like to use ahash on the padded strings, as efficiently as possible. That suggests using:

1. CallHasher on type (u64, u64), representing (length, zero_padded_payload) pairs. Alternatively, CallHasher on u128 representing (length | (zero_padded_payload << 64)).
2. CallHasher on type (u64, u64, u128), representing (length, payload_bytes_0to8, payload_bytes_9to16) tuples.
3. CallHasher on type &[u8].

I have two questions:
A) In general the contract is that CallHasher avoids collisions within a single type. Does collision resistance extend to hashing over multiple different types? Eg can I assume collisions resistance across the hashing modes (1)/(2)/(3)?
B) Any guidance on faster alternatives to (1) and (2)?

[tkaitchuck]

As the layout affects hashing which of 1,2, or 3 is fed in will affect the resulting hash. This means that one cannot assume the same string with different amounts of padding or stored in one of these formats will hash differently. In general collisions would only occur between hashes of different layouts when the data from one matches the other. For example (u64, u64) would collide with (u32, u32) with the same numeric values, because when hashing u32s are just treated as u64s. But as you mention above (u64, u64) would very likely not collide with (u64, u64, u128) because those involve a different sequence of calls.

In terms of a faster result hashing a single u128 is faster than (u64, u64) ignoring any conversion cost.
A (u64, u64, u128) is probably not too much faster than hashing the same size &[u8], but the conversion cost between the two is probably more expensive than the difference either way, so you are probably best off just using whatever layout is actually needed for the rest of the logic.