バイナリデータ用の移植可能なhashCodeの実装

Question

私は、バイナリデータ用のhashCodeを作成するポータブルアルゴリズムを探しています。バイナリデータは非常に長くありません - 私はAvro - kafka.KeyedMessagesで使用するための符号化キーです - おそらく長さは2〜100バイトですが、ほとんどのキーは4〜8バイトの範囲です。

これまでのところ、データを16進文字列に変換し、hashCodeを実行することをお勧めします。私はScalaとJavaScriptの両方でその作業を行うことができます。私はb: Array[Byte]を定義したと仮定すると、Scalaは次のようになります。

b.map("%02X" format _).mkString.hashCode 

それはJavaScriptにもう少し手の込んだだ - 幸いにもsomeone already ported JavaScriptに基本のhashCodeアルゴリズム - しかし、ポイントはHexを作成できることです文字列は、バイナリデータを表すために、私はハッシュアルゴリズムが同じ入力をオフに動作することを確認することができます。

一方、hashCodeを作成するために、オリジナルの2倍のサイズのオブジェクトを作成する必要があります。幸運なことに、私のデータの大部分は小さいですが、これを行うにはより良い方法が必要です。

データを16進数の値にパディングするのではなく、バイナリデータをストリングに変換してバイナリデータと同じバイト数にすることができます。それはすべて文字化けし、印刷可能な文字よりも制御文字が多いですが、それでも文字列になります。あなたは移植性の問題に遭遇しますか？などエンディアン、Unicodeの、あなたがこれまで読んだ本を持って、すでにこれを知っていない場合

ところで、 - あなただけで行うことはできません。

val b: Array[Byte] = ... 
b.hashCode 

幸いにも私はすでに私の前にいることを知っていました私は早い時期にそれに遭遇したので、開始した。与えられた最初の回答に基づいて

更新

、java.util.Arrays.hashCode(Array[Byte])は、トリックを行うだろうと最初に顔を赤らめるに表示されます。しかし、javadocの追跡に従えば、リストのアルゴリズムとbyteのアルゴリズムに基づくアルゴリズムの背後にあるアルゴリズムであることがわかります。

int hashCode = 1; 
for (byte e : list) hashCode = 31*hashCode + (e==null ? 0 : e.intValue()); 

あなたが見ることができるように、それはやっているすべての値を表すLongを作成しています。特定のポイントでは、数値が大きくなりすぎて折り返します。これはあまり移植性がありません。私はそれがJavaScriptのために働くことができますが、npmモジュールlongをインポートする必要があります。そうした場合、それは次のようになります。

function bufferHashCode(buffer) { 
    const Long = require('long'); 
    var hashCode = new Long(1); 
    for (var value of buff.values()) { hashCode = hashCode.multiply(31).add(value) } 
    return hashCode 
} 

bufferHashCode(new Buffer([1,2,3])); 
// hashCode = Long { low: 30817, high: 0, unsigned: false } 

、データがラップアラウンドしたときに、私はなぜわからないけれども、あなたは、並べ替えの、同じ結果を得るのですか。 Scalaで：

java.util.Arrays.hashCode(Array[Byte](1,2,3,4,5,6,7,8,9,10)) 
// res30: Int = -975991962 

結果がIntであることに注意してください。 JavaScriptでは：

bufferHashCode(new Buffer([1,2,3,4,5,6,7,8,9,10]); 
// hashCode = Long { low: -975991962, high: 197407, unsigned: false } 

だから私は、lowバイトを取るとhighを無視する必要がありますが、そうでない場合、私は同じ結果を得ます。

Answer 1

この機能はすでにJava標準ライブラリで利用できます。Arrays.hashCode()メソッドを参照してください。

あなたのバイナリデータは、ここでは、Array[Byte]なので、あなたはそれが動作することを確認する方法である。

println(java.util.Arrays.hashCode(Array[Byte](1,2,3))) // prints 30817 
println(java.util.Arrays.hashCode(Array[Byte](1,2,3))) // prints 30817 
println(java.util.Arrays.hashCode(Array[Byte](2,2,3))) // prints 31778 

更新：それはJava実装ボックスというバイト真実ではありません。もちろん、intへの変換はありますが、その回りの方法はありません。これは、Javaの実装です：

public static int hashCode(byte a[]) { 
    if (a == null) return 0; 
    int result = 1; 
    for (byte element : a) result = 31 * result + element; 
    return result; 
} 

アップデート2 何が必要なのあなただけ取って、例えば、によってアルゴリズムを拡張することができるよりも、Scalaの/ Javaの実装と同じ結果を与えるJavaScriptの実装である場合右端の31ビット：

def hashCode(a: Array[Byte]): Int = { 
    if (a == null) { 
    0 
    } else { 
    var hash = 1 
    var i: Int = 0 
    while (i < a.length) { 
     hash = 31 * hash + a(i) 
     hash = hash & Int.MaxValue // taking only the rightmost 31 bits 
     i += 1 
    } 
    hash 
    } 
} 

とJavaScript：

var hashCode = function(arr) { 
    if (arr == null) return 0; 
    var hash = 1; 
    for (var i = 0; i < arr.length; i++) { 
     hash = hash * 31 + arr[i] 
     hash = hash % 0x80000000 // taking only the rightmost 31 bits in integer representation 
    } 
    return hash; 
} 

2つのIを行う理由mplementationsは同じ結果を生成しますか？ Javaでは、整数のオーバーフローは、精度が低下することなく加算が実行された場合と同様に動作し、32より大きいビットがスローされ、& Int.MaxValueが32 ^ndビットをスローします。 JavaScriptでは、最大で2 の整数の精度が失われることはなく、式31 * hash + a(i)を超えることはありません。 % 0x80000000は、右端の31ビットをとるように動作します。オーバーフローのない場合は明らかです。

Answer 2

これは、Javaライブラリで使用されるアルゴリズムの肉です：

int result 1; 
    for (byte element : a) result = 31 * result + element; 

あなたがコメント：

をこのアルゴリズムが正しくない

非常に移植性がありません。 Javaについて話している場合は、resultのタイプにすべて同意すれば、アルゴリズムは100％移植性があります。

はい計算はオーバーフローしますが、はJava言語のすべての有効な実装で全く同じ方法でオーバーフローします。 Java intはで、は32ビット符号付き2の補数で、オーバーフローが発生したときの演算子の動作は明確に定義されています。すべての実装で同じです。 （同じことがlong ...となります）

私は専門家ではありませんが、私はScalaの数値型がJavaと同じプロパティを持っていることを理解しています。 JavascriptはIEE 754倍精度浮動小数点に基づいて異なります。しかし、大文字と小文字を区別すると、JavaアルゴリズムをJavaで移植可能にコードできるはずです。 （私は@ミーフェットのバージョンが間違っていると思う...）