Rabin-Karp算法的最佳哈希函數是什麼？

我正在尋找Rabin-Karp算法的高效哈希函數。這是我的實際代碼（C編程語言）。Rabin-Karp算法的最佳哈希函數是什麼？

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哈希函數應具有哪些特徵？

來源

2012-07-18 md5

你是否已經看到[這]（http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm #Hash_function_used）？ – Gigi 2012-07-18 17:18:38

Rabin-Karp不能使用任何散列函數，它需要一個專門的散列函數，可以根據位置（i-1）的已知值快速計算位置i。 – rossum 2012-07-18 20:59:40

是的，@吉吉，我有。但是如果有更好的散列函數，它會是完美的（因爲我會多次運行這個函數）。 @rossum：根據維基百科的文章，我做了一個'rehash'函數。 – md5 2012-07-19 08:25:01

一個極好的表現散列是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

來源

2012-07-18 17:55:00

在算術運算中「無符號」是否溢出？ – Pupsik 2017-05-09 07:48:50

Rabin-Karp算法的最佳哈希函數是什麼？

回答

相關問題