60

次のようなハッシュ関数を探しています。

  1. テキスト文字列を適切にハッシュします（例：衝突が少ない）
  2. Javaで書かれており、広く使用されています
  3. ボーナス：いくつかのフィールドで機能します（私がそれらを連結して、連結された文字列にハッシュを適用する代わりに）
  4. ボーナス：128ビットのバリアントがあります。
  5. ボーナス：CPUを集中的に使用しません。
4

9 に答える 9

73

longデフォルトのバリアントを使用しないのはなぜですかString.hashCode()(一部の非常に賢い人は確かに効率化に力を入れています - このコードを既に見た何千もの開発者の目は言うまでもありません)。

// adapted from String.hashCode()
public static long hash(String string) {
  long h = 1125899906842597L; // prime
  int len = string.length();

  for (int i = 0; i < len; i++) {
    h = 31*h + string.charAt(i);
  }
  return h;
}

さらにビットを探している場合は、おそらくBigInteger Editを使用できます。

@brianegge の回答へのコメントで述べたように、32 ビットを超えるハッシュのユースケースはあまりなく、64 ビットを超えるハッシュのユースケースはおそらく 1 つもありません。

数十億のマッピングを保存する、数十のサーバーに分散された巨大なハッシュテーブルを想像することができました。このようなシナリオでは、@brianegge はここでも有効なポイントを持っています: 32 ビットは 2^32 (約 43 億) の異なるハッシュ キーを許可します。強力なアルゴリズムを仮定すると、衝突はまだかなり少ないはずです。64 ビット (18,446,744,073 億の異なるキー) を使用すると、必要なクレイジーなシナリオに関係なく、確実に節約できます。ただし、128 ビット キー (340,282,366,920,938,463,463,374,607,431 億のキー) のユースケースを考えることはほとんど不可能です。

複数のフィールドのハッシュを結合するには、単純に XORを実行して素数を乗算し、それらを加算します。

long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2);

小さな素数は、切り替えられた値のハッシュ コードが等しいことを避けるためにあります。つまり、{'foo','bar'} と {'bar','foo'} は等しくなく、異なるハッシュ コードを持つ必要があります。XOR は、両方の値が等しい場合に 0 を返すため、不適切です。したがって、{'foo','foo'} と {'bar','bar'} は同じハッシュ コードになります。

于 2009-11-02T11:00:52.767 に答える
4

SHA-1 ハッシュを作成し、最下位の 64 ビットをマスクします。

于 2009-11-02T10:49:51.357 に答える
2

CRC64多項式を使用してみませんか。これらはかなり効率的で最適化されており、すべてのビットがカウントされ、結果スペース全体に分散されるようになっています。

「CRC64Java」をグーグルで検索すると、ネット上で利用可能な実装がたくさんあります。

于 2010-06-03T10:15:49.887 に答える
2 
long hash = string.hashCode();

はい、上位 32 ビットは 0 になりますが、ハッシュ衝突の問題が発生する前にハードウェア リソースが不足する可能性があります。String の hashCode は非常に効率的で、十分にテストされています。

更新上記はおそらく機能する可能性のある最も単純なことを 満たしていると思いますが、既存の String hashCode を拡張するという @sfussenegger のアイデアに同意します。

String に適切な hashCode を使用することに加えて、実装でハッシュ コードを再ハッシュすることを検討することをお勧めします。ストレージが他の開発者によって使用されている場合、または他のタイプで使用されている場合、これはキーの分散に役立ちます。たとえば、Java の HashMap は 2 の累乗の長さのハッシュ テーブルに基づいているため、この関数を追加して、下位ビットが十分に分散されるようにします。

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
于 2009-11-02T11:42:56.463 に答える
1

文字列を逆にして別の 32 ビット ハッシュコードを取得し、2 つを結合します。

String s = "astring";
long upper = ( (long) s.hashCode() ) << 32;
long lower = ( (long) s.reverse().hashCode() ) - ( (long) Integer.MIN_VALUE );
long hash64 = upper + lower;

これは疑似コードです。String.reverse()メソッドは存在しないため、別の方法で実装する必要があります。

于 2014-08-06T07:17:08.573 に答える
1

次のようにします。

import java.io.ByteArrayOutputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class Test {

    public static void main(String[] args) throws NoSuchAlgorithmException,
            IOException {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        DataOutputStream dos = new DataOutputStream(baos);

        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            SomeObject testObject = new SomeObject();

            dos.writeInt(testObject.count);
            dos.writeLong(testObject.product);
            dos.writeDouble(testObject.stdDev);
            dos.writeUTF(testObject.name);
            dos.writeChar(testObject.delimiter);
            dos.flush();

            byte[] hashBytes = md.digest(baos.toByteArray());
            BigInteger testObjectHash = new BigInteger(hashBytes);

            System.out.println("Hash " + testObjectHash);
        } finally {
            dos.close();
        }
    }

    private static class SomeObject {
        private int count = 200;
        private long product = 1235134123l;
        private double stdDev = 12343521.456d;
        private String name = "Test Name";
        private char delimiter = '\n';
    }
}

DataOutputStreamを使用すると、プリミティブと文字列を記述して、それらをバイトとして出力できます。ByteArrayOutputStreamをラップすると、バイト配列に書き込むことができ、 MessageDigestとうまく統合されます。ここにリストされている任意のアルゴリズムから選択できます。

最後に、 BigIntegerを使用すると、出力バイトを使いやすい数値に変換できます。MD5 アルゴリズムと SHA1 アルゴリズムは両方とも 128 ビットのハッシュを生成するため、64 ビットが必要な場合は単に切り捨てることができます。

SHA1 は、ほとんどすべてのものを適切にハッシュし、衝突の頻度は低いはずです (128 ビットです)。これは Java から動作しますが、どのように実装されているかわかりません。実際にはかなり速いかもしれません。私の実装では、いくつかのフィールドで動作しDataOutputStreamます。それらすべてを にプッシュするだけで、準備完了です。リフレクションと注釈を使用してそれを行うこともできます (おそらく@HashComponent(order=1)、どのフィールドがどの順序でハッシュに入るかを示すため)。128 ビットのバリアントがあり、思ったほど CPU を使用しないことがわかると思います。

このようなコードを使用して、膨大なデータ セット (現在ではおそらく数十億個のオブジェクト) のハッシュを取得し、多くのバックエンド ストアでそれらをシャーディングできるようにしました。必要なものは何でも機能するはずです。MessageDigest.getInstance()一度だけ呼び出して、それ以降は呼び出したいと思うかもしれないことに注意してくださいclone()。IIRCのクローン作成ははるかに高速です。

于 2010-06-03T10:55:15.157 に答える
0

Apache commons langを見ていますか？

ただし、64 ビット (および 128) の場合は、いくつかのトリックが必要です。Joshua Bloch 著『Effective Java』という本に記載されているルールを使用すると、64 ビット ハッシュを簡単に作成できます (int の代わりに long を使用するだけです)。128ビットの場合、追加のハックが必要です...

于 2009-11-02T11:12:42.297 に答える
-2

免責事項: このソリューションは、個々の自然言語の単語を効率的にハッシュしたい場合に適用できます。長いテキストやアルファベット以外の文字を含むテキストのハッシュには非効率的です。

私は機能を認識していませんが、ここに役立つアイデアがあります：

  • 64 ビットのうち 52 ビットを、文字列に含まれる文字を表す専用にします。たとえば、'a' が存在する場合、ビット [0] を設定し、'b' にはビット1を設定し、'A' にはビット [26] を設定します。そうすれば、まったく同じ文字セットを含むテキストだけが同じ「署名」を持つことになります。

次に、残りの 12 ビットを使用して文字列の長さ (またはそのモジュロ値) をエンコードし、衝突をさらに減らすか、従来のハッシュ関数を使用して 12 ビットの hashCode を生成できます。

入力がテキストのみであると仮定すると、これにより衝突がほとんど発生せず、計算が安価になると想像できます (O(n))。 これまでの他のソリューションとは異なり、このアプローチでは問題領域を考慮して衝突を減らします。これは、プログラミング パール (こちらを参照) で説明されているアナグラム検出器に基づいています。

于 2009-11-02T10:47:43.807 に答える