Какая хеш-функция лучше? - PullRequest
Новая
       37

Какая хеш-функция лучше?

0 голосов
/ 04 февраля 2012

Я пишу свою реализацию HashMap на Java. Я использую открытую адресацию для разрешения коллизий. Для лучшего распределения ключей я хочу использовать красивую хеш-функцию для int хеш-кода ключа. Я не знаю, какая хеш-функция для него лучше? 

public int getIndex(K key) { return hash(key.hashCode()) % capacity; }

Мне нужна хеш-функция для хэш-кода ключа.

Ответы [ 2 ]

3 голосов
/ 04 февраля 2012

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

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

Однако это обычно нереалистичный вариант, поэтому вы просто выбираете хеш, чей вывод является непредвзятым и непредсказуемым (тот, который ведет себя как генератор псевдослучайных чисел, но детерминированный).Некоторые такие функции - это хэш-семейство «ропота».

1 голос
/ 04 февраля 2012

Основная проблема с использованием % capacity заключается в том, что он может возвращать отрицательные и положительные значения.

HashMap позволяет избежать этой проблемы, используя степень 2, и использует следующий подход 

 public int getIndex(K key) { return hash(key.hashCode()) & (capacity-1); }

Если емкость не является степенью 2, вы можете игнорировать старший бит (который часто не так уж случайен) 

 public int getIndex(K key) { return (hash(key.hashCode()) & 0x7FFFFFFF) % capacity; }

Фактически используемая хеш-функция может иметь значение. 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 в LinkedList. К сожалению, вам по-прежнему нужно использовать другой hashCode (), а также вы можете создать длинный список строк с базовым хеш-кодом, поэтому изменять его позже будет позже.

Вот список строк, у всех из которых hashCode () равен 0, функция hash () ничего не может с этим поделать.

Почему String hashCode () не кеширует 0?

...