問題タブ [fnv]

Fowler–Noll–Vo ハッシュ関数の実装を試みています

擬似コードは次のようになります

これはそのための私のコードです

今はこんな感じで使っています

ここで結果をテストして おり、結果は0d47307150c412cfとして得られます

アップデート：

タイプを次のように修正しました

そして、まだ結果0d47307150c412cfと一致しない結果fa365282a44c0ba7を取得します

これを修正する方法についての提案

Cormen の各レベルでユニバーサル ハッシュを使用して、完璧なハッシュ手法を実装しようとしています。具体的には、圧縮方法を使用します（少なくとも、ここに問題があると思います）。

私は文字列に取り組んでおり、短い文字列 (8 から 150 の間) だと思います。そのために、64 ビット キーを使用して、Murmur3/2、xxhash、FNV1、Cityhash、および Spookyhash を使用した一連のハッシュ関数があります (これらのspookyhash のようなハッシュ関数では下位 64 ビットを取得しています)、問題は、9 つ​​のバケットに 3 つの一意の文字列 (10 文字のうちの 2 つと 11 文字のうちの 1 つ) しかない衝突が存在することです。

そのためにコーメンのハッシュ圧縮方法を使用しています。

h_ab(k) = ((ak+b)mod p) mod m

a = 3、p = 4294967291 (最大の32 ビット素数)、b = 5およびm = 9 (m_j は n_j の 2 乗であるため) を使用します。「k」として、ハッシュ関数によって返されたハッシュ値を使用しています（つぶやきなど）。

たとえば、murmur2 (64 ビット バージョン) のようなハッシュ関数を使用している場合、p番号は最大の 64 素数である必要がありますか? そのようにして、つぶやきが返す可能性のあるすべてのハッシュをカバーしていますね。

他にどのハッシュ圧縮手法 (除算以外) が存在し、推奨しますか?

参考文献、ヒント、本、論文、ヘルプは大歓迎です。ばかげた質問で申し訳ありませんが、私はハッシュ関数とハッシュテーブルの初心者です。

前もって感謝します。

python-3.6 で fnv ハッシュ関数を使用しようとしていますが、エラーが発生します

トレースバック (最後の最後の呼び出し): ファイル "C:/Users/SACHIN/AppData/Local/Programs/Python/Python36/bloom.py"、4 行目、モジュール fnv.hash(data, algorithm=fnv.fnv_1a, bits) =64) ファイル "C:\Users\SACHIN\AppData\Local\Programs\Python\Python36\lib\site-packages\fnv__init__.py"、52 行目、ハッシュ OFFSET_BASIS[bits] ファイル "C:\Users\SACHIN \AppData\Local\Programs\Python\Python36\lib\site-packages\fnv__init__.py", line 28, in fnv_1a return ensure_bits_count((hash_value ^ byte) * PRIMES[bits], bits) TypeError: unsupported operand type(s) ) ^: 'int' および 'str' の場合

コード用

https://pypi.python.org/pypi/fnv/0.2.0から正確にコピーされます

実際に何が間違っているのか教えてください。

私はRustが初めてで、2つのFnvHashMapを反復処理して違いを見つけるコードを次に示します

これらの値を別のベクトルに追加すると、Rust がコンパイル エラーをスローする

どんな助けでも本当に感謝しています。ありがとう