java - 文字列連結の特定のタイプのハッシュ

Question

次のプロパティを持つ Java の特殊なハッシュ関数 h(X,Y) が必要です。

1. X と Y は文字列です。
2. h(X,Y) = h(Y,X)。
3. X と Y は任意の長さの文字列であり、h(X,Y) の結果にも長さ制限はありません。
4. X が A と等しくなく、Y が B と等しくない場合、h(X,Y) と h(Y,X) は h(A,B) = h(B,A) と衝突してはなりません。
5. h() は、前述の要件を満たす必要がない限り、安全なハッシュ関数である必要はありません。
6. かなり高いパフォーマンスですが、これは制限のない基準です。

私の考えでは、要件 2 と要件 4 は少し矛盾していると思いますが、心配しすぎているのかもしれません。

現在、私がJavaで行っていることは次のとおりです。

public static BigInteger hashStringConcatenation(String str1, String str2) {
    BigInteger bA = BigInteger.ZERO;
    BigInteger bB = BigInteger.ZERO;
    for(int i=0; i<str1.length(); i++) {
        bA = bA.add(BigInteger.valueOf(127L).pow(i+1).multiply(BigInteger.valueOf(str1.codePointAt(i))));
    }
    for(int i=0; i<str2.length(); i++) {
        bB = bB.add(BigInteger.valueOf(127L).pow(i+1).multiply(BigInteger.valueOf(str2.codePointAt(i))));
    }
    return bA.multiply(bB);
}

これは恐ろしいことだと思いますが、それがより良い解決策を探している理由です。ありがとう。

OS X 10.7 で 8GB RAM と Java 1.6 を搭載した 2.53GHz デュアル コア Macbook Pro では、ハッシュ関数は 2 つの 8 (ASCII) 文字列に対して約 270 マイクロ秒かかります。文字列のサイズが大きくなったり、Unicode 文字が使用されたりすると、これは高くなると思います。

Answer 1

hashCode を一緒に追加しないのはなぜですか?

Answer 2

3）XがAに等しくなく、YがBに等しくない場合、h（X、Y）およびh（Y、X）はh（A、B）= h（B、A）と衝突してはなりません。

この要件は、元の文字列よりも（平均して）小さい数値を生成するハッシュ関数を支配していると思います。

衝突がないという要件は、鳩の巣原理の障害にぶつかります。

Answer 3

4番目のポイントから、真になるまでh(x,"")衝突してはならないことがわかります。したがって、生成するものにサイズ制限はありません。これは、一意のそれぞれに対して一意の結果を生成する必要があるためです。しかし、一意の文字列は無数にあります。これは正しいハッシュ関数ではないと思います。h(y,"")x.equals(y)h(x,y)x

Answer 4

今日、私はこのハッシュ関数の問題に対する解決策を追加することにしました。それはあまりよくテストされておらず、私はそのパフォーマンスを測定しなかったので、あなたはあなたのコメントで私にフィードバックすることができます。私の解決策は以下にあります：

public abstract class HashUtil {
    //determines that we want hash, that has size of 32 integers ( or 32*32 bits )
    private static final int hash_size = 32;

    //some constants that can be changed in sake of avoiding collisions
    private static final BigInteger INITIAL_HASH = BigInteger.valueOf(7);
    private static final BigInteger HASH_MULTIPLIER = BigInteger.valueOf(31);
    private static final BigInteger HASH_DIVIDER = BigInteger.valueOf(2).pow(32*hash_size);

    public static BigInteger computeHash(String arg){
        BigInteger hash = new BigInteger(INITIAL_HASH.toByteArray());
        for (int i=0;i<arg.length()/hash_size+1;i++){
            int[] tmp = new int[hash_size];
            for(int j=0;j<Math.min(arg.length()-32*i,32);j++){
                tmp[i]=arg.codePointAt(i*hash_size+j);
            }
            hash = hash.multiply(HASH_MULTIPLIER).add(new BigInteger(convert(tmp)).abs()).mod(HASH_DIVIDER);
        }
        //to reduce result space to something meaningful
        return hash;
    }

    public static BigInteger computeHash(String arg1,String arg2){
        //here I don't forgot about reducing of result space
        return computeHash(arg1).add(computeHash(arg2)).mod(HASH_DIVIDER);
    }

    private static byte[] convert(int[] arg){
        ByteBuffer byteBuffer = ByteBuffer.allocate(arg.length*4);
        IntBuffer intBuffer = byteBuffer.asIntBuffer();
        intBuffer.put(arg);
        return byteBuffer.array();
    }

    public static void main(String[] args){
        String firstString="dslkjfaklsjdkfajsldfjaldsjflaksjdfklajsdlfjaslfj",secondString="unejrng43hti9uhg9rhe3gh9rugh3u94htfeiuwho894rhgfu";
        System.out.println(computeHash(firstString,secondString).equals(computeHash(secondString,firstString)));
    }

}

私のソリューションでは、長さが32未満の単一の文字列に対して衝突が発生することはないと思います（より正確には、長さがhash_size可変値未満の単一の文字列の場合）。また、衝突を見つけるのは非常に簡単ではありません（私が思うように）。特定のタスクのハッシュ競合の可能性を調整するには、 andin変数の代わり7に別の素数を試すことができます。あなたはそれについてどう思いますか？それはあなたにとって十分ですか？31INITIAL_HASHHASH_MULTIPLIER

PSもっと大きな素数を試してみるともっといいと思います。

Answer 5

要件 4 はどの程度厳格ですか? 答えが「完全に厳密ではない」場合は、2 つの文字列を連結して小さい方を先に置くことができます (これにより、h('A', 'B') と h('AB', '') の衝突が発生します)。 )

文字列値に決して現れないことが確実な文字がある場合は、単一のインスタンスをセパレーターとして使用できます。これにより、上記の衝突が修正されます。

Answer 6

さて、@ gkuzminのコメントは、なぜ私が127の累乗を実行しているのかを考えさせてくれました。それで、ここに少し単純なバージョンのコードがあります。変更点は次のとおりです。

1. 私はもはや127の累乗を実行していませんが、実際にはcodePointAt数値を文字列として連結し、結果を各入力文字列のBigIntegerに変換してから、2つのBigIntegerを追加しています。
2. 答えをコンパクトにするために、私は最終的な答えでmod 2^1024を実行しています。

速度はこれ以上良くはありませんが（おそらく少し悪いです！）、速度の測定方法は正しくないと思います。おそらく関数呼び出しにかかる時間も測定するからです。

これが変更されたコードです。これは、2 ^ 1024の結果スペースで繰り返しが発生する可能性があるような不幸なケースではありますが、すべての条件を満たしていますか？

public static BigInteger hashStringConcatenation(String str1, String str2) {
    if(str1==null || str1.isEmpty() || str2 == null || str2.isEmpty()) {
        return null;
    }
    BigInteger bA, bB;
    String codeA = "", codeB = "";
    for(int i=0; i<str1.length(); i++) {
        codeA += str1.codePointAt(i);
    }
    for(int i=0; i<str2.length(); i++) {
        codeB += str2.codePointAt(i);
    }
    bA = new BigInteger(codeA);
    bB = new BigInteger(codeB);
    return bA.add(bB).mod(BigInteger.valueOf(2).pow(1024));
}

Answer 7

少し変更された機能はどうですか？

public static BigInteger hashStringConcatenation(String str1, String str2) {
    BigInteger bA = BigInteger.ZERO, bB = BigInteger.ZERO;
    StringBuffer codeA = new StringBuffer(), codeB = new StringBuffer();
    for(int i=0; i<str1.length(); i++) {
        codeA.append(str1.codePointAt(i)).append("0");
    }
    for(int i=0; i<str2.length(); i++) {
        codeB.append(str2.codePointAt(i)).append("0");
    }
    bA = new BigInteger(codeA.toString());
    bB = new BigInteger(codeB.toString());
    return bA.multiply(bB).mod(BigInteger.valueOf(2).pow(1024));
}

ここでは、各文字コードの間に区切り文字「0」を追加します。したがって、文字 11 111 と 111 11 の組み合わせは、連結によって 110111 と 111011 が生成されるため、関数を混乱させることはありません。ただし、要件 2 を破ることはありません。元の質問。

2^1024 の範囲内ではありますが、これで問題は解決しますか?

Answer 8

@gkuzminの提案に従って変更されたコードは次のとおりです。

public static BigInteger hashStringConcatenation(String str1, String str2) {
    BigInteger bA = BigInteger.ZERO, bB = BigInteger.ZERO;
    StringBuffer codeA = new StringBuffer(), codeB = new StringBuffer();
    for(int i=0; i<str1.length(); i++) {
        codeA.append(str1.codePointAt(i));
    }
    for(int i=0; i<str2.length(); i++) {
        codeB.append(str2.codePointAt(i));
    }
    bA = new BigInteger(codeA.toString());
    bB = new BigInteger(codeB.toString());
    return bA.multiply(bB).mod(BigInteger.valueOf(2).pow(1024));
}

結果では、加算する代わりに bA を bB で乗算していることに注意してください。

また、@gkuzmin の推奨テスト関数を追加しました。

public static void breakTest2() {
    String firstString=new StringBuffer().append((char)11).append((char)111).toString();
    String secondString=new StringBuffer().append((char)111).append((char)11).toString();
    BigInteger hash1 = hashStringConcatenation(firstString,"arbitrary_string");
    BigInteger hash2 = hashStringConcatenation(secondString,"arbitrary_string");
    System.out.println("Is hash equal: "+hash1.equals(hash2));
    System.out.println("Conflicted values: {"+firstString+"},{"+secondString+"}");
}

数値のみを持つ文字列を使用した別のテスト:

public static void breakTest1() {
    Hashtable<String,String> seenTable = new Hashtable<String,String>();
    for (int i=0; i<100; i++) {
        for(int j=i+1; j<100; j++) {
            String hash = hashStringConcatenation(""+i, ""+j).toString();
            if(seenTable.contains(hash)) {
                System.out.println("Duplication for " + seenTable.get(hash) + " with " + i + "-" + j);
            }
            else {
                seenTable.put(hash, i+"-"+j);
            }
        }
    }
}

コードが実行されます。もちろん、完全なチェックではありませんが、breakTest1() 関数には問題はありません。@gkuzmin の関数は次のように表示します。

Is hash equal: true
Conflicted values: {                    o},{o                         }

2 つの文字列が同じハッシュを生成するのはなぜですか? どちらの場合も、文字列「11111arbitrary_string」を効果的に処理しているためです。これは問題です。

Answer 9

String#hashCode に基づいて構築されているため、これは完全なハッシュ関数ではないため、条件 4 を満たしていません。

public static long hashStringConcatenation(String str1, String str2) {
    int h1 = str1.hashCode();
    int h2 = str2.hashCode();

    if ( h1 < h2 )
    {
        return ((long)h1)<<32 & h2;
    }
    else
    {
        return ((long)h2)<<32 & h1;
    }
}

Answer 10

@Anirban Basuが別の解決策を提案したため、別の回答を追加することにしました。したがって、彼の投稿へのリンクを提供する方法がわかりません。誰かがその方法を知っている場合は、修正してください。

Anirban のソリューションは次のようになります。

public static BigInteger hashStringConcatenation(String str1, String str2) {
    if(str1==null || str1.isEmpty() || str2 == null || str2.isEmpty()) {
        return null;
    }
    BigInteger bA, bB;
    String codeA = "", codeB = "";
    for(int i=0; i<str1.length(); i++) {
        codeA += str1.codePointAt(i);
    }
    for(int i=0; i<str2.length(); i++) {
        codeB += str2.codePointAt(i);
    }
    bA = new BigInteger(codeA);
    bB = new BigInteger(codeB);
    return bA.add(bB).mod(BigInteger.valueOf(2).pow(1024));
}

新しいソリューションはハッシュ関数のように見えますが、まだいくつかの問題があります。これについて考える必要があることをお勧めします：

1. たぶん、関数の引数として使用されたときにスローする方が良いでしょうNullPointerExceptionか？空の文字列のハッシュを計算しないでよろしいですか?IllegalArgumentExceptionnull
2. 大量の文字列を連結するには、演算子StringBufferの代わりに使用することをお勧めします。+このクラスを使用すると、コードのパフォーマンスに大きなプラスの影響が生じます。
3. あなたのハッシュ関数はあまり安全ではありません.文字列を計算するのは本当に簡単で、競合が発生します.

このコードを試して、ハッシュ関数の衝突を実証できるアルゴリズムを確認できます。

public static void main(String[] args){
    String firstString=new StringBuffer().append((char)11).append((char)111).toString();
    String secondString=new StringBuffer().append((char)111).append((char)11).toString();

    BigInteger hash1 = hashStringConcatenation(firstString,"arbitrary_string");
    BigInteger hash2 = hashStringConcatenation(secondString,"arbitrary_string");
    System.out.println("Is hash equal: "+hash1.equals(hash2));
    System.out.println("Conflicted values: {"+firstString+"},{"+secondString+"}");
}

したがって、ハッシュ関数を壊すのは本当に簡単です。さらに、2^1024 の結果空間があるのは良いことですが、実際の実装では多くの競合が非常に近くて単純な文字列にあります。

PSすでに開発されたハッシュアルゴリズム、実際に失敗したハッシュ関数（String過去に最初の16文字のみを使用してハッシュを計算したJavaクラスハッシュ関数など）について何かを読んで、要件に従ってソリューションを検討する必要があると思いますそして実生活。少なくとも、ハッシュの競合を手動で見つけようとすることができます。成功した場合、解決策にはすでにいくつかの問題がある可能性があります。