如何在Java中生成共享相同哈希码的字符串?

问题描述 投票:11回答:5

使用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类的重写方法是不可接受的,因为我从命令行输入了这些字符串。

仪器也是不可接受的,因为这会对系统造成一些影响。

java string hashcode
5个回答
25
投票

基本上看一个测试方法,只要您匹配,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;
    }

8
投票

我认为从长字符串中找到等价的字符串太难了,当找到短字符串(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'=哈希码(“ iF”)所以愿望字符串是“ iFlloworld”我们将'h'增加了1,我们可以增加2或3,依此类推(但如果它溢出char值将是错误的)]

下面的代码在小级别上运行良好,如果级别大,会出错,使char值溢出,如果需要,我稍后会修复(此代码更改了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;
}

2
投票

我想知道是否有一个“通用”解决方案;例如一些常量字符串XYZ,例如


1
投票

您可以检测java.lang.String类,因此其方法hashCode()将始终返回相同的数字。


-1
投票
String s = "Some String"
for (int i = 0; i < SOME_VERY_BIG_NUMBER; ++i) {
    String copy = new String(s);

    // Do something with copy.
}

推荐问答