hashCode, реализация и отношение к HashMap

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

• Наихудший сценарий: каждое хеш-значение одинаково, поэтому все элементы попадают в одно и то же ведро, и в этом случае вы получаете производительность O (n) (при условии, что цепочки представляют собой связанные списки).
• В лучшем случае: каждое значение хеш-функции отличается, поэтому каждый элемент оказывается в другом сегменте, поэтому вы получаете ожидаемую производительность O(1).

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

Вы спросили: «Или я что-то упустил? Пожалуйста, просветите меня».

Да, вы что-то упускаете.

Внутри реализации класса HashMap он защищает от плохих функций хеширования:

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Таким образом, ваши полученные хэш-коды в вашем примере:

k1 - Before: 3366 After: 3566
k2 - Before: 3367 After: 3567
k3 - Before: 3368 After: 3552

Таким образом, даже в вашей небольшой выборке из 3 элементов один из них был перефразирован. Это не защищает от агрессивно-злобных хэш-кодов (от return randomInt(); или return 4; просто невозможно защититься), но защищает от плохо написанных хэш-кодов.

Я также должен отметить, что вы можете многое изменить, используя нетривиальные входные данные. Рассмотрим, например, следующие строки.

k1longer - Before: 1237990607 After: 1304548342
k2longer - Before: 2125494288 After: 2040627866
k3longer - Before: -1281969327 After: -1178377711

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

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;

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

00: 00000000000000000000000000000001
01: 00000000000000000000000000000010
02: 00000000000000000000000000000100
03: 00000000000000000000000000001000
04: 00000000000000000000000000010001
05: 00000000000000000000000000100010
06: 00000000000000000000000001000100
07: 00000000000000000000000010001001
08: 00000000000000000000000100010010
09: 00000000000000000000001000100100
10: 00000000000000000000010001001000
11: 00000000000000000000100010010000
12: 00000000000000000001000100100001
13: 00000000000000000010001001000010
14: 00000000000000000100010010000100
15: 00000000000000001000100100001000
16: 00000000000000010001001000010001
17: 00000000000000100010010000100010
18: 00000000000001000100100001000100
19: 00000000000010001001000010001001
20: 00000000000100010010000100010011
21: 00000000001000100100001000100110
22: 00000000010001001000010001001100
23: 00000000100010010000100010011000 # means a 1 in the 23rd bit position will  
24: 00000001000100100001000100110001  # cause positions 4, 5, 8, 12, and 20 to 
25: 00000010001001000010001001100010  # also be altered
26: 00000100010010000100010011000100
27: 00001000100100001000100110001001
28: 00010001001000010001001100010010
29: 00100010010000100010011000100100
30: 01000100100001000100110001001000
31: 10001001000010001001100010010000

Итак, ваши опасения по поводу «ухудшения времени поиска большого O с O (1) до ... кто знает, насколько плохо ... может быть, хуже, чем O (log n)» и «Не предоставит ли Sun функцию hashCode по умолчанию, которая будет хорошо работать для больших наборов данных?» могут быть отправлены на покой — у них есть меры предосторожности, чтобы этого не произошло.

Если это поможет вам обрести покой, вот теги автора для этого класса. Они буквально все звезды в мире Java. (комментарии с # мои)

 * @author  Doug Lea          # Formerly a Java Community Process Executive Committee member
 * @author  Josh Bloch        # Chief Java architect at Google, amongst other things
 * @author  Arthur van Hoff   # Done too many hardcore Java things to list...
 * @author  Neal Gafter       # Now a lead on the C# team at Microsoft, used to be team lead on javac 

На днях я прочитал запись в блоге Эрика Липперта под названием Рекомендации. и правила для GetHashCode. Хотя примеры кода относятся к C#, большинство общих принципов в равной степени применимы и к Java. Эту статью стоит прочитать, если вы хотите больше узнать о том, для чего используются хеш-коды и как их следует генерировать.

В частности, следующий бит кажется особенно актуальным для вашего вопроса:

Рекомендация: распределение хеш-кодов должно быть случайным

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

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

В случае HashMaps и Strings он должен сопоставить эти хешированные ключи с некоторым смещением сортировки в случайно доступный контейнер, такой как массив, для которого существует ряд решений, но если два ключа «близки», это все равно приведет к тому, что они будут помещены в разные ведра, и это все, о чем мы действительно заботимся.

Для очень больших контейнеров Map (думаю, миллиарды ключей) мы, вероятно, хотим быть немного умнее, но это выходит за рамки того, для чего был разработан Java HashMap.

И последнее замечание: вам не нужно использовать лавинный эффект для создания довольно случайных ключей для строк. Вы хотите выбрать достаточно случайную и быструю функцию.

Если вы посмотрите на исходный код HashMap, там есть хэш-функция, вызываемая со значением key.hashCode(), что означает, что она использует собственный способ назначения хэша. Один момент, в котором нужно быть уверенным, — это не подчиняться контракту equals и hashcode. Я бы посоветовал, если вы ищете улучшение производительности, изучить исходный код и понять количество доступных сегментов и их оптимальное использование.