2012-04-12 9 views
2

異なるオブジェクトからの2つのハッシュを結合する合法的な方法は、XORを使用することです。これは理にかなっていますが、次の記事のThomas Porninによる2番目のコメントで述べたように、XORは可換です。つまり、セットの各要素をハッシュしてXORと組み合わせると、同じハッシュ:順序集合に対するハッシュの結合

Why is XOR the default way to combine hashes?

あなたが順序に依存するようにしたいのハッシュを組み合わせるための良い方法は何ですか?サイズに固有の場合は、32ビットと64ビットのいくつかの既知のテクニックは何ですか?

+0

サイドノート、特定のケースでは、私は0から要素の数になる反復変数 'i'を持っています。注文依存のハッシュを作るために '私'を使う良い方法はありますか? – Trevor

+0

もしあなたが命令を加えたいならば、部分ハッシュを回転させてから集約にxoringすることができます。これはコースが衝突(H(ABCD)== H(DABC)など)を引き起こす可能性がありますが、それはゲームの一部です... – wildplasser

+0

今、私は巨大なプライム、そしてxorか、それはすべての要素のハッシュです。それは命令を課すが、私は確かに専門家ではないし、それが大きな衝突を引き起こすかどうかはわからない。 – Trevor

答えて

1

結果のハッシュ順序に依存するためには、アルゴリズムにいくつかの連続した(つまり非静的な)アスペクトがなければなりません。最も一般的なテクニックは、おそらくCyclic Redundancy Checks(CRC)のテクニックです。

CRCは、XOR-edフィードバック付きのシフトレジスタとしてハードウェアで実装できます。このようなシフトレジスタは、決定論的乱数発生器として機能する。初期状態が同じであれば、常に同じ状態のシーケンスを辿ります。これらの状態は、データを反復可能にXORするためにCRCシグネチャの計算に使用されます。

2つのハッシュ値を結合するには、それらをCRCアルゴリズムの3番目の値とXORします。これはtable.-

人気のCRCコードを計算またはルックアップから撮影される可能性があります。

09 bits (CRC-8) 
17 bits (CRC-16) 
33 bits (CRC-32) 
65 bits (CRC-64) 

Classless.Hasherは、より多くの詳細を提供します。

C#実装はHashLibにあります。

関連する問題