기본 2 범위에서 정수의 최소 완벽 해싱

Question

나는 기본 2의 범위 내에서 정수를 취하고 충돌없이 해당 범위 내의 다른 정수로 걸리는 간단한 해시 함수 다음에 있습니다. 이것은 순열 (permutation)과 바람직하게는 시드 값 (seed value)을 구성하는 데 사용됩니다. 따라서 정수를 오프셋하고 변조하는 것만으로는 효과가 없습니다. 누구든지 C로 작성된 좋은 옵션을 알고 있습니까?

감사합니다, 조쉬

Answer 1

Andrew Kensler가 작성한 Correlated Multi-Jittered Sampling 종이에서 좋은 해결책을 발견했습니다. 여기에서 순열은 가역 연산자로만 구성된 혼합 함수를 사용하여 구성됩니다. 이것은 두 범위의 거듭 제곱 내에서 충돌이 발생하지 않도록합니다.

이 함수는 각 후보를 평가하는 힐 클라이밍 (hill-climbing) 프로그램을 사용하여 반복적으로 발견되었습니다. 또한, Kensler는 사이클 워킹이라는 기술을 사용하여 해시가 2의 거듭 제곱이 아닌 범위를 허용하도록 해시를 일반화합니다.

이 때문에 결과의 품질과 순열을 쉽게 스크램블 할 수있는 능력 때문에 제안 된 함수는 원래의 질문에 대한 좋은 해결책입니다. 가역 연산자와 품질 혼합 함수 생성에 대한 자세한 내용은 Bret Mulvey의 해시 함수 here을 참조하십시오.

Answer 2

이 (더 일반적인 접근 방식 하단 참조) 도움이 될 수

:의 multiplicative cyclic groups 당신이 k "씨"값을 선택할 수 있도록 n "최대"값을, 그리고 자연을 순열 0부터 n-1까지의 숫자는 매우 효율적입니다 (k는 Z이지만 바람직하게는 자연수입니다). 만약 당신이 순열을 원한다면, 단지 n이 소수이어야하고, 모든 순열이 시드 공간 주위에 균일하게 분산되어 있는지 확실하지 않습니다. (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; 
} 

반환

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 

주요 작업은 다음 의사 코드에서이 같은 일 것이다

이것은 정확히 원하는 것만은 아니지만 약간 조정하면 정상적으로 작동 할 수 있습니다 ... 우리가 고급 보안 장치 ity stuff. 아마 가장 직접적인 해결책은 2의 거듭 제곱에 가까운 소수를 선택하고 약간의 조정을하는 것일 것입니다. https://primes.utm.edu/lists/2small/

도움이되는지 알려주세요. 내가 직접 내 이맥스에서 테스트하는 데 도움이되지 수

편집, 그래서 여기에 후대를위한 기능입니다 : 2 사실

(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) 

편집, 그것은 충분 k 및 n 그 Bézout's theorem에 명시된 바와 같이 서로에게 중요합니다. 따라서 기술적으로는 n에 대해 임의의 자연 값을 가질 수 있습니다. 간단하지만 제한된 방법은 소수 목록에서 임의로 k을 선택하는 것입니다. 어쩌면 더 좋은 해결책은 각 주어진 n에 대해 상대적인 소수를 계산하는 것입니다 (aclaration : 8도 9도 소수이지만 9 (mod 8) = 1이므로 서로를 소수입니다). 그보다 훨씬 더 "완벽하다"는 것은 아니지만이 방법으로 순열이 어떻게 분산되어 있는지는 여전히 알 수 없습니다.