基数范围内整数的最小完美散列

Question

我正在寻找一个简单的散列函数，该函数将采用基数为 2 的范围内的整数，并（随机）散列到该范围内的另一个整数而不会发生冲突。这将用于构建排列，最好是从种子值构建排列。所以仅仅抵消整数和调制是行不通的。有人知道用 C 编写的一个好的选项吗？

谢谢，乔什

Answer 1

这可能会有所帮助（请参阅底部以获得更通用的方法）：multiplicative cyclic groups allow you to pick a k "seed" value, a n "maximum" value, and permutate the natural numbers from zero to n-1 in a very efficient way (k can be in Z but preferibly both natural numbers). The only gotcha, if you want a permutation, is that n has to be a prime number, and I'm not sure if all permutations are uniformly distributed around the seed space (some knowledge on cryptography 在这里会有很大帮助）。

主要操作将是这样的，在伪代码中：

for i in range(0, n){ i:= (i*k)(mod n);}

这里是 C:

中的一个工作玩具程序

#include <stdio.h>

int main(void)
{
  // take a prime number (from https://primes.utm.edu/lists/2small/0bit.html)
  //int n = (int)pow(2,13)-1;
  // for the sake of test, let's take a little one:
  int n = 23;
  // take a random integer seed:
  int k = 1234;
  printf("permutation of numbers from 0 below %d with seed %d:\n", n, k);
  for (int i=0; i<n; i++){
    printf("%d ", ((i*k)%n));
  }
  printf("\n");
  return 0;
}

哪个returns:

permutation of numbers from 0 below 23 with seed 1234:
0 15 7 22 14 6 21 13 5 20 12 4 19 11 3 18 10 2 17 9 1 16 8

这不是您想要的，但通过一些调整它可以正常工作...除非我们谈论的是高端安全性内容。可能最直接的解决方案是选择接近 2 的幂的素数，然后进行一些调整？ https://primes.utm.edu/lists/2small/

如果有帮助请告诉我！

编辑我忍不住直接在我的 emacs 上测试它，所以这是后代的功能：

(defun permute (n seed)
  "prints a permutation of the set of numbers between 0 and n-1, 
   provided n is prime"
  (let ((permuted (loop for i below n collect (% (* i seed) n))))
    (print permuted)
    ;(print (sort permuted '<)) ; debug print
    ))

(test 23  1234) ; returns (0 15 7 22 14 6 21 13 5 20 12 4 19 11 3 18 10 2 17 9 1 16 8)

编辑 2 实际上，k 和 n 互为质数就足够了，如 Bézout's theorem 中所述。因此，从技术上讲，如果您确保 n 可以具有任意自然值。一种直接但有限的方法是从素数列表中随机选择 k。一个可能更好的解决方案是为每个给定的 n 计算其相对质数，并从那里选择（声明：8 和 9 都不是质数，但它们互为质数，因为 9(mod 8 )= 1).它并没有比这更多 "complete"，但我仍然不知道这种方法是如何分布排列的。

Answer 2

我在 Andrew Kensler 的论文 Correlated Multi-Jittered Sampling 中找到了一个很好的解决方案。这里的排列是使用仅由可逆运算符组成的混合函数构造的。这样可以保证在二次方范围内不会发生碰撞。

该函数是通过使用爬山程序迭代找到的，该程序根据雪崩属性评估每个候选者。此外，Kensler 通过使用一种称为循环行走的技术将散列概括为允许范围不是 2 的幂。

由于这一点，结果的质量以及轻松打乱排列的能力，所提出的函数是对原始问题的一个很好的解决方案。有关可逆运算符和生成高质量混合函数的更多详细信息，请参阅 Bret Mulvey 关于哈希函数的文章 here。

基数范围内整数的最小完美散列

Minimal perfect hashing of integers in base two range

c

hash

integer

range

perfect