Subj : Re: Multi-dimensional data structure
To   : comp.programming
From : Googmeister
Date : Wed Oct 12 2005 07:22 am


Adi wrote:
> In general, I don't know if hashing works for the same reasons that you
> outline above.
>
> xor(a, a, b) = xor(c, c, b).
>
> I can guarentee that I won't be using duplicates such as in the example
> above but I still get the same problem in the following situation
>
> A = 0101
> B = 1000
> C = 1101
> D = 1111
> E = 1010
>
> xor(A, B, C) = xor(A, D, E)

You should expect collisions with hashing - that's not a problem.
Perhaps you misunderstand how hashing is supposed to work.

The basic assumption when analyzing hashing is that each
key maps to a random slot. Under this idealized assumption,
the expected number of collisions is sufficiently low.

The potential problem with xor'ing the keys is that it can
lead to collision pile-ups, e.g., if the keys were (x, x, A)
for different value of x, then all the keys would collide. It's
not always a problem, but something to be aware of.

.