josh247 josh247 - 2 months ago 14
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

Answer

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)