rlbond rlbond - 2 months ago 7
C++ Question

Good hash function for a 2d index

I have a struct called Point. Point is pretty simple:

struct Point
{
Row row;
Column column;

// some other code for addition and subtraction of points is there too
}


Row
and
Column
are basically glorified
int
s, but I got sick of accidentally transposing the input arguments to functions and gave them each a wrapper class.

Right now I use a
set
of points, but repeated lookups are really slowing things down. I want to switch to an
unordered_set
.

So, I want to have an
unordered_set
of
Point
s. Typically this set might contain, for example, every point on a 80x24 terminal = 1920 points. I need a good hash function. I just came up with the following:

struct PointHash : public std::unary_function<Point, std::size_t>
{
result_type operator()(const argument_type& val) const
{
return val.row.value() * 1000 + val.col.value();
}
};


However, I'm not sure that this is really a good hash function. I wanted something fast, since I need to do many lookups very quickly. Is there a better hash function I can use, or is this OK?

Answer

Following the technique is given in Effective Java (2nd edition), and quoted from there in Programming in Scala. Have a prime constant (we'll say 53 but you may find something larger will give more even distribution here), and perform multiplication and addition as follows:

(53 + int_hash(row)) * 53 + int_hash(col)

For more values (say you add a z coordinate), just keep nesting, like

((53 + int_hash(row)) * 53 + int_hash(col)) * 53 + int_hash(z)

Where int_hash is a function for hashing a single integer. You can visit this page to find a bunch of good hash functions for single integers.