7

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 ハッシュ関数が持つべき特性は何ですか?

4

2 に答える 2

9

非常に優れたパフォーマンスのハッシュは、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;
}

もちろん、ここで説明されているように、他のハッシュ アルゴリズムを試すこともできます: NIST のハッシュ関数

注: が33他の「より多くのロジック」定数よりもはるかに優れたパフォーマンスを発揮する理由は説明されていません。

ご参考までに: さまざまなハッシュ アルゴリズムの優れた比較を次に示します: strchr ハッシュ アルゴリズムの比較

于 2012-07-18T17:55:00.357 に答える
0

核酸配列検索 (例: alphabet = {A, T, C, G, U}) などの小さなアルファベットの問題については、nt-Hashが適切なハッシュ関数である可能性があります。より高速なバイナリ操作とローリング ハッシュ更新を使用し、一様な分散ハッシュ値も提供します。

于 2020-10-09T14:46:04.177 に答える