How to generate strings that share the same hashcode in Java?

 

Questions


An existing system written in Java uses the hashcode of a string as its routing strategy for load balancing.

Now, I cannot modify the system but need to generate strings that share the same hashcode to test the worst condition.

I provide those strings from commandline and hope the system will route all these strings into the same destination.

Is it possible to generate a large numbers of strings that share the same hashcode?

To make this question clear:

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
}

Remarks: Any hashCode value is acceptable. There is no constraint on what the string is. But they should be different from each other.

EDIT:
Override method of String class is not acceptable because I feed those string from command line.

Instrumentation is also not acceptable because that will make some impacts on the system.

 

 

————————————————-

Answer

since you can read chinese you can look at my post
http://www.hetaoblog.com/myblogs/post/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C%E9%9D%A2%E7%9A%84hashcode-string-hashcode.jhtml

see a test method, basically, so long as you match,
a1*31+b1 = a2*31 +b2, which means (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()));

}

you will get

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

edit: someone said this is not straightforward enough. I added below part

    @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

below is the source code, it might be not efficient, but it work:

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;      
    }
}

look at 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;
    }

hashcode,java,string

Facebook Comments

Post a comment