5 ms·
It's not too difficult: hash function 1 generates an integer from 0 to n-1, that index element is deleted, then hash function 2 generates an integer from 0 to n
by ReaLNero 6y ago
It's not too difficult: hash function 1 generates an integer from 0 to n-1, that index element is deleted, then hash function 2 generates an integer from 0 to n-2, that element is deleted etc.
This is an O(n^2) algorithm, which you can improve to O(nlgn) using fenwick trees.
In practice however, it is much quicker to generate random hashes and repeat until they're distinct.
- anonymoushn 6y agoIn k^2 time, which is maybe faster than running a hash an additional time: function get_bits(input, hashes, n) local bits = {} for i=1,#hashes do local bit = hashes[i](input) % (n-i+1) for j=1,i-1 do if bits[j] <= bit then bit = bit + 1 end end bits[i] = bit while i > 1 and bits[i] < bits[i-1] do bits[i], bits[i-1] = bits[i-1], bits[i] i = i - 1 end end return bits end
- marcan_42 6y agoYour % operation is not uniformly distributed if the hash domain isn't an integer multiple of the output size, which is a bigger problem for formal correctness than the colliding output issue (hashes are not uniformly distributed). You need to truncate to an even number of bits and retry until the output is < n, at which point you're retrying anyway, so you can just retry on collision instead of having all that complicated logic to skip bits. Nice try though, but if you want formally perfect results like the OP you have to try harder :-) (except real hash functions are only assumed to have perfectly distributed functions anyway, that is not proven and probably not provable, so basically you're screwed either way and none of this matters :-) ).