Rabin-Karp 알고리즘에 가장 적합한 해시 함수는 무엇입니까?

Question

나는 Rabin-Karp 알고리즘을위한 효율적인 해시 함수를 찾고있다. 다음은 실제 코드 (C 프로그래밍 언어)입니다.

static bool f2(char const *const s1, size_t const n1, 
       char const *const s2, size_t const n2) 
{ 
    uintmax_t hsub = hash(s2, n2); 
    uintmax_t hs = hash(s1, n1); 
    size_t nmax = n2 - n1; 

    for (size_t i = 0; i < nmax; ++i) { 
     if (hs == hsub) { 
      if (strncmp(&s1[i], s2, i + n2 - 1) == 0) 
       return true; 
     } 
     hs = hash(&s1[i + 1], i + n2); 
    } 
    return false; 
} 

일부 Rabin-Karp C 구현을 고려했지만 모든 코드 간에는 차이점이 있습니다. 그래서 내 질문은 : Rabin-Karp 해시 함수가 가져야하는 특성은 무엇입니까?

Answer 1

극히 좋은 해시는 bernstein 해시입니다. 많은 인기있는 해싱 알고리즘을 능가합니다.

참고 : 여기에 설명 된대로 물론

unsigned bernstein_hash (void *key, int len) 
{ 
    unsigned char *p = key; 
    unsigned h = 0; 
    int i; 

    for (i = 0; i < len; i++) 
     h = 33 * h + p[i]; 

    return h; 
} 

, 당신은 다른 해싱 알고리즘을 시도 할 수 있습니다 그것은 설명 적이 한 33 다른 "더 논리보다는 훨씬 더 수행하는 이유 " 일정한. 관심을

는 : strchr comparison of hash algorithms