Jak wygenerować ciągi, które mają ten sam kod skrótu w Javie?

Question

Istniejący system napisany w Javie używa hashcode ciągu jako strategii routingu dla równoważenia obciążenia.

Teraz, I nie można zmodyfikować systemu, ale trzeba wygenerować ciągi, które mają ten sam kod skrótu, aby przetestować najgorszy warunek.

Dostarczam te ciągi z linii poleceń i mam nadzieję, że system prześle wszystkie te struny do tego samego miejsca docelowego.

Czy można wygenerować dużą liczbę ciągów, które mają ten sam kod skrótu?

Aby na to pytanie jasno:

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 
} 

Uwagi: Każda wartość hashCode jest dopuszczalne. Nie ma ograniczeń co do łańcucha znaków. Ale powinny się różnić od siebie.

EDYTOWANIE: Metoda przesłaniania klasy String jest niedopuszczalna, ponieważ przekazuję te ciągi z wiersza poleceń.

Oprzyrządowanie jest również niedopuszczalne, ponieważ spowoduje to pewne skutki w systemie.

Answer 1

ponieważ można odczytać chińskiej można spojrzeć na mój 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

patrz metody badawczej, w zasadzie, tak długo, jak pasują do siebie, a1 * 31 + b1 = a2 * 31 + b2, co oznacza (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())); 

} 

dostaniesz

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

edit: ktoś powiedział, to nie jest wystarczająco proste.Dodałem poniżej części

@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 

Poniżej znajduje się kod źródłowy, to może nie być skuteczna, ale to działa:

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

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

Answer 2

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

    // Do something with copy. 
} 

Czy to zadziała? Po prostu tworzy wiele kopii tego samego literału String, który można następnie wykorzystać w swoich testach.

Answer 3

Możesz zaimplementować klasę java.lang.String, aby jej metoda hashCode() zawsze zwracała ten sam numer.

Przypuszczam, że Javassist to najprostszy sposób na wykonanie takiego oprzyrządowania.

W skrócie:

• uzyskania wystąpienie java.lang.instrument.Instrumentation przy użyciu technologii Java środka (patrz package java.lang.instrument documentation szczegóły)
• Przedefiniowanie klasy java.labg.String za pomocą oprzyrządowania. redefineClasses (ClassDefinition []) metodą

Kod będzie wyglądać (w przybliżeniu)

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 

Należy również pamiętać, że plik manifestu agenta musi określać Can-Redefine-Classes: true, aby móc użyć metody redefineClasses (ClassDefinition []).

Answer 4

I uważam, że wyszukanie łańcuchów o równym haśle z długiego łańcucha jest zbyt trudne, jest to łatwe, gdy odnajdziemy łańcuch równy-haszowi krótkiego ciągu (2 lub 3). Spójrz na równanie poniżej. (przykro mi, nie mogę opublikować obrazu powoduje, że jestem nowym członkiem)

Należy zauważyć, że "FB" i "Ea" mają ten sam kod skrótu, a dowolne dwa ciągi takie jak s1 + "FB" + s2 i s1 + "Ea" + s2 będą miały ten sam hashcode. Tak, proste rozwiązanie jest znalezienie dowolny fragment 2-char istniejącego łańcucha i zastąpić podciągu 2-char z tego samego hashcode

Exmaple mamy ciąg „helloworld” dostać 2-char podciąg " on ", hashcode (" on ") = 'h' * 31 + 'e' = ('h' * 31 + 31) + ('e' - 31) = ('h' + 1) * 31 + 'F '=' i '+' F '= hashcode ("iF") , więc pożądany ciąg to "iFlloworld" zwiększyliśmy "h" o 1, możemy zwiększyć o 2 lub 3 itd. (ale będzie źle, jeśli przepełnia wartość char)

Poniższy kod działa dobrze z małym poziomem, będzie źle, jeśli poziom jest duży, spraw, aby wartość przekroczyła wartość, I f ix go później, jeśli chcesz (ta zmiana kodu 2 pierwsze znaki, ale będę edytować kod do 2 ostatnich zwęgla bo 2 pierwsze znaki są obliczono z największej wartości)

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

Answer 5

Zastanawiałem się, czy nie było „uniwersalne” rozwiązanie; na przykład niektóre stały ciąg XYZ, tak że

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

na dowolny ciąg s. Znalezienie takiego ciągu wymaga rozwiązania dość skomplikowanego równania ... które wykracza poza moje zardzewiałe zdolności matematyczne. Ale wtedy uświadomiłem sobie, że h == 31*h + ch jest zawsze true, kiedy są zerowe!

podstawie tego wglądu, co następuje metoda powinna utworzyć inny ciąg z tego samego hashcode jako argument:

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

Jeżeli znaki NUL są problematyczne dla ciebie, poprzedzenie żadnego ciąg którego hashcode jest zero będzie działa też ... chociaż zderzające się struny będą dłuższe niż przy zerowym użyciu.