Сопоставление целых чисел во всем диапазоне

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

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

источник

2009-09-19 David Rutten

Прежде всего, настоящий убийца производительности не является проблемой при использовании словаря. Настоящий убийца - это когда вы закончите таблицу, в которой несколько объектов имеют один и тот же ключ, но это не вариант со словарем. Более того, это не значит, что ваши объекты разбросаны по любому произвольному набору ключей. набор, подобный 1,2,3,4, потенциально будет использовать меньше memmory, чем 1 1024 1089999 2^32-1 –

Чтобы улучшить производительность словаря в .NET, вам необходимо сбалансировать скорость и скорость хэширования. Чтобы иметь идеальный хеш без столкновения, он будет более трудоемким. Аналогично, самый быстрый алгоритм хэширования будет иметь больше коллизий. Нахождение баланса - это ключ, и в этом отношении команда BCL хорошо провела бы свою надежную работу, поэтому просто полагайтесь на нее, если у вас нет проблем с производительностью. – nawfal

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

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

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

Ницца и равномерно разделить, сохраняя при этом усилия к минимуму.

источник

2009-09-19 05:24:29 Erich

@ Erich, спасибо, но гарантируется ли это уникальное отображение каждого возможного целого числа? –

Это не так, но если предположить, что они достаточно сгруппированы, они будут. Кроме того, вам НЕОБХОДИМО использовать уникальное отображение, как работает хэш-таблица. Они будут достаточно распространены, чтобы ваша скорость была довольно быстрой. Помимо диапазона, вам может быть лучше использовать массив с индексом int. Каждое пустое место занимает всего 4 байта, поэтому оно не будет ужасно большим. Вы упомянули, что это самое большое значение - 10 000, так что это всего 40 000 байт или 40 тысяч для всего массива, у которого будет время поиска O (1) и времени вставки. Если вы готовы отказаться от k памяти, было бы лучше всего сделать это. – Erich

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

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

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

Примечание: убедитесь, что премьер-б не то же самое, как количество ковшей в таблице Hash.

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

источник

2009-09-19 05:17:23

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

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

источник

2009-09-19 06:03:51

Это хороший момент! –

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

@ Давид, справедливо. Здесь есть некоторые функции хеширования: http://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key –

Сопоставление целых чисел во всем диапазоне

ответ

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