16

Java で記述された既存のシステムは、負荷分散のためのルーティング戦略として文字列のハッシュコードを使用します。

システムを変更することはできませんが、同じハッシュコードを共有する文字列を生成して、最悪の状態をテストする必要があります。

これらの文字列をコマンドラインから提供し、システムがこれらすべての文字列を同じ宛先にルーティングすることを願っています。

同じハッシュコードを共有する多数の文字列を生成することは可能ですか?

この質問を明確にするために：

String[] getStringsInSameHashCode(int number){
    //return an array in length "number"
    //Every element of the array share the same hashcode. 
    //The element should be different from each other
}

備考: 任意の hashCode 値を使用できます。文字列が何であるかについての制約はありません。しかし、それらは互いに異なっている必要があります。

EDIT：コマンドラインからこれらの文字列をフィードするため、Stringクラスのオーバーライドメソッドは受け入れられません。

システムに何らかの影響を与えるため、インストルメンテーションも受け入れられません。

4

6 に答える 6

34

基本的に、a1*31+b1 = a2*31 +b2 と一致する限り、テスト メソッドを参照してください。つまり、(a1-a2)*31=b2-b1 を意味します。

public void testHash()
{
    System.out.println("A:" + ((int)'A'));
    System.out.println("B:" + ((int)'B'));
    System.out.println("a:" + ((int)'a'));

    System.out.println(hash("Aa".hashCode()));
    System.out.println(hash("BB".hashCode()));
    System.out.println(hash("Aa".hashCode()));
    System.out.println(hash("BB".hashCode()));


    System.out.println(hash("AaAa".hashCode()));
    System.out.println(hash("BBBB".hashCode()));
    System.out.println(hash("AaBB".hashCode()));
    System.out.println(hash("BBAa".hashCode()));

}

あなたが得る

A:65
B:66
a:97
2260
2260
2260
2260
2019172
2019172
2019172
2019172

編集：誰かがこれは簡単ではないと言いました. 下の部分を追加しました

    @Test
    public void testN() throws Exception {
        List<String> l = HashCUtil.generateN(3);
        for(int i = 0; i < l.size(); ++i){
            System.out.println(l.get(i) + "---" + l.get(i).hashCode());
        }
    }
AaAaAa---1952508096
AaAaBB---1952508096
AaBBAa---1952508096
AaBBBB---1952508096
BBAaAa---1952508096
BBAaBB---1952508096
BBBBAa---1952508096
BBBBBB---1952508096

以下はソースコードです。効率的ではないかもしれませんが、動作します:

public class HashCUtil {

    private static String[] base = new String[] {"Aa", "BB"};

    public static List<String> generateN(int n)
    {
        if(n <= 0)
        {
            return null;
        }

        List<String> list = generateOne(null);
        for(int i = 1; i < n; ++i)
        {
            list = generateOne(list);
        }

        return list;
    }


    public static List<String> generateOne(List<String> strList)
    {   
        if((null == strList) || (0 == strList.size()))
        {
            strList = new ArrayList<String>();
            for(int i = 0; i < base.length; ++i)
            {
                strList.add(base[i]);
            }

            return strList;
        }

        List<String> result = new ArrayList<String>();

        for(int i = 0; i < base.length; ++i)
        {
            for(String str: strList)
            {   
                result.add(base[i]  + str);
            }
        }

        return result;      
    }
}

String.hashCode() を見てください

   public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }
于 2012-10-17T02:36:59.380 に答える
9

長い文字列からイコール ハッシュ文字列を見つけるのは難しいと思いますが、短い文字列 (2 または 3) のイコール ハッシュ文字列を見つけるのは簡単です。下の方程式を見てください。（すみません、私は新しいメンバーのせいで画像を投稿できません）

"FB" と "Ea" は同じハッシュコードを持ち、s1+"FB"+s2 と s1+"Ea"+s2 のような 2 つの文字列は同じハッシュコードを持つことに注意してください。したがって、簡単な解決策は、既存の文字列の 2 文字の部分文字列を見つけて、同じハッシュコードを持つ 2 文字の部分文字列に置き換えることです

例として、文字列 "helloworld" から 2 文字の部分文字列 "he" を取得します。hashcode("he") = 'h'*31 + 'e' = ('h'*31 + 31) + ('e' - 31) = ('h'+1)*31 + 'F' = 'i' + 'F' = hashcode("iF") したがって、欲望の文字列は "iFlloworld" です。 'h' を 1 増やしました。 2、または 3 など増加します (ただし、char 値をオーバーフローするとエラーになります)

以下のコードは小さいレベルでうまく動作します。レベルが大きいと問題が発生し、char 値がオーバーフローします。必要に応じて後で修正します (このコードは最初の 2 文字を変更しますが、コードを最後の 2 文字に編集します。最初の 2 文字は最大値で計算されます)

    public static String samehash(String s, int level) {
    if (s.length() < 2)
        return s;
    String sub2 = s.substring(0, 2);
    char c0 = sub2.charAt(0);
    char c1 = sub2.charAt(1);
    c0 = (char) (c0 + level);
    c1 = (char) (c1 - 31 * level);
    String newsub2 = new String(new char[] { c0, c1 });
    String re =  newsub2 + s.substring(2);
    return re;
}
于 2012-10-17T02:48:13.233 に答える
2

「普遍的な」解決策があるかどうか疑問に思っていました。XYZたとえば、次のような定数文字列

    s.hashCode() == (s + XYZ).hashCode()

任意の文字列に対してs。そのような文字列を見つけるには、かなり複雑な方程式を解く必要があります...それは私の錆びた数学的能力を超えていました. h == 31*h + chしかし、いつでもtrue、両方ともゼロhであることに気づきました。ch

その洞察に基づいて、次のメソッドは、引数と同じハッシュコードを持つ別の String を作成する必要があります。

    public String collider(String s) { 
        return "\0" + s;
    }

NUL 文字が問題になる場合は、ハッシュコードが 0 の文字列を先頭に追加しても機能しますが、衝突する文字列は 0 を使用した場合よりも長くなります。

于 2012-10-17T03:15:20.897 に答える
1

java.lang.String クラスを計測して、そのメソッド hashCode() が常に同じ数値を返すようにすることができます。

Javassist は、そのようなインストルメンテーションを行う最も簡単な方法だと思います。

要するに：

  • Java エージェントを使用して java.lang.instrument.Instrumentation のインスタンスを取得します (詳細については、パッケージ java.lang.instrument のドキュメントを参照してください)。
  • Instrumentation.redefineClasses(ClassDefinition[]) メソッドを使用して java.lang.String クラスを再定義する

コードは（おおまかに）次のようになります。

ClassPool classPool = new ClassPool(true);
CtClass stringClass = classPool.get("java.lang.String");
CtMethod hashCodeMethod = stringClass.getDeclaredMethod("hashCode", null);
hashCodeMethod.setBody("{return 0;}");
byte[] bytes = stringClass.toBytecode();
ClassDefinition[] classDefinitions = new ClassDefinition[] {new ClassDefinition(String.class, bytes);
instrumentation.redefineClasses(classDefinitions);// this instrumentation can be obtained via Java-agent

Can-Redefine-Classes: trueまた、redefineClasses(ClassDefinition[]) メソッドを使用できるようにするには、エージェント マニフェスト ファイルで指定する必要があることも忘れないでください。

于 2012-10-17T02:08:34.647 に答える
0 
String s = "Some String"
for (int i = 0; i < SOME_VERY_BIG_NUMBER; ++i) {
    String copy = new String(s);

    // Do something with copy.
}

これはうまくいきますか？テストで使用できる同じ文字列リテラルの多くのコピーを作成するだけです。

于 2012-10-17T02:04:07.420 に答える