5

I wonder if there is a general all-around solution for a hash map for coordinates (in 2d or 3d, i.e. a vector of doubles)?

An example here demonstrates how to create a custom hash-map for pair<int,int>, but it does not seem to be trivial to come-up with an unique map from pair<double,double> (which could represent a 2d coordinate) to size_t.

I know that i can use ordered maps by providing comparator object, but for my application there is no need to order them and hash-maps seems to be faster anyway. However since i'm a newcomer to all this hash stuff, i am kind of lost on how to proceed.

p/s/ i use c++11.

Community
  • 1
  • 1
Denis
  • 1,526
  • 6
  • 24
  • 40
  • 1
    Why can't you use the same approach in the link you provided? It seems trivial to use `pair` instead of `pair`, and since you don't need ordering you can still use `std::unordered_map`. – André Neves May 28 '13 at 13:30
  • @André because the map is not unique. – Denis May 28 '13 at 13:35
  • If I am not mistaken, you cannot have multiple equal keys in the `std::unordered_map`. You can however have different keys map to the same value. So, the keys themselves are unique. Could you describe your problem a little bit better? – André Neves May 28 '13 at 13:40
  • Frankly, i don't yet have a problem. I just assumed that the map should be unique, therefore mapping `(double)*100+(double)` to `int` is not unique. But maybe that's all right. As i said, i'm a newcomer to hash stuff. – Denis May 28 '13 at 13:42
  • you are correct, the hash should be unique and you should devise a way to avoid collisions depending on your data ranges, or use a good hashing method. – André Neves May 28 '13 at 13:47

4 Answers4

5

To avoid extra dependencies, you can use std::hash. Here's an example using the code from the link you posted, and updated to use a std::pair<double,double>:

#include <unordered_map>
#include <cassert>

using namespace std;

class TPoint3D{
public:
    TPoint3D(double x, double y, double z) : x(x), y(y), z(z){};

    double x, y, z;
};

struct hashFunc{
    size_t operator()(const TPoint3D &k) const{
    size_t h1 = std::hash<double>()(k.x);
    size_t h2 = std::hash<double>()(k.y);
    size_t h3 = std::hash<double>()(k.z);
    return (h1 ^ (h2 << 1)) ^ h3;
    }
};

struct equalsFunc{
  bool operator()( const TPoint3D& lhs, const TPoint3D& rhs ) const{
    return (lhs.x == rhs.x) && (lhs.y == rhs.y) && (lhs.z == rhs.z);
  }
};

typedef unordered_map<TPoint3D, int, hashFunc, equalsFunc> TPoint3DMap;

int main(){
  TPoint3DMap myMap;

  // test equalsFunc
  myMap[TPoint3D(10.0, 20.0, 30.0)] = 100;
  myMap[TPoint3D(10.0, 20.0, 30.0)] = 200;

  assert(myMap[TPoint3D(10.0, 20.0, 30.0)] == 200);

  // test if hashFunc handles well repeated values inside TPoint3D
  myMap[TPoint3D(10.0, 10.0, 10.0)] = 1;
  myMap[TPoint3D(10.0, 20.0, 10.0)] = 2;
  myMap[TPoint3D(10.0, 10.0, 20.0)] = 3;
  myMap[TPoint3D(20.0, 10.0, 10.0)] = 4;

  assert(myMap[TPoint3D(10.0, 10.0, 10.0)] == 1);
  assert(myMap[TPoint3D(10.0, 20.0, 10.0)] == 2);
  assert(myMap[TPoint3D(10.0, 10.0, 20.0)] == 3);
  assert(myMap[TPoint3D(20.0, 10.0, 10.0)] == 4);

  return 0;
}

As I said before, if you wish to use another structure you have to adapt both the pairHash class and pairEquals struct operator() to appropriately hash and compare the new keys, respectively.

Cheers

EDIT :

  • Modified code to use custom TPPoint3D class and uniform functor classes definitions (both using struct).
  • Added simple tests to validate the hash and equals functors.
André Neves
  • 1,066
  • 10
  • 14
  • thanks for reply, that's probably what i was looking for. What would be the best extension to 3D: `(h1^(h2<<1))^h3` ? – Denis May 29 '13 at 15:58
  • @Denis: Yes, I think that would work. However, I think @Timothy Shields' solution is more elegant and easily extensible. I didn't know myself that `std::tuple<>` already defined equality and compare functions automatically. You just have to create your map of tuples and it will just work for 2D, 3D, ..., nD :) Still, attention to the fact Timothy mentioned that the lookup must be _exact_, which means all the items in the tuple must be _exactly_ the same (value) for the keys to be considered equal and for the map to work as you expect. – André Neves May 29 '13 at 16:30
  • @AndreNevas thanks for reply. Maybe i miss something, but i don't see how could i apply his solution to an arbitrary given class (other than std::tuple). – Denis May 29 '13 at 17:27
  • @Denis: what he says is that `std::tuple` automatically uses the equality and hash functions of the types _it contains_ to perform the equality and hash functions of the tuple _itself_ **as a whole**. If you use a custom class as an element of the tuple, you will have to provide the equality and hash functions yourself for that class, I guess. For `double` though (which is what we thought you needed), `std::tuple` will work out of the box since it's a built in type. – André Neves May 29 '13 at 19:27
  • sorry for not being clear, my custom class is actually something like `class TPoint()` which, say, has `point.x` and `point.y`. So i want to use it. I can easily use it in `std::map`, but i though of moving to `unordered_map` instead, if i can make it work. – Denis May 30 '13 at 10:21
  • In that case I think you will have to define your own hash and compare functions as mentioned in my solution. [Here](http://stackoverflow.com/a/15809592/1921751) you have other ways to define these functions. – André Neves May 30 '13 at 11:03
4

I cannot comment on Andre's answer because I do not have enough reputation yet, but anyone trying to create a hash function using ^ (XOR) should note that XOR is associative. In other words a ^ (b ^ c) == (a ^ b) ^ c. This means that

(h1 ^ (h2 << 1)) ^ h3

which is the return value of Andre's answer, is the same as:

h1 ^ ((h2 << 1) ^ h3)

which itself is, due to the commutative nature of XOR (a ^ b == b ^ a), equivalent to:

(h3 ^ (h2 << 1)) ^ h1

What all of this means is that the hash method I am referring to will, for distinct a, b, and c, return the same hash for (a,b,c) as it will for (c,b,a). In other words the x and z coordinates are order independent / insensitive.

Depending on how you are using this hash method this might not be a problem. However, if for example the points you were hashing were aligned to a grid you would receive an inordinate number of hash collisions.

I would replace the expression in the return statement in Andre's answer with the one below. This should be order dependent / sensitive.

(h1 ^ (h2 << 1)) ^ (h3 << 2)
Garrett Gutierrez
  • 747
  • 3
  • 16
  • i don't see how `int hashFunc(int h1,int h2,int h3){return h1 ^ (h2<<1) ^ (h3<<2);}` would work as a hash function either. cause `hash(4,0,0) = 4`, `hash(0,2,0) = 4`, `hash(0,0,1) = 4`, `hash(4,2,1) = 4` etc... so there's many coords (in a shifted/xor'd pattern) that will give the same hash. – Puddle Aug 08 '19 at 21:07
2

In the 3D case,std::unordered_map<std::tuple<double, double, double>, your_value_type> should work fine for you, assuming you are doing exact lookups. std::tuple<...> defines equality and hash functions for you, based on the equality and hash functions of the types it is aggregating.

The 2D case is of course the same, but using a std::tuple<double, double>.

Edit: Sorry for misinformation. There actually is not a default hash defined for std::tuple. To use this approach, you would have to define a hash_tuple templated functor class and then use that in the std::unordered_map. Other answers show how to do that part.

Timothy Shields
  • 75,459
  • 18
  • 120
  • 173
  • thanks for the reply. Can one look at implemented hash for touple, or is this information not disclosed? I'm apply this to already written class in third-party library, so i would prefer not to use std::tuple. – Denis May 29 '13 at 15:55
  • This is the best solution presented so far and you will essentially only need one line to define your entire data structure. – André Neves May 29 '13 at 16:39
  • @TimothyShields tried your solution in another context, it seems hash is not provided by default: `static assertion failed: std::hash is not specialized for this type`, at least for `std::unordered_map,double >` – Denis Jun 19 '13 at 08:08
  • @Denis Yeah, I've learned the same thing since. Only comparisons are provided for tuples. Defining a hash_tuple templates functor and using that won't be hard though. Other answers suggest how to implement the hash. – Timothy Shields Jun 19 '13 at 12:35
  • @TimothyShields sure, it's not hard to implement. I actually used the first answer, but just wanted to be sure that i didn't overlook something and there is indeed no default hash for tuples – Denis Jun 19 '13 at 12:40
1

What about using hash_combine from Boost?

http://www.boost.org/doc/libs/1_53_0/doc/html/hash/combine.html

bluescarni
  • 3,937
  • 1
  • 22
  • 33