Какое свойство битового шаблона вызывает коллизии?

Question

Я читал о подходе Java к рандомизации ключей хеша здесь
Очевидно, что идея состоит в том, чтобы младшие биты были "случайными", чтобы помочь распределению, но я пытаюсь понять это больше.
Таким образом, если у нас есть таблица размером 10, то числа 0,10,20,30,40 и т. Д. Все попадают в сегмент 0, числа 1,11,21,31 и т. Д. Попадают в сегмент 1 и т. Д. (По модулю 10).
Таким образом, изменяя битовые комбинации, вы можете сделать так, чтобы они переходили в разные сегменты, а не в 0.
Но что мне не ясно, так это то, что именно свойство побуждает младшие биты влиять на это, и мы должны их рандомизировать. Итак, мы имеем:

0000 0000 (0)  
0000 1010 (10)  
0001 0100 (20) 
0001 1110 (30)  
0010 1000 (40) 

Какова закономерность в младших битах, которая делает их размещенными в одном и том же слоте?
Возможно, я запутался в следующем? Насколько я понимаю, это некоторая закономерность в битах младшего разряда, которые вызывают конфликты, и мы пытаемся рандомизировать бит, чтобы компенсировать

Answer 1

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

Конкретный пример: предположим, что у вас 32 сегмента, а хэш-коды кратны 8. В таблице используются только 5 наименее значимых битов кода, и 3 из них всегда равны 0. Поэтому только 2 бита определяют сегмент, и вы используете только 4 из 32 ведер:

XXXXXX00000 -> bucket 0
XXXXXX01000 -> bucket 8
XXXXXX10000 -> bucket 16
XXXXXX11000 -> bucket 24

К счастью, в Java все не так плохо, потому что HashMap не использует только самые младшие биты хеш-кода: он скремблирует биты, так что случайно создать плохие сценарии не так просто. Вот выдержка из реализации HashMap в OpenJDK:

/**
 * 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);
}

Answer 2

Некоторые хеш-функции действительно плохо справляются с рандомизацией младших битов.

Одним из классических случаев является использование аппаратных адресов в качестве хеша для ссылок на объекты ("указатели" в C), которые в противном случае были бы разумным способом дешевого получения уникального номера для идентификатора объекта. Это работало бы хорошо, если бы количество блоков в хэш-таблице было простым числом, но для реализаций хеша, где число блоков всегда является степенью 2, тот факт, что все хэши делятся на 8, означал бы, что большинство блоков были пустыми.

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