通过给定点的最小线数

Question

首先，我已经为 Point2D 定义了 operator== 并专门化了 struct hash<Point2D> 模板 class 以便能够将位于同一行上的点视为非唯一点.

在下面的代码中，我在同一行上生成了 1000 个随机点，并检查它们是否相等，然后我打印了 is equal: 1 1000 次，但最后，它被打印 2. 当我试验 hash 函数和 return 任何注释值时，unordered_set 的大小变为 1（即使我 return哈希函数）。那么我下面的哈希函数有什么问题？

#include <cmath>
#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
#include <set>
#include <string>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <functional>
#include <stack>
#include <queue>
#include <random>
using namespace std;


struct Point2D
{
    int x;
    int y;

    bool operator==(const Point2D& other) const
    {
        return x * other.y == y * other.x;
    }
};

namespace std
{
    template <>
    struct hash<Point2D>
    {
        std::size_t operator()(const Point2D& k) const
        {
            // Compute individual hash values for first,
            // second and combine them using XOR
            // and bit shifting:
            return ((hash<int>()(k.x) ^ (hash<int>()(k.y) << 1)) >> 1);

            /*
            int i1 = k.x;
            int i2 = k.y;
            size_t ret = i1;
            ret *= 2654435761U;
            return ret ^ i2;
            */

            /*
            return 111;
            */
        }
    };

}

int solution(vector<Point2D> &A)
{
    unordered_set<Point2D> pointsOnTheSameLine;

    for (auto& point : A)
    {
        pointsOnTheSameLine.insert(point);
    }

    return static_cast<int>(pointsOnTheSameLine.size());
}

int main()
{
    std::random_device rd;     // only used once to initialise (seed) engine
    std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
    std::uniform_int_distribution<int> uni(-10000, 10000); // guaranteed unbiased

    int x = 13;
    int y = 7;
    vector<Point2D> v; // { {0, 1}, {0, 2}, {1, 1}, {-1, -1} };
    for (int i = 0; i < 1000; ++i)
    {
        auto random_integer = uni(rng);
        const Point2D curr{x * random_integer, y * random_integer};
        v.push_back(curr);

        cout << "is equal: " << (Point2D{x, y} == curr) << endl;
    }



    cout << solution(v) << endl;

    return 0;
}

哈希函数如何影响结果。它会影响我的程序运行时间，因为根据散列函数的不同，可能会有或大或小的冲突，但我的程序应该 return 相同的结果，对吧？

Answer 1

问题可能在于某些相等的点（Point2D::operator== 为真）在您的代码中产生了不同的哈希值。

相等的点应产生相同的哈希值。

Answer 2

I expect to get 1, as according the my operator== all the generated points are equal

根据 == 的相等性不足以让散列容器认为所有点都相等：散列函数还必须 return 相同的点值被认为是相等的。当哈希值不同时，无序容器甚至不会将您的 operator== 应用于存储的值，这会导致您看到的结果。

实现此目的的一种方法是通过除以 gcd 和 xor-ing 分子与分母来计算斜率：

int gcd (int a, int b){
    a = abs(a); b = abs(b);
    return (b==0) ? a : gcd(b, a%b);
}

std::size_t operator()(const Point2D& k) const {
    int g = gcd(k.x, k.y);
    int a = k.x/g, b = k.y/g;
    return a ^ b;
}

Demo.

通过给定点的最小线数

Minimum count of lines that goes through the given points

c++

algorithm

hash

unordered-set