Làm cách nào để tạo các chuỗi có cùng mã băm trong Java?

Question

Một hệ thống hiện có được viết bằng Java sử dụng mã băm của chuỗi làm chiến lược định tuyến để cân bằng tải.

Hiện tại, tôi không thể sửa đổi hệ thống nhưng cần phải tạo chuỗi có cùng mã băm để kiểm tra điều kiện tồi tệ nhất.

Tôi cung cấp các chuỗi đó từ dòng lệnh và hy vọng hệ thống sẽ định tuyến tất cả các chuỗi này vào cùng một đích.

Có thể tạo một số lượng lớn các chuỗi có cùng mã băm không?

Để làm cho câu hỏi này rõ ràng:

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 
} 

Ghi chú: Bất kỳ giá trị hashCode là chấp nhận được. Không có ràng buộc về chuỗi ký tự là gì. Nhưng chúng phải khác nhau.

CHỈNH SỬA: Phương pháp ghi đè của lớp String không được chấp nhận bởi vì tôi cho chúng ăn chuỗi từ dòng lệnh.

Thiết bị đo đạc cũng không được chấp nhận vì điều đó sẽ gây ra một số tác động lên hệ thống.

Answer 1

vì bạn có thể đọc Trung Quốc, bạn có thể nhìn vào bài của tôi 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

thấy một phương pháp kiểm tra, về cơ bản, miễn là bạn kết hợp, a1 * 31 + b1 = a2 * 31 + b2, có nghĩa là (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())); 

} 

bạn sẽ nhận được

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

chỉnh sửa: ai đó nói đây không phải là đủ đơn giản.Tôi thêm vào bên dưới phần

@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 

dưới đây là mã nguồn, nó có thể là không hiệu quả, nhưng nó hoạt động:

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

nhìn vào 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. 
} 

Điều này có phù hợp với bạn không? Nó chỉ tạo ra rất nhiều bản sao của cùng một chuỗi ký tự mà bạn có thể sử dụng trong thử nghiệm của mình.

Answer 3

Bạn có thể thiết lập lớp java.lang.String để phương thức hashCode() của nó luôn trả về cùng một số.

Tôi cho rằng Javassist là cách dễ nhất để thực hiện một công cụ như vậy.

Nói tóm lại:

• có được một thể hiện của java.lang.instrument.Instrumentation bằng cách sử dụng một Java-agent (xem package java.lang.instrument documentation để biết chi tiết) lớp java.lang.String
• Định nghĩa lại bằng cách sử dụng Instrumentation. redefineClasses (ClassDefinition []) phương pháp

mã sẽ trông giống như (khoảng):

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 

Cũng đừng quên rằng tệp kê khai tác nhân phải chỉ định Can-Redefine-Classes: true để có thể sử dụng phương pháp redefineClasses (ClassDefinition []).

Answer 4

tôi nghĩ rằng tìm một chuỗi băm bằng nhau từ một chuỗi dài quá khó, thật dễ dàng khi tìm chuỗi băm bằng nhau của một chuỗi ngắn (2 hoặc 3). Nhìn vào phương trình bên dưới. (xin lỗi tôi không thể đăng hình ảnh gây cho tôi thành viên mới)

Lưu ý rằng, "FB" và "Ea" có cùng mã băm và hai chuỗi như s1 + "FB" + s2 và s1 + "Ea" + s2 sẽ có cùng một hashcode. Vì vậy, giải pháp dễ dàng được tìm thấy bất kỳ chuỗi 2 char của chuỗi hiện có và thay thế bằng một chuỗi 2 char với cùng hashcode

Exmaple, chúng tôi có chuỗi "helloworld" được 2 char chuỗi con " anh ta ", hashcode (" anh ") = 'h' * 31 + 'e' = ('h' * 31 + 31) + ('e' - 31) = ('h' + 1) * 31 + 'F '=' i '+' F '= hashcode ("iF") vì vậy chuỗi mong muốn là "iFlloworld" chúng tôi đã tăng' h 'lên 1, chúng tôi có thể tăng 2, hoặc 3 v.v ... (nhưng sẽ sai nếu nó tràn giá trị char)

Mã dưới đây chạy tốt với mức độ nhỏ, nó sẽ sai nếu mức độ lớn, làm cho tràn giá trị char, tôi sẽ f ix nó sau này nếu bạn muốn (thay đổi mã này 2 ký tự đầu tiên, nhưng tôi sẽ chỉnh sửa mã đến 2 ký tự cuối cùng bởi vì 2 ký tự đầu tiên là calc với giá trị lớn nhất)

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

tôi đã tự hỏi nếu có là một "phổ" dung dịch; ví dụ. một số chuỗi không đổi XYZ, sao cho

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

cho bất kỳ chuỗi nào s. Tìm kiếm một chuỗi như vậy liên quan đến việc giải quyết một phương trình khá phức tạp ... đó là vượt quá khả năng toán học gỉ của tôi. Nhưng sau đó, tôi nhận ra rằng h == 31*h + ch luôn là true khi h và ch đều bằng không!

Dựa trên cái nhìn sâu sắc rằng, phương pháp sau đây nên tạo một String khác nhau với hashcode giống như đối số của nó:

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

Nếu NUL nhân vật là vấn đề đối với bạn, thêm vào trước bất kỳ Chuỗi có hashcode là zero sẽ làm việc quá ... mặc dù các chuỗi va chạm sẽ dài hơn nếu bạn sử dụng không.