Java HashMap обнаруживает столкновение

Я создал проект для сравнения таких вещей: http://code.google.com/p/hashingbench/ (для хэш-таблиц с фильтрами цепочки, открытой адресации и Блума).

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

public int scramble(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Таким образом, для возникновения коллизии в HashMap необходимым и достаточным условием является следующее: scramble(k1.hashCode()) == scramble(k2.hashCode()). Это всегда верно, если k1.hashCode() == k2.hashCode() (иначе функция смазывания/скремблирования не была бы будет функцией), так что это достаточно, но не необходимое условие для возникновения коллизии.

Редактировать: На самом деле приведенное выше необходимое и достаточное условие должно было быть compress(scramble(k1.hashCode())) == compress(scramble(k2.hashCode())) — функция compress принимает целое число и сопоставляет его с {0, ..., N-1}, где N — это количество сегментов, поэтому в основном выбирается сегмент. Обычно это просто реализуется как hash % N или, когда размер хеш-таблицы равен степени двойки (и это на самом деле является мотивацией для использования размеров хеш-таблицы, равной степени двойки), как hash & N (быстрее). («сжатие» — это имя, которое Гудрич и Тамассия использовали для описания этого шага в Структурах данных и алгоритмах в Java). Спасибо ILMTitan за то, что заметили мою неряшливость.

PS: На самом деле, абсолютно уродливый случай, который побудил разработчиков вставить функцию смазывания, - это hashCode() Floats/Double и использование в качестве ключей значений: 1.0, 2.0, 3.0, 4.0 ..., все они имеют одинаковые (нулевые) младшие биты. Это соответствующий старый отчет об ошибке: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4669519

Простой пример: хеширование Long. Очевидно, что есть 64 бита ввода и только 32 бита вывода. Хэш Long задокументирован как:

(int)(this.longValue()^(this.longValue()>>>32))

то есть представьте, что это два значения int, застрявшие рядом друг с другом, и XOR их.

Таким образом, все они будут иметь хэш-код 0:

0
1L | (1L << 32)
2L | (2L << 32)
3L | (3L << 32)

так далее

Я не знаю, считается ли это «огромным количеством столкновений», но это один из примеров, когда столкновения легко сфабриковать.

Очевидно, что любой хэш, в котором имеется более 2³² возможных значений, будет иметь коллизии, но во многих случаях их сложнее создать. Например, хотя я определенно видел коллизии хэшей на String, используя только значения ASCII, их немного сложнее создать, чем выше.

Два других ответа я вижу в хорошем ИМО, но я просто хотел поделиться тем, что лучший способ проверить, насколько хорошо ваш hashCode() ведет себя в HashMap, - это фактически сгенерировать большое количество объектов из вашего класса, поместить их в конкретную реализацию HashMap как ключ и тест загрузки процессора и памяти. 1 или 2 миллиона записей — хорошее число для измерения, но вы получите наилучшие результаты, если протестируете с ожидаемыми размерами карты.

Я только что посмотрел на класс, который сомневался в его хэш-функции. Поэтому я решил заполнить HashMap случайными объектами этого типа и проверить количество столкновений. Я протестировал две реализации hashCode() исследуемого класса. Итак, я написал в groovy класс, который вы видите внизу, расширяющий реализацию HashMap openjdk для подсчета коллизий в HashMap (см. countCollidingEntries()). Обратите внимание, что это не настоящие коллизии всего хэша, а коллизии в массиве, содержащем записи. Индекс массива рассчитывается как hash & (length-1), что означает, что чем меньше размер этого массива, тем больше коллизий вы получите. И размер этого массива зависит от initialCapacity и loadFactor из HashMap (он может увеличиваться, когда put() больше данных).

В конце концов, я посчитал, что смотреть на эти цифры не имеет большого смысла. Тот факт, что HashMap работает медленнее с плохим методом hashCode(), означает, что, просто сравнив вставку и извлечение данных из карты, вы фактически узнаете, какая реализация hashCode() лучше.

public class TestHashMap extends HashMap {

   public TestHashMap(int size) {
      super(size);
   }

   public TestHashMap() {
      super();
   }

   public int countCollidingEntries() {
      def fs = this.getClass().getSuperclass().getDeclaredFields();
      def table;
      def count =0 ;
      for ( java.lang.reflect.Field field: fs ) {
         if (field.getName() == "table") {
            field.setAccessible(true);
            table = field.get(super);
            break;
         }
      }
      for(Object e: table) {
         if (e != null) {
            while (e.next != null) {
               count++
               e = e.next;
            }
         }
      }
      return count;
   }
}