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

Question

Есть ли способ обнаружить коллизию в Java Hash-map? Можно ли указать на какую-то ситуацию, в которой может произойти много столкновений. Конечно, если вы переопределите хеш-код для объекта и просто вернете постоянное значение, то обязательно произойдет коллизия. Я не говорю об этом. Я хочу знать, во всех других ситуациях, кроме упомянутых ранее, происходит коллизия. без изменения реализации хэш-кода по умолчанию.

Answer 1

Я создал проект для сравнения таких вещей: 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 за обнаружением моей небрежности.

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

(Например, функция размазывания HashMap была введена в действие, потому что люди использовали HashMap с объектами с наихудшим типом hashCode () для старой реализации HashMap со степенью двух таблиц без размазывания - объектыкоторые немного или совсем не различаются по своим младшим битам, которые использовались для выбора сегмента - например, new Integer(1 * 1024), new Integer(2 * 1024) * и т. д. Как вы можете видеть, функция размазывания HashMap старается изо всех сил иметь все биты влияют на младшие биты).

Все они, тем не менее, должны хорошо работать в общих случаях - частный случай - это объекты, которые наследуют hashCode () системы.

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

Answer 2

Простой пример: хеширование 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, их немного сложнее произвести, чем выше.

Answer 3

В двух других ответах я вижу хорошее ИМО, но я просто хотел поделиться, что лучший способ проверить, насколько хорошо ваш 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;
   }
}