2 
unsigned int HashString( const char *string ) {
    const char* p;
    unsigned hash = 40503;

    for ( p = string; *p != '\0'; ++p ) {
        hash += *p;
        hash += ( hash << 10 );
        hash ^= ( hash >> 6 );
    }
    hash += ( hash << 3 );
    hash ^= ( hash >> 11 );
    hash += ( hash << 15 );

    return hash;
}

彼らのコードをさまよっているだけです。ただし、このようなハッシュ関数はこれまで見たことがありません。

ビットごとの操作に関しては、私はあまり経験がありません。ビットシフトとマスキングがどのように機能するかは知っていますが、ビットが設定されているかどうかを確認するなどの基本的なシナリオでのみです。

これは正確に何をしますか？

4

3 に答える 3

1

誰がそれがよくハッシュすると言いますか?

ハッシュ関数は、入力 (この場合は文字列) を出力 (この場合はunsigned int. 入力のサイズは、(number of usable characters) ^ number of characters in the string「^累乗」です。

入力文字列に文字のみを含めることができ、入力 0の1サイズは2^ number of characters in the string

出力のサイズは、 で表現可能な最大数に固定されていunsigned intます。

これは、入力のサイズが出力のサイズよりも大きくなる「文字列内の文字数」があることを意味します。ピジョン ホールの原理により、確実に衝突が発生し始めます。実際には、このしきい値に達する前に衝突が発生した可能性があります。

hash_map独自のデータ構造またはその他のデータ構造でハッシュ関数を使用する場合は、特定の入力に合わせて調整されていることを確認してください。インターネットで最初に見つけたものを拾わないでください。優れたハッシュ関数は、特定の入力に対して可能な限り少ない衝突を提供します。

汎用ハッシュ関数は、特定のケースでは最適ではない場合があります。一部の入力用に特別に設計されたハッシュ関数 (およびこれはそのような関数である可能性が非常に高い) は、入力に対して大幅に機能が低下する可能性があります。

于 2013-05-22T21:55:00.123 に答える