Хэш-таблицы (словарь и т. д.) с целочисленными ключами

Question

Я ломал голову над этим несколько дней...не стесняйтесь опровергать любые мои предположения.

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

Было бы лучше предоставить IEqualityComparer, который делал бы что-то умное с простыми числами и математическими модулями для расчета более распределенного хеша?

Answer 1

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

Я считаю, что способ работы словаря .NET не основан на равномерном распределении хеш-значений.Занимает hash % bucketCount где bucketCount всегда является простым.(Хотя это по памяти, могу ошибаться.)

Конечно, вы все равно можете получить неэффективный набор ключей, если они будут расположены на расстоянии друг от друга по количеству сегментов.Однако так будет всегда — хеш-таблица будет только когда-либо искренне O(1) для всех ключей, если они имеют уникальные значения хеш-функции. и в таблице поддерживается набор сегментов для каждого возможного хеша :) На самом деле это не является проблемой.Если вы случайно узнали, что это воля быть проблемой, тогда да, кастом IEqualityComparer<T> мог бы помочь.

Answer 2

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

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

Если я ошибаюсь, то:.NET, тогда да ладно;это скорее общий ответ.:)

Answer 3

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