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 值都是可以接受的。字符串是什么没有限制。但它们应该彼此不同。

编辑： 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 字符子字符串替换

例如，我们有字符串 "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个第一个字符是最大值的calc）

    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为零！

基于这种见解，下面的方法应该创建一个不同的字符串，它的参数具有相同的哈希码：

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

如果 NUL 字符对您来说有问题，那么添加任何哈希码为零的字符串也可以工作......尽管冲突的字符串会比您使用零时更长。

于 2012-10-17T03:15:20.897 回答
2

给定字符串 X，那么 String Y = "\u0096\0\0ɪ\0ˬ" + X 将与 X 共享相同的哈希码。

解释：

  1. String.hashcode() 返回 Integer，Java 中的每个 Integer X 都具有 X = X + 2 * (Integer.MAX_VALUE + 1) 的属性。这里，Integer.MAX_VALUE = 2 ^ 31 - 1；

  2. 所以我们只需要找到String M，它的性质是M的hashcode % (2 * (Integer.MAX_VALUE + 1)) = 0;

  3. 我发现“\u0096\0\0ɪ\0ˬ”：\u0096的ascii码是150，\0的ascii码是0，ɪ的ascii码是618，ˬ的ascii码是748，所以它的hashcode是150 * 31 ^ 5 + 618 * 31 ^ 2 + 748 = 2 ^ 32 = 0；

这取决于你想要哪个字符串，我选择这个。

于 2020-07-22T08:52:14.263 回答
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 回答