Переход на хэш-функцию HashMap в Java 8

В java 8 java.util.Hashmap я заметил изменение из:

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);

to:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

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

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

Ответы

Ответ 1

Как вы отметили: в Java 8 наблюдается значительное улучшение производительности в HashMap, как описано в JEP-180. В принципе, если хеш-цепочка переходит на определенный размер, HashMap будет (по возможности) заменять его сбалансированным двоичным деревом. Это делает поведение "худшего случая" различных операций O(log N) вместо O(N).

Это не объясняет непосредственно изменение hash. Однако я бы предположил, что оптимизация в JEP-180 означает, что производительность, вызванная плохо распределенной хэш-функцией, менее важна и что анализ затрат-выгод для метода hash изменяется; то есть более сложная версия в среднем менее выгодна. (Bear in bind, когда метод ключа hashcode генерирует коды высокого качества, тогда гимнастика в сложной версии метода hash является пустой тратой времени.)

Но это только теория. Реальное обоснование для изменения hash скорее всего является конфиденциальной Oracle.

Ответ 2

Когда я выполнял разности хеш-реализации, я вижу разницу во времени в nano-секундах, как показано ниже (не очень хорошо, но может иметь некоторый эффект, когда размер огромен ~ 1 миллион +) -

7473 ns - java 7

3981 ns- java 8

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

Ответ 3

В документации Java говорится, что идея состоит в том, чтобы обрабатывать ситуацию, когда старая реализация Linked list выполняет O (n) вместо O (1). Это происходит, когда один и тот же хэш-код генерируется для большого набора данных, вставленных в HashMap.

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