Java HashMap обнаруживает коллизию
Существует ли способ обнаружить коллизию в карте Хеша Java? Может любой указывать на некоторую ситуацию, где партия коллизии может произойти. Конечно, если Вы переопределяете хэш-код для объекта и просто возвращаетесь, коллизия постоянной величины, несомненно, произойдет. Я не говорю об этом. Я хочу знать в том, что все ситуации другой, который ранее упомянутый, огромное количество коллизий происходит, не изменяя реализацию хэш-кода по умолчанию.
2 ответа
Я создал проект для тестирования таких вещей: 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 с двумя таблицами без размытия - объекты, которые отличаются мало или совсем не используется в младших битах, которые использовались для выбора сегмента - например, новое целое число (1 * 1024) , новое целое число (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
Простой пример: хеширование Long . Очевидно, что есть 64 бита ввода и только 32 бита вывода. Документировано, что хеш Long имеет следующий вид:
(int)(this.longValue()^(this.longValue()>>>32))
т.е. представьте, что это два значения int , прикрепленные друг к другу, и выполните XOR.
Итак, все они будут иметь хэш-код 0:
0
1L | (1L << 32)
2L | (2L << 32)
3L | (3L << 32)
и т. Д.
Я не знаю, считается ли это «огромным количеством коллизий», но это один из примеров, когда коллизии легко произвести.
Очевидно любой хэш, в котором имеется более 2 32 возможных значений, будет иметь коллизии, но во многих случаях их сложнее создать. Например, хотя я определенно встречал хеш-коллизии в String с использованием только значений ASCII, их немного сложнее создать, чем указанные выше.