Thread: Hashing function

What data type would x and y be?

I think it depends more on the distribution of points.

For example, if the points are random and fairly sparse then it might be good to just sort by x or y-coordinate. Also if the points tend to fall in a line then you could sort by the axis parallel to that line.
If the points tend to group together or form perpendicular lines, though, that could be rather inefficient. You'd have to try something else, and knowing where the data comes from is probably the best way to know how to hash it well.

You could also represent the coordinates as a long int, specifically:

Code:

long int coord = ((long int)x << 16) + y;

and use a standard hash function on that.

In case you're having trouble deciding over the hashes in the above link. The FNV-1a hash is often a good choice.

Or if I needed something really fast, I'd be temped to do:

Code:

hash = ((x * prime1 + prime2) ^ y) * prime3 + prime4;

Where primes 1 through 4 are values often found in LCRNGs.

In the past, I've used a 64-to-32-bit downmixing function for this. See the section on this page called "64 bit to 32 bit Hash Functions". You pack your two 32-bit coordinates into a single 64-bit long value, pass it to this function, and out comes a 32-bit hash result.

Another possibility would be the 3-way 32-bit mixer on the same page in section "Robert Jenkins' 96 bit Mix Function" -- it takes three inputs. Two of those inputs would be your coordinates, the third input is some random (but fixed) value.