Используя набор целых чисел для генерации уникального ключа

Question

Теперь я некоторые наборы целых чисел, говорим:

set1 = {int1, int2, int3}; 
    set2 = {int2, int3, int1}; 
    set3 = {int1, int4, int2}; 

Порядка или цифры не принимаются во внимание, так set1 и set2 одинаковы, в то время как set3 не с двумя другими.

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

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

key = n1 + n2*2^16 + n3*2^32 

может быть возможным способом, но мне интересно, можно ли это решить более элегантно. Ключ может быть целым или строковым.

Значит, у кого-нибудь есть идея решить это как можно быстрее? Или любые материалы для чтения приветствуются.

Дополнительная информация: Цифры на самом деле цвета так каждое целое число меньше, чем 0xffffff

Answer 1

Если это были маленькие целые числа (все в пределах диапазона (0,63)), то вы могли бы представлять каждый набор как битовую строку (1 для любого целого числа это присутствует в наборе 0 для любого, что отсутствует). Для разреженных множеств больших целых чисел это было бы ужасно дорого с точки зрения хранения/памяти).

Другим методом, который приходит на ум, является сортировка набора и формирование ключа в виде конкатенации цифрового представления каждого номера (разделенного некоторым разделителем). Таким образом, множество {2,1,3} -> "1/2/3" (используя «/» в качестве разделителя) и {30,1,2,4} => "1/2/4/30"

Я полагаю, вы также можете использовать гибридный подход. Все элементы < 63 кодируются в шестнадцатеричную строку, а все остальные кодируются в строку, как описано. Тогда ваш окончательный результат будет сформирован: HEXxA/B/c ...(с «x», отделяющим маленькую строку int hex от больших int в наборе).

Answer 2

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

---

Надеется, что это поможет вашему решению, если нет лучшей идеи.

Answer 3

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

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

Я бы использовал функцию хэша, подобную описанной в Why chose 31 to do the multiplication in the hashcode() implementation ?, где вы сохраняете текущую сумму, умножая значение хэша на нечетное число, прежде чем добавить в него следующий элемент. Умножение на нечетное число mod 2^n по крайней мере не потеряет информацию немедленно. Я бы предложил 131, но у Java есть традиция использования 31.