对于给定的情况,什么是好的哈希函数？

Question

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

Answer 1

这是不可能的,因为共线性不是传递性的.即,让我们说AB和C在一条线上(即共线).因此,AB和C应该获得相同的散列键.接下来,CD和E也位于另一条线上.因此,CD和E也应该获得相同的散列键.因此,AB接收与D和E相同的散列密钥,这是错误的,因为这些点不是共线的.

此外,共线性是根据点集定义的,因此我的上述定义相当模糊.即你不能说A和B是共线的(嗯,你可以,但如果你只考虑两点,每对点是共线的).

你可以做的是将一组共线点保存在哈希映射中.然后,良好的散列函数将简单地包括斜率s和纵坐标i.例如,您可以使用s*31i.此哈希映射可用于向集合添加新点,并最终计算集合的大小以检索您的答案.