散列2D点的有效方法

Question

好，所以任务就是这样，我将得到点（x，y）的坐标，且两个（x，y）的范围都在-10 ^ 6到10 ^ 6之间。我必须检查是否给了我一个特定的点，例如（x，y）元组。简而言之，我如何回答查询是否设置了特定的point（2D）。到目前为止，我能想到的最好的方法是维持a，std::map<std::pair<int,int>, bool>并在给出点时将其标记为1。 。

如果有人使用上述数据结构作为哈希表，那么如果有人能说出实际上复杂度是多少，我也会很高兴。我的意思是，std::map无论元素的大小如何，其复杂度都将是O（log N）钥匙的结构？

Answer 1

为了使用哈希映射，您需要使用std::unordered_map而不是std::map. 使用此功能的限制是您的值类型需要为其定义一个哈希函数，如本答案中所述。或者使用boost::hash来实现：

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

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

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

正如这个答案中所描述的。x 和 y 分量可以存储在整数的高字节和低字节中，然后您可以使用std::unordered_map<uint64_t, bool>. 尽管我很想知道这是否比以前的方法更有效，或者它是否甚至产生不同的代码。

Answer 2

与其将每个点映射到布尔值，不将所有给定的点存储在集合中？然后，您可以简单地搜索集合以查看它是否包含您要寻找的点。它与您所做的基本相同，而无需额外查找关联的布尔。例如：

set<pair<int, int>> points;

然后，您可以像这样检查集合是否包含某个点：

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
}

如前所述，std::set通常实现为平衡的二进制搜索树，因此每次查找将花费O（logn）时间。

如果您想改用哈希表，则可以使用std::unordered_set代替做同样的事情std::set。假设您使用了良好的哈希函数，这将使您的查询速度最多提高O（1）倍。但是，为此，您必须为定义哈希函数pair<int, int>。下面是取自一个例子这个答案：

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);
    }
};

}

编辑：没关系，我看到您已经开始使用它了！