hashmap for 2d(3d) coordinates (i.e. vector of doubles)?

Question

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.

Answer 1

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.

Answer 2

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)