整数序列的完美哈希函数

Question

给定一组整数（序列）1…999_999（例如）我需要将每个单独的整数随机映射到同一组 1:1 中的另一个整数（分布取决于种子） .哈希函数必须可扩展到大型集合，因此不能将所有值混洗并存储在内存中。有什么好的方法吗？

一些示例：


// 1..3 seq
lowerBound = 1;
upperBound = 3;

seed = 1

h1 = makeHashFn(lowerBound, upperBound, seed)

h1(1) // 2
h1(2) // 3
h1(3) // 1

newSeed = 2

h2 = makeHashFn(lowerBound, upperBound, newSeed)

h2(1) // 3
h2(2) // 1
h2(2) // 2

Answer 1

如果不使用任何类型的内存，则无法执行此操作。

如果您对数字冲突的发生感到高兴，那是有可能发生的，否则，您就不能真正让它成为随机的和无状态的。

不过，您可以做的是随机排列所有索引的列表。每个列表元素只有 4 或 8 个字节，这对于大多数应用程序来说是相当合理的。

如果您使用确定性种子 RNG 来打乱索引，则每次结果都是相同的，在这种情况下，您不需要存储打乱后的索引，而是可以重新生成它们并将它们丢弃为满足您的内存要求。

没有任何灵丹妙药，这个问题的每一个解决方案都会有重大的权衡。如果你有一个包含数十亿条目的超大数据库，最好退后一步，以更有效的方式重新定义问题。

整数序列的完美哈希函数

Perfect hash function for integer sequence

hash

hash-function