Как сгенерировать строки, которые используют один и тот же хэш-код в Java?

Существующая система, написанная на 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 неприемлем, поскольку я корню эту строку из командной строки.

Инструментарий также неприемлем, потому что это повлияет на систему.

Ответы

Ответ 1

так как вы можете читать китайский, вы можете посмотреть мой пост 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

см. метод тестирования, в основном, до тех пор, пока вы соответствуете, 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()));

}

вы получите

изменить: кто-то сказал, что это недостаточно просто. Я добавил ниже часть

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

Ответ 2

Я думаю, что найти строку с равным хешем из длинной строки слишком сложно, это легко, если найти равную хэш-строку короткой строки (2 или 3). Посмотрите на приведенное ниже уравнение. (извините, что я не могу опубликовать изображение, вызывая меня новым членом)

Обратите внимание, что "FB" и "Ea" имеют одинаковый хэш-код, и любые две строки, такие как s1 + "FB" + s2 и s1 + "Ea" + s2, будут иметь один и тот же хэш-код. Таким образом, простое решение находит любую подстроку 2 char существующей строки и заменяет подстроку 2- char тем же хэш-кодом

Exmaple, у нас есть строка "helloworld" get2 char подстрока "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;
}

Ответ 3

Вы можете измерить класс java.lang.String, чтобы его метод hashCode() всегда возвращал тот же номер.

Я полагаю, что Javassist - самый простой способ сделать такую инструментацию.

Короче:

получить экземпляр java.lang.instrument.Instrumentation с помощью Java-агента (подробнее см. пакет java.lang.instrument)
redefine класс java.lang.String с помощью метода Instrumentation.redefineClasses(ClassDefinition [])

Код будет выглядеть примерно так:

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 []).

Ответ 4

Мне было интересно, существует ли "универсальное" решение; например некоторая константная строка XYZ, такая, что

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

для любой строки s. Поиск такой строки предполагает решение довольно сложного уравнения... которое было выше моих ржавых математических способностей. Но потом мне стало ясно, что h == 31*h + ch всегда true, когда h и ch равны нулю!

На основе этого понимания следующий метод должен создать другую строку с тем же хэш-кодом, что и аргумент:

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

Если символы NUL являются проблематичными для вас, добавление любой строки, чей хэш-код равен нулю, тоже будет работать... хотя и столкновение строк будет длиннее, чем если бы вы использовали нуль.

Ответ 5

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

    // Do something with copy.
}

Будет ли это работать на вас? Он просто создает много копий одного и того же строкового литерала, который затем можно использовать при тестировании.