Отображение целых чисел на весь диапазон

Question

Я использую хеш-таблицу (объект DotNET Dictionary) как часть разреженного двумерного набора данных. Большинство записей в хеш-таблице будут близко друг к другу. Я, вероятно, в итоге получу 100 ~ 10000 записей, все они сгруппированы около нуля. Я читал, что хэш-таблица работает лучше, когда хэши распределены по всему целочисленному (32-битному) диапазону.

Есть ли дешевый способ отобразить последовательные целые числа на совершенно разные значения 1: 1? Мне не нужно отображать их обратно, это чисто односторонняя вещь.

Answer 1

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

Answer 2

Вместо использования Integer напишите класс, который наследуется от Integer, и переопределите функцию GetHashCode. Таким образом, вам не нужно ничего делать, кроме как создать эту функцию!

Самый простой способ равномерного распределения значений - это сделать что-то вроде:

public class MyInteger:Integer
{
    public override int GetHashCode()
    {
       unchecked
       {
           return (int)Math.Pow(this,this);
       }
    }
}

Красиво и равномерно разделено, при этом усилие сведено к минимуму.

Answer 3

Если вы знаете максимальное значение вашего набора ключей (kmax), вы можете увеличить его на постоянный множитель (множитель), скажем, умножить на фиксированное простое число, которое удерживает произведение ниже максимального целочисленного размера (2 ^ 31 - 1) :

т.е. ближайшее простое число к (2^30) / kmax

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

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