josh247 josh247 - 10 months ago 44
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?


Answer Source

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
  //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));
  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?

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)