c++ - 给定情况下好的散列函数是什么？

Question

在二维平面中给出了一个点，我想计算最大共线点，因为我计算了所有可能的直线斜率及其截距。为了解决这个问题，我试图建立一个哈希表，但我无法找到一个哈希函数，通过它我可以轻松地将所有共线点指向一个哈希键。所以帮我找出适合这种情况的哈希函数？

Answer 1

这是不可能的，因为共线性是不可传递的。即，假设 A B 和 C 位于一条线上(即共线)。因此，A B 和 C 应该得到相同的散列键。接下来，C D 和 E 也位于另一条线上。因此，C D 和 E 也应该得到相同的散列键。因此，A B 收到与 D 和 E 相同的哈希键，这是错误的，因为这些点不共线。

另外，共线性是在点集上定义的，所以我上面的定义比较模糊。 IE。你不能说 A 和 B 是共线的(好吧，你可以，但是如果你只考虑两个点，那么每对点都是共线的)。

您可以做的是将共线点集保存在 HashMap 中。那么，一个好的散列函数将仅由斜率 s 和纵坐标截距 i 组成。例如，您可以使用 s * 31i。此 HashMap 可用于向集合中添加新点，并最终计算集合的大小以检索您的答案。