Java hashcode() strings collision

Question

Я мало знаю о хэш-кодах. Я нашел этот код, который печатает столкновения.

Не могли бы вы рассказать мне, что такое столкновения и как его уменьшить? Почему мы должны использовать хэш-коды?

public static int getHash(String str, int limit) 
{ 
    int hashCode = Math.abs(str.hashCode()%(limit)); 
    return hashCode; 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) 
{ 
    int hashLimit = 10000; 
    int stringsLimit = 10000; 
    String[] arr = new String[hashLimit]; 
    List<String> test = new ArrayList<String>(); 
    Random r = new Random(2); 
    for (int i = 0 ; i < stringsLimit ; i++) 
    { 
     StringBuffer buf = new StringBuffer(""); 
     for (int j = 0 ; j < 10 ; j++) 
     { 
      char c = (char)(35+60*r.nextDouble()); 
      buf.append(c); 
     } 
     test.add(buf.toString()); 
     //System.out.println(buf.toString()); 
    } 
    int collisions = 0; 
    for (String curStr : test) 
    { 
     int hashCode = getHash(curStr,hashLimit); 
     if (arr[hashCode] != null && !arr[hashCode].equals(curStr)) 
     { 
      System.out.println("collision of ["+arr[hashCode]+"] ("+arr[hashCode].hashCode()+" = "+hashCode+") with ["+curStr+"] ("+curStr.hashCode()+" = "+hashCode+")"); 
      collisions++; 
     } 
     else 
     { 
      arr[hashCode] = curStr; 
     } 
    } 
    System.out.println("Collisions: "+collisions); 
} 

Answer 1

Не могли бы вы рассказать мне, что такое столкновения и как его уменьшить?

Столкновения, когда два неравных объекта имеют одинаковый хэш-код. Они - факт жизни - вам нужно иметь дело с этим.

Почему мы должны использовать хэш-коды?

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

Вы должны never предположить, что два эквивалентных хэш-кода означают, что объекты, из которых они были получены, равны. Верно только обратное: при условии правильной реализации, если два объекта дают разные хэш-коды, то они не равные.

Answer 2

У нас есть «столкновение», если два различные неравномерных объектов имеют один и тот же хэш-код. Это может быть проблемой, например, при попытке использовать оба объекта в качестве ключей в Hashmap.

Answer 3

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

Например, предположим, что вы реализовали наивный hashCode() метод хеширования MyString экземпляров:

public class MyString { 
    private final char[] arr; 

    // Constructor and other methods. 

    public int hashCode() { 
    return arr.length == 0 ? 0 : (int) arr[0]; 
    } 
} 

В этом примере только первый символ используется для создания хэш-код. Поэтому, если вы хотите хэшировать строки: «яблоко», «анаконда», «анекдот», все они будут иметь одинаковое значение хэш-функции. Более эффективный хэш-код будет проверять все буквы в массиве символов, чтобы определить значение хеш-кода, что, мы надеемся, уменьшит вероятность столкновения.