Существуют различные подходы в рамках двух основных категорий, каждая из которых, как правило, имеет свои преимущества и недостатки с точки зрения эффективности и производительности. Вероятно, лучше выбрать самый простой алгоритм для любого приложения и использовать только более сложные варианты, если это необходимо для любой ситуации.
Обратите внимание, что в этих примерах используется EqualityComparer<T>.Default, поскольку он будет работать с нулевыми элементами чисто. Вы можете сделать лучше, чем ноль для нуля, если хотите. Если T ограничен для структурирования, это также не нужно. При желании вы можете вывести функцию 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) post.