Как обеспечить равномерное распределение в HashMap?

HashMap datastructure распределяет ключи среди своих ковшей на основе хэш-кода ключа. В основном, если алгоритм хеширования очень хорош, все ключи будут распределяться между разными ковшиками. Но что, если все ключи возвращают один и тот же хэш-код? Операции вставки/извлечения будут иметь порядок O (n).Как обеспечить равномерное распределение в HashMap?

Если бы я реализовал свой собственный HashMap, как бы я (или что мне делать), чтобы обеспечить равное распределение среди ведер? Есть ли даже способ?

источник

2013-02-25 Kiran K

Но что, если все ключи возвращают один и тот же хэш-код?

Тогда вы проиграли игру, и вы ничего не можете с этим поделать.

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

Теоретически даже злонамеренно выбранные входные значения могут быть распределены разумно равномерно с universal hashing, но на Java это действительно не вариант.

источник

2013-02-25 02:59:47

Запустите что-то вроде DES на клавишах для создания хэшей. Приличный алгоритм шифрования гарантирует, что результаты будут выглядеть случайными.

источник

2013-02-25 03:01:21 stark

Сгенерировать хэши _from what? _ В Java потребитель HashMap, а не автора структуры данных, получает возможность выбора 'hashCode()'. –

Вы можете рандомизировать генерацию хешей, но это создает реальную проблему при поиске. Я мог бы создать HashMap, поддерживаемый массивом TreeMaps. Таким образом, я бы оценил сопоставимость ключей для ввода/извлечения (и, надеюсь, сделает все это в Log (n)). Но это просто откладывает проблему до функции Comparable. Есть ли математическая функция, которую я мог бы использовать вместо этого? Или какой-то другой шаблон дизайна? –

Почему это создает проблему при поиске? Ключ всегда имеет хэши того же значения. – stark

Как обеспечить равномерное распределение в HashMap?

ответ

Смежные вопросы