Hashtables (словарь и т.д.) С целыми ключами

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

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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