hash function providing unique uint from an integer coordinate pair

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.

hash hashtable

Edit Report

You can do

a >= b ? a * a + a + b : a + b * b

taken from here.

That works for points in positive plane. If your coordinates can be in negative axis too, then you will have to do:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

But to restrict the output to uint you will have to keep an upper bound for your inputs. and if so, then it turns out that you know the bounds. In other words in programming its impractical to write a function without having an idea on the integer type your inputs and output can be and if so there definitely will be a lower bound and upper bound for every integer type.

public uint GetHashCode(whatever a, whatever b)
{
    if (a > ushort.MaxValue || b > ushort.MaxValue || 
        a < ushort.MinValue || b < ushort.MinValue)
    {    
        throw new ArgumentOutOfRangeException();
    }

    return (uint)(a * short.MaxValue + b); //very good space/speed efficiency
    //or whatever your function is.
}

If you want output to be strictly uint for unknown range of inputs, then there will be reasonable amount of collisions depending upon that range. What I would suggest is to have a function that can overflow but unchecked. Emil's solution is great, in C#:

return unchecked((uint)((a & 0xffff) << 16 | (b & 0xffff)));

See Mapping two integers to one, in a unique and deterministic way for a plethora of options..

answered 2012-12-27T08:37:11.277

hash function providing unique uint from an integer coordinate pair

1 Answer

Your Answer