algorithm - 特定数据结构的无冲突哈希函数

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

像（我的头顶）：hash = (a << 34) | (b << 17) | (c)

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"
    }
}