高效的二维点散列方式 [英] Efficient way to hash a 2D point

问题描述

所以这个任务就是这样，我给予（x，y）坐标坐标（x，y），范围从-10 ^ 6到10 ^ 6。我必须检查一个特定的点，例如（x，y）元组被赋予给我。简单来说，如何回答查询是否设置了特定点（2D）。到目前为止，我可以想到的最好的是维护一个 std :: map< std :: pair< int，int>，bool> 虽然这必须以对数时间运行，并且是相当优化的方式来回答查询，我想知道是否有更好的方法来做到这一点。

另外我会如果有人可以告诉我如果使用上面的数据结构作为一个hash，那么实际的复杂度是多么高兴。我的意思是， std :: map 的复杂性将会不管密钥的结构如何，都是O（log N）的元素大小？

解决方案

为了使用哈希map需要使用 std :: unordered_map 而不是 std :: map 。使用这一点的限制是，您的值类型需要为其定义的哈希函数，如此答案所述。或者只是使用 boost :: hash 这个：

std :: unordered_map< std :: pair< int，int>，boost :: hash< std :: pair& INT> > map_of_pairs;

另一个令人想到的方法是将64位int值存储在64位整数中，如下所示：

  uint64_t i64; 
 uint32_t a32，b32; 
 i64 =（（uint64_t）a32< 32）| B32; 
  

如这个答案。 x和y组件可以存储在整数的高字节和低字节中，然后可以使用 std :: unordered_map< uint64_t，bool> 。虽然我有兴趣知道这是否比以前的方法更有效，或者甚至生成不同的代码。

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?

解决方案

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.

这篇关于高效的二维点散列方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！