Равномерное распределение длинных целочисленных идентификаторов в сегменты

Question

У меня есть огромный набор длинных целочисленных идентификаторов, которые должны быть распределены по (n) блокам как можно более равномерно. Длинные целочисленные идентификаторы могут иметь карманы отсутствующих идентификаторов. С учетом того, что это критерий, есть ли разница между использованием длинного целого как есть и выполнением по модулю (n) [длинное целое число] или лучше создать hashCode для строковой версии длинного целого (чтобы улучшить распределение) а затем сделать по модулю (n) [хэш-код строки (длинное целое)]? Требуется ли дополнительное преобразование строк для получения равномерного разброса по хеш-коду?

Так как я получил отзыв, что мой вопрос не имеет достаточного количества справочной информации. Я добавляю еще немного информации.

Идентификаторы в основном представляют собой автоматически увеличивающиеся числовые идентификаторы строк, которые автоматически генерируются в базе данных, представляющей идентификатор элемента. Причиной появления пропущенных идентификаторов является удаление.

Сами идентификаторы являются длинными целыми числами. Сами идентификаторы (элементы) имеют порядок (10 с-100)+ миллион в некоторых случаях и порядка тысяч в некоторых случаях.

Только в том случае, когда идентификаторы имеют порядок миллионов, я действительно хочу распределить их в сегменты (число идентификаторов >> количество сегментов) для хранения в системе без SQL (разделы).

Мне было интересно, если из-за того, что элементы удаляются, я должен прибегнуть к (Long).toString(). HashCode(), чтобы получить равномерный спред вместо непосредственного использования длинного числа. У меня было ощущение, что выполнение toString.hashCode не принесет мне много пользы, и мне также не понравился тот факт, что java hashCode не гарантирует одно и то же значение для всех версий java (хотя для String их реализация hashCode кажется документированной и стабильной за прошедшие релизы по годам)

Answer 1

Там нет необходимости привлекать String,

new Integer(i).hashCode()

... дает вам хэш - разработанный для самой цели равномерного распределения в ведра.

new Integer(i).hashCode() % n

... даст вам номер в диапазоне, который вы хотите.

---

тем не мение Integer.hashCode() просто:

 return value;

Так new Integer(i).hashCode() % n эквивалентно i % n,

Answer 2

На ваш вопрос не может быть ответа. Попытка @slim - лучшее, что вы получите, потому что в вашем вопросе отсутствует важная информация.

• Чтобы распространять набор предметов, вы должны знать кое-что об их первоначальном распространении.

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

• Если диапазон входных данных не значительно превышает количество сегментов, необходимо убедиться, что диапазон входных данных точно кратен количеству сегментов, в противном случае последние сегменты не получат столько элементов. Например, с диапазоном [0-999] и 400 сегментами первые 200 сегментов получают элементы [0-199], [400-599] и [800-999], в то время как остальные 200 сегментов получают значения [200-399] и [600-799].

  То есть половина ваших корзин заканчивается на 50% больше предметов, чем другая половина.

• Если они распределены неравномерно, так как оператор по модулю не меняет распределение, за исключением случаев его обтекания, распределение на выходе также не является равномерным.

  Это когда вам нужна хеш-функция.

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

Чтобы быть справедливым, есть некоторые хеш-функции, которые довольно хорошо работают в большинстве наборов данных, например, мультипликативный метод Кнута (при условии, что входные данные не слишком большие). Вы могли бы, скажем, вычислить

hash(input) = input * 2654435761 % 2^32

Хорошо разбивает кластеры ценностей. Тем не менее, это не в делимости. То есть, если большинство ваших входов делится на 2, выходы тоже будут. [кредит на этот ответ]

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