Ответ 1
Здесь существуют различные подходы к двум основным категориям, каждая из которых, как правило, имеет свои преимущества и недостатки с точки зрения эффективности и производительности. Вероятно, лучше выбрать самый простой алгоритм для любого приложения и использовать только более сложные варианты, если это необходимо для любой ситуации.
Обратите внимание, что в этих примерах используется EqualityComparer<T>.Default поскольку он будет чисто работать с нулевыми элементами. Вы можете сделать лучше, чем ноль для нуля, если хотите. Если T ограничен для структурирования, это также не нужно. При желании вы можете EqualityComparer<T>.Default поиск EqualityComparer<T>.Default из функции.
Коммутативные Операции
Если вы используете операции с хеш-кодами отдельных записей, которые являются коммутативными, то это приведет к одному и тому же конечному результату независимо от порядка.
Есть несколько очевидных вариантов чисел:
XOR
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 0;
foreach (T element in source)
{
hash = hash ^ EqualityComparer<T>.Default.GetHashCode(element);
}
return hash;
}
Недостатком этого является то, что хеш для {"x", "x"} такой же, как хеш для {"y", "y"}. Если это не проблема для вашей ситуации, возможно, это самое простое решение.
прибавление
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 0;
foreach (T element in source)
{
hash = unchecked (hash +
EqualityComparer<T>.Default.GetHashCode(element));
}
return hash;
}
Переполнение здесь хорошо, отсюда явный unchecked контекст.
Есть еще несколько неприятных случаев (например, {1, -1} и {2, -2}, но с большей вероятностью все будет хорошо, особенно со строками. В случае списков, которые могут содержать такие целые числа, вы всегда можете реализовать пользовательскую функцию хеширования (возможно, такую, которая принимает индекс повторения определенного значения в качестве параметра и, соответственно, возвращает уникальный хэш-код).
Вот пример такого алгоритма, который довольно эффективно справляется с вышеупомянутой проблемой. Он также имеет преимущество, заключающееся в значительном увеличении распространения сгенерированных хеш-кодов (см. Статью, приведенную в конце для некоторых пояснений). Математический/статистический анализ того, как именно этот алгоритм генерирует "лучшие" хеш-коды, был бы довольно продвинутым, но тестирование его в широком диапазоне входных значений и построение графиков результатов должно подтвердить это достаточно хорошо.
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 0;
int curHash;
int bitOffset = 0;
// Stores number of occurences so far of each value.
var valueCounts = new Dictionary<T, int>();
foreach (T element in source)
{
curHash = EqualityComparer<T>.Default.GetHashCode(element);
if (valueCounts.TryGetValue(element, out bitOffset))
valueCounts[element] = bitOffset + 1;
else
valueCounts.Add(element, bitOffset);
// The current hash code is shifted (with wrapping) one bit
// further left on each successive recurrence of a certain
// value to widen the distribution.
// 37 is an arbitrary low prime number that helps the
// algorithm to smooth out the distribution.
hash = unchecked(hash + ((curHash << bitOffset) |
(curHash >> (32 - bitOffset))) * 37);
}
return hash;
}
умножение
Который имеет мало преимуществ по сравнению с сложением: небольшие числа и сочетание положительных и отрицательных чисел могут привести к лучшему распределению хэш-битов. В качестве отрицательного значения для смещения эта "1" становится бесполезной записью, ничего не вносящей, и любой нулевой элемент приводит к нулю. Вы можете установить нулевой специальный случай, чтобы не вызывать этого серьезного недостатка.
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 17;
foreach (T element in source)
{
int h = EqualityComparer<T>.Default.GetHashCode(element);
if (h != 0)
hash = unchecked (hash * h);
}
return hash;
}
Заказ первым
Другой основной подход заключается в том, чтобы сначала навести порядок, а затем использовать любую функцию хеширования, которая вам нравится. Сам порядок не имеет значения, если он последовательный.
public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
int hash = 0;
foreach (T element in source.OrderBy(x => x, Comparer<T>.Default))
{
// f is any function/code you like returning int
hash = f(hash, element);
}
return hash;
}
Это имеет некоторые существенные преимущества в том, что операции объединения, возможные в f могут иметь значительно лучшие свойства хеширования (например, распределение битов), но это происходит при значительно более высокой стоимости. Сортировка O(n log n) а требуемая копия коллекции - это выделение памяти, которое вы не можете избежать, если хотите избежать изменения оригинала. Реализации GetHashCode должны обычно полностью избегать выделения. Одна из возможных реализаций f была бы аналогична приведенной в последнем примере в разделе "Добавление" (например, любое оставшееся число битовых сдвигов влево с последующим умножением на простое число - вы могли бы даже использовать последовательные простые числа на каждой итерации без дополнительных затрат, так как они должны быть сгенерированы только один раз).
Тем не менее, если вы имели дело со случаями, когда вы можете вычислить и кэшировать хэш и амортизировать стоимость многих вызовов GetHashCode такой подход может привести к превосходному поведению. Кроме того, последний подход является еще более гибким, поскольку он позволяет избежать необходимости использовать GetHashCode для элементов, если он знает их тип, и вместо этого использовать операции с байтами для них, чтобы обеспечить еще лучшее распределение хеша. Такой подход, вероятно, будет полезен только в тех случаях, когда производительность была определена как существенное узкое место.
Наконец, если вы хотите получить достаточно полный и довольно нематематический обзор предмета хэш-кодов и их эффективности в целом, эти посты в блоге были бы полезны для чтения, в частности пост "Реализация простого алгоритма хеширования (pt II)".