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

Question

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

Answer 1

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

Помимо хэш-код() ключа, вы должны знать «смазывание» (или «карабкаться», как я его называю в этом проекте) функции Hashtable. Из this list, размазывая функция 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() (в противном случае, размытость/функция скремблирования бы не быть функция), так что это достаточно, но не необходимым условием столкновение произойдет.

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

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

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

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

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

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

Я просто посмотрел на класс, в котором я сомневался в его функции хэширования. Поэтому я решил заполнить HashMap случайными объектами этого типа и проверить количество столкновений. Я проверил две реализации hashCode() класса, находящегося под следствием. Поэтому я написал в groovy класс, который вы видите в нижней части расширения openjdk реализации HashMap, чтобы подсчитать количество столкновений в 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; 
    } 
}