rlbond - 4 months ago 21

C++ Question

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`

`Column`

`int`

Right now I use a

`set`

`unordered_set`

So, I want to have an

`unordered_set`

`Point`

`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.