Good hash function for a 2d index
Posted
by rlbond
on Stack Overflow
See other posts from Stack Overflow
or by rlbond
Published on 2010-04-14T03:25:30Z
Indexed on
2010/04/14
3:33 UTC
Read the original article
Hit count: 407
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?
© Stack Overflow or respective owner