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

Question

Итак, я задал еще один связанный вопрос: хеш-функция java-строки с лавинным эффектом , но у меня сейчас другой, связанный вопрос.

Что я установил в этом вопросе, так это то, что функция hashCode () для String не имеет лавинного эффекта. Это означает, например, что если у меня есть строки «k1», «k2», «k3» и я вызываю hashCode () для каждого, возвращаемые значения будут смежными.

Теперь, основываясь на моих воспоминаниях о структурах данных 101, у меня сложилось впечатление, что это плохо. Потому что, предполагая, что HashMap выбирает сегменты алгоритмом что-то вроде:

class HashMap {
    private int capacity;
    private int chooseBucket(String key) {
        return key.hashCode() % capacity;
    }
}

Это будет означать, что подобные ключи хранятся в смежных сегментах, что приводит к более высокой частоте коллизий, что снижает время поиска больших O из O (1) до ... кто знает, как плохо ... может быть хуже, чем O (журнал N).

Типы ответов, которые я получил на свой первый вопрос, были такими: «лавинный эффект здесь не нужен», «он предназначен только для криптографических хеш-функций» и «реализация hashCode для строк быстрая и хорошо работает для маленькие хеш-карты.

Что меня смущает. Все структуры данных быстры, когда они маленькие. Разве Sun не предоставит функцию hashCode по умолчанию, которая будет хорошо работать для больших наборов данных? Именно тогда производительность HashMap действительно имеет значение, не так ли?

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

Answer 1

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

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

---

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

Answer 2

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

Да, вы что-то упустили.

Внутри реализации класса 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

Таким образом, даже при небольшом размере выборки из трех элементов один из них был перефразирован. Теперь он не защищает от агрессивно злых хеш-кодов (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 

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

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

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