The problem in general: I have a big 2d point space, sparsely populated with dots. Think of it as a big white canvas sprinkled with black dots. I have to iterate over and search through these dots a lot. The Canvas (point space) can be huge, bordering on the limits of int and its size is unknown before setting points in there.
That brought me to the idea of hashing:
Ideal: I need a hash function taking a 2D point, returning a unique uint32. So that no collisions can occur. You can assume that the number of dots on the Canvas is easily countable by uint32.
IMPORTANT: It is impossible to know the size of the canvas beforehand (it may even change), so things like
canvaswidth * y + x
are sadly out of the question.
I also tried a very naive
abs(x) + abs(y)
but that produces too many collisions.
Compromise: A hash function that provides keys with a very low probability of collision.
a hash function that is GUARANTEED collision-free is not a hash function :)
Instead of using a hash function, you could consider using binary space partition trees (BSPs) or XY-trees (closely related).
If you want to hash two uint32's into one uint32, do not use things like Y & 0xFFFF because that discards half of the bits. Do something like
(x * 0x1f1f1f1f) ^ y
(you need to transform one of the variables first to make sure the hash function is not commutative)