問題タブ [murmurhash]

I have to use an x86 32 bits murmurhash to determinate the partition in which I send messages in Kafka. Another application is using NodeJS murmurhash.v3() method to get the messages from the expected partition.

I tried two methods :

1. First, I got the Java class from https://svn.apache.org/repos/asf/mahout/trunk/math/src/main/java/org/apache/mahout/math/MurmurHash3.java
2. I also tried to translate the JS code of NodeJS murmurhash.v3() in Java (N to A column in the table below)

Here is the code I use to get values from Apache java method :

Note: at present time, KAFKA_PARTITION_SEED = 100 but it's just a test value. It will be a Long value in the future.

Here is the code I have done, translating from NodeJS to Java :

In both cases I get the same results when trying to get the partition value. The partition value (P in the table below) is the modulo 8 (%8) of the murmurhash method returned value.

Here is a example of the result I get :

0009B5192951 | 1285784451 | 3 |  1285784451 |  3 |  1285784451 |   3 | TRUE

0009B5192953 | 2252321193 | 1 | -2042646103 | -7 | -2042646103 | -7 | FALSE

0009B5192979 |   973658619 | 3 |    973658619 |   3 |    973658619 |  3 | TRUE

0009B5192985 | 1359432313 | 1 |  1359432313 |   1 |  1359432313 |  1 | TRUE

0009B5192987 | 3551230334 | 6 |   -743736962 |  -2 |  -743736962 | -2 | FALSE

0009B5192995 |   199863683 | 3 |    199863683 |   3 |    199863683 |  3 | TRUE

0009B5193001 | 1660947343 | 7 |  1660947343 |   7 |  1660947343 |  7 | TRUE

0009B5193007 | 1980598253 | 5 |  1980598253 |   5 |  1980598253 |  5 | TRUE

0009B5203789 | 1358113422 | 6 |  1358113422 |   6 |  1358113422 |  6 | TRUE

0009B5203791 | 1339226023 | 7 |  1339226023 |   7 |  1339226023 |  7 | TRUE

As you can see, in some cases, the Apache murmurhash method returns a negative value, which is not expected (I guess).

Can anyone tell me what I am doing wrong ?

Java と C++ の 2 つの個別のアプリケーションがあります。両方に Murmurhash3 を使用しています。ただし、C++ では、同じ文字列に対して Java と比較して異なる結果が得られます。

これは C++ のものです: https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp?r=144

私は次の機能を使用しています：

これは Java 用のものです: http://search-hadoop.com/c/HBase:hbase-common/src/main/java/org/apache/hadoop/hbase/util/MurmurHash3.java||server+void+% 2522ハッシュ

上記の同じ Java コードの多くのバージョンがあります。

これは、私が Java を呼び出す方法です。

Java から得た出力: -1868221715

C++ 3297211900 から得られる出力

「7c6c5be91430a56187060e06fd64dcb8」や「7e7e5f2613d0a2a8c591f101fe8c7351」などの他のサンプル文字列をテストしたところ、Java と C++ で一致しました。

任意のポインタをいただければ幸いです

約 6,400 万個の 64 ビットの一意の符号なし整数を 1 億 2,800 万個のバケット (27 ビット幅のアドレス) にハッシュしようとしていました。Bob Jenkin のHashLittleとMurmurハッシュを試しました (これらのハッシュ関数はどちらも 32 ビット ハッシュを提供し、それをマスクして 27 ビット アドレスを取得しました)。どちらの場合も、約 22% の衝突が発生し、最終的にバケットの 37% しか占有しませんでした。これは予期されていることですか、それとも何か間違っていますか? 衝突がはるかに少なく、バケツの占有が改善されることを期待していました。

Cassandra が複合パーティション キーの murmur3 ハッシュを生成するために使用するアルゴリズムを理解しようとしています。CQL から直接値を取得できることはわかっていますが、特定のタプルに対して Java/scala コードから直接 Cassandra の動作を再現したいと考えています。

単純なパーティション キーの場合、次の関数で正しい値が計算されます (少なくとも多くの場合、正確ではないことはソース コードを見ればわかります)。

long l = com.google.common.hash.Hashing.Hashing.murmur3_128().hashString("my-string", Charset.forName("UTF-8")).asLong();

パーティション キーに 2 つの列がある場合はどうなりますか?

2 つの文字列の連結のハッシュは同じではありません。

ファイルを処理するプログラムで重複を検出するために SHA-1 を使用しています。強力な暗号である必要はなく、元に戻すことができます。この高速ハッシュ関数のリストを見つけましたhttps://code.google.com/p/xxhash/

より高速な関数と SHA-1 に近いランダム データの衝突が必要な場合は、何を選択すればよいですか?

ファイルの重複排除には 128 ビットのハッシュで十分ではないでしょうか? (vs 160 ビット sha-1)

私のプログラムでは、ハッシュは 0 ～ 512 KB のチャンクで計算されます。

Python と Java でそれぞれ Murmur3 を使用して同じ文字列をハッシュしたい 2 つの異なるプログラムがあります。

Python バージョン 2.7.9:

79267961763742113019008347020647561319L を返します。

Java は Guava 18.0 です。

文字列 "6778ad3f3f3f96b4522dca264174a23b" を返し、BigInterger に変換すると 137537073056680613988840834069010096699 が返されます。

両方から同じ結果を得るには？

ありがとう

Murmur3 アルゴリズムを使用してハッシュを生成しようとしています。ハッシュは一貫していますが、Scala と Guava によって返される値は異なります。

異なるハッシュが得られるのはなぜですか?

Hazelcast のようなキー値ストアのキーとしてハッシュ (CityHash、Murmur など) を使用するのは良い考えかどうか疑問に思っています。データベースには約 2,000,000,000 のレコード (URL) があると予想しているため、競合が発生する可能性があります。ハッシュの衝突によって一部のデータが失われることはそれほど重要ではありませんが、もちろん回避することが最善です。

レコードには、URL、タイム スタンプ、ステータス コードが含まれます。主な操作は、URL が既に存在するかどうかの挿入と検索です。

それで、速度が関連していることを考えると、あなたは何を提案しますか：

• ID ジェネレーターを使用する、または
• CityHash や Murmur などのハッシュ アルゴリズムを使用する、または
• 関連する文字列、この場合は URL、それ自体を使用して?