Столкновение строк хэш-кода Java ()

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

Подскажите, пожалуйста, что такое столкновения и как их уменьшить?

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

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

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

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

Answer 2

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

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

public class MyString {
  private final char[] arr;

  // Constructor and other methods.

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

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

Answer 3

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