josh247 - 1 month ago 4
C Question

Minimal perfect hashing of integers in base two range

I'm after a simple hash function that would take an integer within a range of base two and (randomly) hash to another integer within that range without collisions. This is going to be used to construct a permutation and preferably from a seed value. So just offsetting the integer and modulating won't work. Anyone know of a good option written in C?

Thanks,
Josh

This may help: the 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 would help here a lot).

The main operation would then be something like this, in pseudocode:

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

and here a working toy-program in 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 to %d with seed %d:\n", n, k);
for (int i=0; i<n; i++){
printf("%d ", ((i*k)%n));
}
printf("\n");
return 0;
}
``````

which returns:

``````permutation of numbers from 0 to 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
``````

This isn't exactly what you want, but with some tweaks it could work OK... unless we're talking about high-end security stuff. Probably the most straightforward solution would be to pick the primes that are close to the power of two, and do some tweaking? https://primes.utm.edu/lists/2small/

Let me know if it helps!

EDIT I couldn't help to directly test it on my emacs, so here is the function for the posterity:

``````(defun permute (n seed)
"prints a permutation of the set of numbers between 0 and n,
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)
``````