Comment générer des chaînes qui partagent le même hashcode en Java?

depuis que vous pouvez lire le chinois, vous pouvez consulter mon message http://www.hetaoblog.com/myblogs/post/%E8%AF%B4%E4%B8%80%E8%AF%B4java%E9%87%8C% E9% 9D% A2% E7% 9A% 84hashcode-ssortingng-hashcode.jhtml

voir une méthode de test, fondamentalement, tant que vous correspondez, a1 * 31 + b1 = a2 * 31 + b2, ce qui signifie (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())); } 

tu auras

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

edit: quelqu’un a dit que ce n’est pas assez simple. J’ai ajouté la partie ci-dessous

  @Test public void testN() throws Exception { List 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 

ci-dessous est le code source, cela peut ne pas être efficace, mais ça marche:

 public class HashCUtil { private static Ssortingng[] base = new Ssortingng[] {"Aa", "BB"}; public static List generateN(int n) { if(n <= 0) { return null; } List list = generateOne(null); for(int i = 1; i < n; ++i) { list = generateOne(list); } return list; } public static List generateOne(List strList) { if((null == strList) || (0 == strList.size())) { strList = new ArrayList(); for(int i = 0; i < base.length; ++i) { strList.add(base[i]); } return strList; } List result = new ArrayList(); for(int i = 0; i < base.length; ++i) { for(String str: strList) { result.add(base[i] + str); } } return result; } } 

regardez Ssortingng.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; } 

Je pense que trouver une chaîne d’égale-hachage à partir d’une longue chaîne est trop difficile, c’est facile quand trouver une chaîne d’égale-hachage d’une chaîne courte (2 ou 3). Regardez l’équation ci-dessous. (désolé, je ne peux pas poster d’image parce que je suis nouveau membre)

Notez que, “FB” et “Ea” ont le même hashcode, et que deux chaînes comme s1 + “FB” + s2 et s1 + “Ea” + s2 auront le même hashcode. Donc, la solution de facilité consiste à trouver une sous-chaîne à 2 caractères d’une chaîne existante et à la remplacer par une sous-chaîne à 2 caractères avec le même hashcode.

Exemple: nous avons la chaîne “helloworld”, où nous obtenons une sous-chaîne à deux caractères “il”, hashcode (“il”) = ‘h’ * 31 + ‘e’ = (‘h’ * 31 + 31) + (‘e’ – 31) = (‘h’ + 1) * 31 + ‘F’ = ‘i’ + ‘F’ = hashcode (“iF”) donc la chaîne désirée est “iFlloworld” nous avons augmenté le “h” de 1, nous pouvons augmente de 2, ou 3, etc. (mais sera erroné s’il déborde de la valeur du caractère)

Le code ci-dessous fonctionne bien avec petit niveau, il se trompera si le niveau est grand, faites déborder la valeur du caractère, je le corrigerai plus tard si vous le souhaitez (ce code change 2 premiers caractères, mais je modifierai le code en 2 derniers caractères car 2 premiers caractères sont calculés avec la plus grande valeur)

  public static Ssortingng samehash(Ssortingng 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; } 

Vous pouvez instrumenter la classe java.lang.Ssortingng afin que sa méthode hashCode () retourne toujours le même nombre.

Je suppose que Javassist est le moyen le plus simple de faire une telle instrumentation.

En bref:

• obtenir une instance de java.lang.instrument.Instrumentation à l’aide d’un agent Java (voir la documentation du paquet java.lang.instrument pour plus de détails)
• redéfinir la classe java.lang.Ssortingng à l’aide de la méthode Instrumentation.redefineClasses (ClassDefinition [])

Le code ressemblera (à peu près) à:

 ClassPool classPool = new ClassPool(true); CtClass ssortingngClass = classPool.get("java.lang.Ssortingng"); CtMethod hashCodeMethod = ssortingngClass.getDeclaredMethod("hashCode", null); hashCodeMethod.setBody("{return 0;}"); byte[] bytes = ssortingngClass.toBytecode(); ClassDefinition[] classDefinitions = new ClassDefinition[] {new ClassDefinition(Ssortingng.class, bytes); instrumentation.redefineClasses(classDefinitions);// this instrumentation can be obtained via Java-agent 

N’oubliez pas non plus que le fichier manifeste de l’agent doit spécifier Can-Redefine-Classes: true pour pouvoir utiliser la méthode redefineClasses (ClassDefinition []).

Je me demandais s’il y avait une solution “universelle”; par exemple, une chaîne constante XYZ , telle que

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

pour toute chaîne s . Trouver une telle chaîne implique de résoudre une équation assez compliquée … qui dépassait mes capacités mathématiques rouillées. Mais alors je me suis rendu compte que h == 31*h + ch est toujours true lorsque h et ch sont tous deux nuls!

Sur la base de cet aperçu, la méthode suivante devrait créer une autre chaîne avec le même hashcode comme argument:

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

Si les caractères NUL vous posent problème, l’ajout d’ une chaîne dont le hashcode est zéro fonctionnerait également … même si les chaînes en collision seraient plus longues que si vous utilisiez zéro.

 Ssortingng s = "Some Ssortingng" for (int i = 0; i < SOME_VERY_BIG_NUMBER; ++i) { String copy = new String(s); // Do something with copy. } 

Est-ce que cela fonctionnera pour vous? Il crée simplement de nombreuses copies du même littéral Ssortingng que vous pouvez ensuite utiliser lors de vos tests.