Хеш-функция в списке не зависит от порядка элементов в нем

В основном все подходы здесь являются экземплярами одного и того же шаблона. Сопоставьте x₁, …, x_n с f(x₁) op … op f(x_n) , где op — коммутативно-ассоциативная операция над некоторым множеством X, а f — отображение элементов в X. Этот шаблон использовался пару раз и доказуемо хорош.

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

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

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

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

РЕДАКТИРОВАТЬ: учитывая, что все наборы имеют одинаковые суммы, не выбирайте f как полином степени 1 (например, ступенчатую функцию линейного конгруэнтного генератора).

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

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

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

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

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

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

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

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

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

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

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

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

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

Создайте свой собственный тип, реализующий IEnumerable<T>.

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