Функция hashа в списке, независимая от порядка элементов в нем

Я хочу иметь словарь, который присваивает значение целому числу.

Например, key [1 2 3] и value будет иметь определенное значение.

Дело в том, что [3 2 1] нужно обрабатывать одинаково в моем случае, так что hash должен быть равным, если я пойду с hash-подход.

Набор будет содержать от 2 до 10 элементов.

Сумма элементов обычно фиксируется, поэтому мы не можем сделать hashcode в соответствии с суммой, которая здесь является первой естественной идеей.

Не домашняя задача, на самом деле сталкивающаяся с этой проблемой в моем коде.

Этот набор в основном IEnumerable в C #, поэтому любая структура данных подходит для их хранения.

Любая помощь оценивается. Производительность здесь очень важна.

Немедленная мысль: мы могли бы подытожить items^2 и уже получить какой-то лучший хеш, но все же я хотел бы услышать некоторые мысли.

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

В принципе, все подходы здесь – это экземпляры одного и того же шаблона. Map x 1 , …, x n to f (x 1 ) op … op f (x n ), где op – коммутативная ассоциативная операция на некотором множестве X, а f – это отображение из элементов в X. Этот шаблон был использован пару раз таким образом, что это доказуемо хорошо.

  • Выберем случайное большое простое число p и случайный вычет b из [1, p – 1]. Пусть f (x) = b x mod p, а op – дополнение. По существу, мы интерпретируем множество как многочлен и используем лемму Шварца-Зиппеля, чтобы связать вероятность столкновения (= вероятность того, что ненулевой многочлен имеет b в качестве корня mod p).

  • Пусть op – XOR и пусть f – случайная таблица. Это зобристское хеширование и минимизирует в ожидании количество столкновений прямыми линейно-алгебраическими аргументами.

Модульное возведение в степень медленное, поэтому не используйте его. Что касается hashирования Zobrist, с 3 миллионами элементов, таблица f, вероятно, не будет вписываться в L2, хотя она устанавливает верхнюю границу одного доступа к основной памяти.

Вместо этого я бы взял хеширование Zobrist в качестве точки отправления и искал бы дешевую функцию f, которая ведет себя как случайная функция. Это, по сути, описание работы некриптографического псевдослучайного генератора – я бы попробовал вычислять f, высевая быструю PRG с x и генерируя одно значение.

EDIT: если все множества имеют одинаковые суммы, не выбирайте f для полинома степени 1 (например, ступенчатой ​​функции линейного конгруэнтного генератора).

Используйте HashSet и HashSet.CreateSetComparer() , который возвращает IEqualityComparer> .

Я думаю, что то, что упоминается в этой статье, определенно поможет:

http://people.csail.mit.edu/devadas/pubs/mhashes.pdf

Инкрементные мультисети hash-функции и их применение к проверке целостности памяти

Аннотация: Мы вводим новый криптографический инструмент: мультисети hash-функции. В отличие от стандартных хеш-функций, которые принимают строки в качестве входных данных, мультимножество хеш-функций работает на мультимножествах (или наборах). Они отображают мультимножества произвольного конечного размера на строки (hashи) фиксированной длины. Они инкрементальны в том, что когда новые члены добавляются в мультимножество, hash может обновляться со временем, пропорциональным изменению. Эти функции могут быть устойчивыми к многостанционным столкновениям, так как для них существует два мультимножества, которые производят один и тот же hash или просто устойчивые к столкновению, так как он является идеальным для множества и мультимножества, которые создают один и тот же хеш.

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

Одна возможность: сортировка элементов в списке, а затем hash.

Вы можете отсортировать числа и выбрать образец из заданных индексов и оставить остаток как ноль, если текущее значение имеет меньшее количество чисел. Или вы могли бы их или что угодно.

Почему не что-то вроде

 public int GetOrderIndependantHashCode(IEnumerable source) { return (source.Select(x => x*x).Sum() + source.Select(x => x*x*x).Sum() + source.Select(x => x*x*x*x).Sum()) & 0x7FFFFF; } 

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

Используя пример в вопросе:

 [1, 2, 3] maps to 2 x 3 x 5 = 30 [3, 2, 1] maps to 5 x 3 x 2 = 30 

Создайте свой собственный тип, который реализует IEnumerable .

Переопределить GetHashCode . В нем ToArray().GetHashCode() свою коллекцию, вызывайте и возвращайте ToArray().GetHashCode() .