Насколько глупо использовать целочисленное значение ключ для хэш-таблицы? - PullRequest
4 голосов
/ 03 марта 2010

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

Что касается целого числа, насколько глупо запускать хеш-функцию для числа, чтобы сгенерировать ключ?

Я имею в виду, что числа, которые я буду использовать в качестве ключа для хэш-таблицы, всегда будут разными, дубликатов вообще не будет. Разве мне недостаточно использовать оператор mod для «усечения» значения ниже размера хеш-таблицы?

Или есть что-то еще?

Ответы [ 5 ]

4 голосов
/ 03 марта 2010

Это хорошо, если только не существует высокого шанса, что ваши целочисленные ключи равны 62, 93, 124, ... и ваш размер хеш-таблицы равен 31.

См. Какие целочисленные хеш-функции хороши для принятия целочисленного хеш-ключа? , если вы беспокоитесь об этом.

2 голосов
/ 03 марта 2010

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

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

1 голос
/ 03 марта 2010

На мой взгляд, это не глупо. Это может быть не лучшим вариантом, если вы склонны иметь относительно немного значений (в этом случае лучше использовать простой массив).

Я бы использовал оператор по модулю для хеширования целых чисел до размера хеша.

0 голосов
/ 03 марта 2010

как насчет целочисленного использования отсортированного массива и выполнения бинарного поиска?на самом деле то же самое для строки, но для хеширования строки может быть дешевле

0 голосов
/ 03 марта 2010

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

...