针对特定数据结构的无碰撞哈希函数

Question

是否可以为具有特定属性的数据结构创建无冲突哈希函数。

1. 数据结构是 int[][][]
2. 它不包含重复项
3. 定义了其中包含的整数范围。假设它是 0..1000，最大整数肯定不会大于 10000。

最大的问题是这个哈希函数也应该非常快。 有没有办法创建这样的哈希函数？也许在运行时取决于整数范围？

另外：我应该说这个哈希函数的目的是快速检查特定组合是否已被处理。因此，当处理数据结构中的某些数字组合时，我计算哈希值并存储它。然后，当处理数据结构中的另一个数字组合时，我将比较哈希值。

Answer 1

我认为你想要的是“完美哈希”甚至“最小完美哈希”：

http://en .wikipedia.org/wiki/Perfect_hash_function

编辑：也就是说，如果你确信并且确定你永远不会超过 [0...1000] 并且根据你需要做什么，你可能可以简单地“将结果直接存储在数组中。如果你没有很多元素，该数组将是稀疏的（因此有点浪费），但最多 1001 个元素来自 [0...1000] 一个 Object[1001] （或 int[1001] 或无论如何）可能会做。

Answer 2

如果您只使用 64 位值并将层次结构每一层中的位置存储到一个位段中会怎样？

类似的东西（在我的脑海中）：hash = (a << 34) | (b << 17) | （三）

Answer 3

完美的哈希可能不可行，因为为您的数据集找到一个完美的哈希可能需要大量的计算时间。

bool[][][] 是否适合您，其中 true 表示某个 x,y,z 组合已被处理？下面是三维位数组的原型。由于 Int32 的限制，这最多只能工作到大约 1,024 的最大索引（但适合 128 MB）。通过创建 BitArray[][] 可以达到 10,000。但是，这对于该大小可能不切实际，因为它将占用超过 116 GB 的 RAM。

根据您的具体问题大小和需求，普通的旧哈希表（有冲突）可能是您的最佳选择。也就是说，这是原型代码：

public class ThreeDimensionalBitArray
{
    // todo: consider making the size configurable
    private const int MAX_INDEX = 1000;

    private BitArray _bits = new BitArray(MAX_INDEX * MAX_INDEX * MAX_INDEX);

    public bool this[int x, int y, int z]
    {
        get { return _bits[getBitIndex(x, y, z)]; }
        set { _bits[getBitIndex(x, y, z)] = value; }
    }

    public ThreeDimensionalBitArray()
    {
    }

    private static int getBitIndex(int x, int y, int z)
    {
        // todo: bounds check x, y, and z

        return (x * MAX_INDEX * MAX_INDEX) + (y * MAX_INDEX) + z;
    }
}


public class BitArrayExample
{
    public static void Main()
    {
        ThreeDimensionalBitArray bitArray = new ThreeDimensionalBitArray();
        Console.WriteLine(bitArray[500, 600, 700]); // "false"
        bitArray[500, 600, 700] = true;
        Console.WriteLine(bitArray[500, 600, 700]); // "true"
    }
}