Take the 2-minute tour ×

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.

share|improve this question
using equals string is not an option ? –  Jigar Joshi Oct 17 '12 at 1:54
look at the String source code. –  Hovercraft Full Of Eels Oct 17 '12 at 1:54
Do they need to be Strings with different values or just different String objects? –  Code-Guru Oct 17 '12 at 1:54
I know how java generate the hashcode for string, but have no ideas how to generate different string literal with same hashcode. I cannot override any method of string. @Code-Guru –  StarPinkER Oct 17 '12 at 2:02
add comment

5 Answers

up vote 1 down vote accepted

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'));




you will get


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

    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());

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)

            return strList;


            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;

            hash = h;
        return h;
share|improve this answer
well, that's fine if this is SO's rule or culture to provide english only link... I just want to provide more to the author; while for the problem itself, i think i've explained enough using demo codes and some words here... –  hetaoblog Oct 17 '12 at 2:55
1) Yes it is. 2) The demo codes and words don't actually answer the question. The question is about how to generate collisions. An explanation of how/why the collisions occur is not relevant. –  Stephen C Oct 17 '12 at 3:01
I think this is a very good answer, although the generated string is very long if N is very large. –  StarPinkER Oct 17 '12 at 14:25
add comment

You can instrument the java.lang.String class so its method hashCode() will always return the same number.

I suppose Javassist is the easiest way to do such an instrumentation.

In short:

  • obtain an instance of java.lang.instrument.Instrumentation by using a Java-agent (see package java.lang.instrument documentation for details)
  • redefine java.lang.String class by using Instrumentation.redefineClasses(ClassDefinition[]) method

The code will look like (roughly):

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

Also don't forget that agent manifest file must specify Can-Redefine-Classes: true to be able to use redefineClasses(ClassDefinition[]) method.

share|improve this answer
Thanks for your answer. Overriding the hashCode method is not acceptable since it will affect the system. The scenario is I need to test the system with those string literal. Modification on the system is definitely unacceptable. –  StarPinkER Oct 17 '12 at 2:35
@Jermaine Xu, this is not overriding, but instrumentation. However yes you do need an ability to relaunch JVM with the "existing system written in Java" and add an agent to JVM via command-line arguments. So if you can't do this, my suggestion is unusable. In this case the "hetaoblog"'s answer should fit your situation:) –  Male Oct 17 '12 at 2:43
Instrumentation is a good idea, but the objectives is testing, so I cannot modify redefine the hashCode method of String. Thanks for your instrumentation idea. –  StarPinkER Oct 17 '12 at 2:46
add comment
String s = "Some String"
for (int i = 0; i < SOME_VERY_BIG_NUMBER; ++i) {
    String copy = new String(s);

    // Do something with copy.

Will this work for you? It just creates a lot of copies of the same String literal that you can then use in your testing.

share|improve this answer
Sorry I didn't make it clear enough. Same string literal is not acceptable, because the string is the primary key in the database, I do need different string literals. –  StarPinkER Oct 17 '12 at 2:06
add comment

I think find a equal-hash string from a long string is too hard, it's easy when find equal-hash string of an short string (2 or 3). Look at the equation below. (sorry I cant post image cause me new member)

Notice that, "FB" and "Ea" have the same hashcode, and any two strings like s1+"FB"+s2 and s1+"Ea"+s2 will have the same hashcode. So, the easy solution is finding any 2-char substring of existing string and replace with a 2-char substring with the same hashcode

Exmaple, we have the string "helloworld" get 2-char substring "he", hashcode("he") = 'h'*31 + 'e' = ('h'*31 + 31) + ('e' - 31) = ('h'+1)*31 + 'F' = 'i' + 'F' = hashcode("iF") so the desire string is "iFlloworld" we have increased 'h' by 1, we can increase by 2, or 3 etc (but will be wrong if it overflow the char value)

The below code run well with small level, it will wrong if the level is big, make the char value overflow, I will fix it later if you want (this code change 2 first chars, but I will edit code to 2 last chars because 2 first chars are calc with largest value)

    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;
share|improve this answer
I just edit the question. We are towards the right direction I think. Thanks. –  StarPinkER Oct 17 '12 at 2:55
I think the best question is "write a reverse hashcode function" –  yelliver Oct 17 '12 at 3:04
Actually any old string will do, any hashcode value will do. –  StarPinkER Oct 17 '12 at 3:15
add comment

I was wondering if there was a "universal" solution; e.g. some constant string XYZ, such that

    s.hashcode() == (s + XYZ).hashcode() 

for any string s. Finding such a string involves solving a fairly complicated equation ... which was beyond my rusty mathematical ability. But then it dawned on me that h == 31*h + ch is always true when h and ch are both zero!

Based on that insight, the following method should create a different String with the same hashcode as its argument:

    public String collider(String s) { 
        return 0 + s;

If NUL characters are problematic for you, prepending any string whose hashcode is zero would work too ... albeit that the colliding strings would be longer than if you used zero.

share|improve this answer
Let me have a try whether the \0 solution will work or not. Thanks. –  StarPinkER Oct 17 '12 at 4:28
add comment

Your Answer


