Какую функцию хэширования использует Java для реализации класса Hashtable?

Ответ 1

Когда ключ добавляется или запрашивается из HashMap в OpenJDK, поток выполнения следующий:

• Ключ преобразуется в 32-битное значение с использованием метода hashCode(), определенного разработчиком.
• 32-битное значение затем преобразуется с помощью второй хэш-функции (из которой Andrew отвечает исходный код) в смещение внутри хеш-таблицы. Эта вторая хэш-функция обеспечивается реализацией HashMap и не может быть переопределена разработчиком.
• Соответствующая запись хэш-таблицы содержит ссылку на связанный список или нуль, если ключ еще не существует в хэш-таблице. Если есть коллизии (несколько ключей с одинаковым смещением), ключи вместе со своими значениями просто собираются в отдельном списке.

Если размер хэш-таблицы был выбран соответствующим образом высоким, количество столкновений будет ограничено. Таким образом, один поиск занимает в среднем только постоянное время. Это называется ожидаемым постоянным временем. Однако, если злоумышленник контролирует ключи, вставленные в хеш-таблицу, и знание используемого алгоритма хэширования, он может спровоцировать много хеш-коллизий и, следовательно, заставить линейное время поиска. Вот почему некоторые реализации хеш-таблицы были недавно изменены, чтобы включить случайный элемент, который усложняет для злоумышленника предсказать, какие ключи вызовут столкновения.

Некоторые виды ASCII

key.hashCode()
     |
     | 32-bit value
     |                              hash table
     V                            +------------+    +----------------------+
HashMap.hash() --+                | reference  | -> | key1 | value1 | null |
                 |                |------------|    +----------------------+
                 | modulo size    | null       |
                 | = offset       |------------|    +---------------------+
                 +--------------> | reference  | -> | key2 | value2 | ref |
                                  |------------|    +---------------------+
                                  |    ....    |                       |
                                                      +----------------+
                                                      V
                                                    +----------------------+
                                                    | key3 | value3 | null |
                                                    +----------------------+

Ответ 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);
}

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

HashMap также использует метод для определения индекса хеш-кода (так как длина всегда равна 2, вы можете использовать и вместо%):

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

Метод put выглядит примерно так:

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

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

Ответ 3

Хеширование в целом делится на два этапа: а. Хэш-код б. Сжимая

На шаге a. генерируется целое число, соответствующее вашему ключу. Это может быть изменено вами на Java.

На шаге b. метод сжатия применяется Java для отображения целого числа, возвращаемого на этапе a. к слоту в хэш-карте или хэш-таблице. Этот метод сжатия не может быть изменен.

Ответ 4

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

Java Hashtable использует хеш-значение как индекс в массиве, где хранится фактический объект, принимая во внимание арифметику и коллизии по модулю. Однако это не хеширование.

Реализация java.util.HashMap выполняет некоторую дополнительную замену бит на хэш-значение перед индексированием для защиты от чрезмерных коллизий в некоторых случаях. Он называется "дополнительный хеш", но я не думаю, что это правильный термин.

Ответ 5

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Это последняя хеш-функция, используемая классом hashMap в Java

Ответ 6

Чтобы сделать это очень просто, второе хеширование - это не что иное, как поиск номера индекса массива bucket, в котором будет сохранена новая пара ключей. Это сопоставление выполняется, чтобы получить индексный номер от большего значения int хэш-кода ключа obj. Теперь, если два неравных ключевых объекта имеют один и тот же хэш-код, тогда произойдет столкновение, поскольку они будут сопоставлены с одним и тем же индексом массива. В этом случае второй ключ вместе с ним будет добавлен в связанный список. Здесь индекс массива укажет на добавленный последний node.