特定数组的散列

Question

我有一个非常特殊的问题，我想有效地解决。

几何由V卷定义，编号从0到V-1.每个体积都有不同的曲面，编号从0到N1)。

                            Volume | Surfaces
                            --------------------
Geometry A (V=2, N=7):      0      | [0 3 5 6 2] 
                            1      | [5 4 2 1]
                            2      | [4 0 1 3 6]

请注意，曲面将只在卷中出现一次。另外，曲面最多是一个几何的2卷。

以下是问题所在：

我对相同的基本几何有两种不同的描述，我想找出几何A中的哪个体积对应于几何B中的哪个体积。换句话说，我有相同的N个曲面，但V体积的定义不同。

这里有一个几何B，它可以对应于上面的几何A：

                             Volume | Surfaces
                            --------------------
Geometry B (V=2, N=7):      0      | [1 5 4 2]
                            1      | [3 6 5 0 2] 
                            2      | [0 1 3 6 4]

给定几何A和B，我希望能够将几何A的每一个体积与其对应的几何B中的体积结合起来，这是最有效的。

A   0  1  2
B   1  0  2

解决办法草案：

按升序或降序对每个面数组进行排序，而不是按照其表面的字典顺序对每个卷进行排序。这个问题很容易得到很好的解决。

更好的解决办法：

为每个数组计算一个快速、唯一的散列，而不是在此散列之后排序卷。散列不应依赖于数组中曲面的顺序。

为什么我认为散列可以是一个很好的解决方案？

取散列(体积)=最小(表面)

这个散列最多有一个碰撞，因为一个曲面只能出现在两个卷中！

现在，如果我取散列(体积)=最小(曲面)+最大(曲面)*N，我最多还有1次碰撞，但是当有大量的体积和曲面时，概率变得非常小。

Answer 1

我找到了一个很好的散列函数，它几乎不应该有冲突：

V: [S_0 S_1 S_2 S_3...S_N-1]

u64 hash(V) = 0;
for i in {0..N-1} :
    hash(V) = hash(V) ^ (1<<(S_i & 63))
end

这提供了一个唯一的64位数，并且所有的数字都是可能的(不像Omg的解决方案，大多数数字是不可能得到的，因为表面列表中没有重复)

在发生冲突的极端情况下(在排序后我会看到)，我将以愚蠢的方式按字典顺序比较数组。

Answer 2

如前所述，您的解决方案很好地逼近了您想要的东西。但是，如果您寻求一个完美的哈希函数，则可以使用以下方法：

假设p_i是第一个素数，使得p_0 = 2，p_1 = 3，p_2 = 5，p_3 = 7，p_4 = 11，p_5 = 13，p_6 = 17，p_7 = 19 .我们可以在x_0，x_1，.，x_k上定义一个散列函数，使h(x_0，.，x_k) = p_{x_0} p_{x_1} .p_{x_k}另外，对于重复数，我们可以将重复数作为p_{x_i}的幂。例如，如果x_i重复3次，则p_{ x_i }在h中的幂为p_{x_i}^3。如果x_i的重复次数为a_i，则h(x_0，.，x_k) = p_{x_0}^{a_0} p_{x_1}^{a_1} .p_{x_k}^{a_k}

因此，对于几何A，我们有：

                    Volume |      Surfaces     | Hash
                    ----------------------------------
  geometry A           0   | [0, 3, 5, 6, 2]   | 2 * 7 * 13 * 17 * 5 = 15470 
                       1   | [5, 4, 2, 1]      | 13 * 11 * 5 * 3 = 2145
                       2   | [4, 0, 1, 3, 6]   | 11 * 2 * 3 * 7 * 17 = 7854

和几何学B的类似方式。由于这个函数为每个数组返回一个唯一的值(而不关心顺序)，您可以使用对应的散列值来排列曲面。如果N的值不大，则可以使用素数的预先计算的列表。