Efficient way to hash a 2D point

Question

OK, so the task is this, I would be given (x, y) co-ordinates of points with both (x, y) ranging from -10^6 to 10^6 inclusive. I have to check whether a particular point e.g. (x, y) tuple was given to me or not. In simple words how do i answer the query whether a particular point(2D) is set or not. So far the best i could think of is maintaining a std::map<std::pair<int,int>, bool> and whenever a point is given I mark it 1. Although this must be running in logarithmic time and is fairly optimized way to answer the query I am wondering if there's a better way to do this.

Also I would be glad if anyone could tell what actually complexity would be if I am using the above data structure as a hash.I mean is it that the complexity of std::map is going to be O(log N) in the size of elements present irrespective of the structure of key?

It's been long since I got an answer for my question. Please don't flag this right away :( — Aditya Bahuguna, Oct 05 '14 at 20:23
`std:map` is normally implemented using a balanced binary tree, not a hash table. You can use a `std:unordered_map` if you do not care about the ordering of the elements in the map (which you do not seem to do). — Martin Liversage, Oct 05 '14 at 20:33
I am getting a pile of errors when i use std::unordered_map, please help me here!! — Aditya Bahuguna, Oct 05 '14 at 21:00
*I am getting a pile of errors when i use std::unordered_map, please help me here!!* You need to be more specific than that in order to get any help. — Martin Liversage, Oct 05 '14 at 21:06
Ok, the structure of my std::unordered_map is unordered_map , int> MAP; , I am inserting a key using MAP[make_pair(x, y)] = value; , I am getting these errors when compiling with C++11, /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of ‘struct std::hash >’ struct hash; — Aditya Bahuguna, Oct 05 '14 at 21:14
Actually the error list is too long, I'm posting it in question.!! — Aditya Bahuguna, Oct 05 '14 at 21:15

score 6 · Accepted Answer · edited May 23 '17 at 12:07

6

In order to use a hash map you need to be using std::unordered_map instead of std::map. The constraint of using this is that your value type needs to have a hash function defined for it as described in this answer. Either that or just use boost::hash for this:

std::unordered_map<std::pair<int, int>, boost::hash<std::pair<int, int> > map_of_pairs;

Another method which springs to mind is to store the 32 bit int values in a 64 bit integer like so:

uint64_t i64;
uint32_t a32, b32;
i64 = ((uint64_t)a32 << 32) | b32;

As described in this answer. The x and y components can be stored in the high and low bytes of the integer and then you can use a std::unordered_map<uint64_t, bool>. Although I'd be interested to know if this is any more efficient than the previous method or if it even produces different code.

edited May 23 '17 at 12:07

Community

1
1

answered Oct 05 '14 at 21:17

sjdowling

2,994
2
21
31

Thanx, @Martin Liversage mentioned using this but I was getting weird errors which is explained by the constraints u mentioned on value type, I am working on it – Aditya Bahuguna Oct 05 '14 at 21:19
Well I tried the method for which u gave the link, by defining a hash function, and it worked, execution time decreased to 75% of original(roughly)! – Aditya Bahuguna Oct 05 '14 at 21:25
That's good to hear, I'm a big fan of hash maps, they can be less efficient if the hashing function is onerous and the map is small but generally O(1) is pretty hard to argue with. – sjdowling Oct 05 '14 at 21:32

score 5 · Answer 2 · edited May 23 '17 at 12:16

Instead of mapping each point to a bool, why not store all the points given to you in a set? Then, you can simply search the set to see if it contains the point you are looking for. It is essentially the same as what you are doing without having to do an additional lookup of the associated bool. For example:

set<pair<int, int>> points;

Then, you can check whether the set contains a certain point or not like this :

pair<int, int> examplePoint = make_pair(0, 0);
set<pair<int, int>>::iterator it = points.find(examplePoint);

if (it == points.end()) {
    // examplePoint not found
} else {
    // examplePoint found
}

As mentioned, std::set is normally implemented as a balanced binary search tree, so each lookup would take O(logn) time.

If you wanted to use a hash table instead, you could do the same thing using std::unordered_set instead of std::set. Assuming you use a good hash function, this would speed your lookups up to O(1) time. However, in order to do this, you will have to define the hash function for pair<int, int>. Here is an example taken from this answer:

namespace std {
template <> struct hash<std::pair<int, int>> {
    inline size_t operator()(const std::pair<int, int> &v) const {
        std::hash<int> int_hasher;
        return int_hasher(v.first) ^ int_hasher(v.second);
    }
};

}

Edit: Nevermind, I see you already got it working!

Ya, thats cool enough, I could have used std::set, how come it never occurred to me :P. Ya i got it working , anyways thanx for the answer. — Aditya Bahuguna, Oct 09 '14 at 10:57

Efficient way to hash a 2D point

2 Answers2

Linked