This is language-agnostic advice, nothing rust-specific.
want to assign a unique identifier to a stream of bits.
The standard answer to this is:
- assign hash = SHA3(input)
- return prefix of that hash
where we look at number of inputs, and risk tolerance,
to decide how long that prefix should be.
Often a prefix of 128 bits suffices for a UUID.
You were a bit vague on length of input,
number of inputs, risk tolerance,
and maximum acceptable hash length.
Knowing more details would make it
easier to assess whether your use case
is a good fit for the standard solution.
It is important in my application that no collision happen.
That adjective doesn't really map to a probability figure.
There is certainly the notion of a
perfect hash.
But you didn't disclose an essential precondition.
You didn't tell us that the ("offline") algorithm gets to see all
possible inputs before returning its first hash value.
As written the OP appears to describe requirements of an "online" algorithm.
If offline operation is acceptable, then just set counter = 1
and verify that each SHA3(counter || input)
is distinct.
If collision is detected, simply increment the counter
and keep trying again until you find a perfect hash.
This will happen quickly if we emit 128 bits,
and more slowly if we're required to emit fewer bits,
especially when presented with a large number of inputs.
For practical input values it should take zero or a tiny
number of retries to obtain a perfect hash function.
testing
let a1: [u8; 4] = [0, 0, 0, 0];
...
let a2: [u8; 4] = [0, 0, 0, 1];
...
let a3: [u8; 4] = [0, 1, 0, 0];
Consider renaming these to more natural identifiers: a0
, a1
, a4
.
I found the sequence of .iter()
calls confusing.
I am convinced you deliberately planned them so as to teach me something.
I confess I do not know what you wanted to teach; I am as yet unenlightened.
Possibly doing non-interleaved hashing of the various arrays would be clearer.
The fault perhaps lies less with the unit test code,
which likely should not have a ton of comment lines,
and more with TreeHasher's hash() function.
Certainly there's a bunch of comments in there.
But the overall datastructure eluded me.
The comments are low level, and they're not
guiding me to certain spots in a high level
overview of the tree you're building.
In particular, given an existing tree plus
next bit to hash, I don't know how to resort
to English prose to learn about appropriate tree update.
I saw no diagrams of example trees.
I understand that you were trying to communicate
the details to me, but in this particular instance
communication was not successful.