Создать хеш-код из двух чисел

Question

Я пытаюсь создать функцию быстрого хеширования для класса комплексных чисел (a + b) в C #.

Я неоднократно видел метод a.GetHashcode()^b.GetHashCode(). Но это даст одинаковый хэш-код для (a,b) и (b,a).

Есть ли какой-нибудь стандартный алгоритм для этого и есть ли какие-то функции в .Net framework, чтобы помочь?

Answer 1

Мой обычный способ создания хеш-кода для произвольного набора хешируемых элементов:

int hash = 23;
hash = hash * 31 + item1Hash;
hash = hash * 31 + item2Hash;
hash = hash * 31 + item3Hash;
hash = hash * 31 + item4Hash;
hash = hash * 31 + item5Hash;
// etc

В вашем случае item1Hash может быть просто a, а item2Hash может быть просто b.

Значения 23 и 31 относительно не важны, если они простые (или, по крайней мере, взаимно простые).

Очевидно, что все еще будут столкновения, но вы не столкнетесь с обычными неприятными проблемами:

hash(a, a) == hash(b, b)
hash(a, b) == hash(b, a)

Если вы знаете больше о том, какими могут быть реальные значения a и b, вы, вероятно, сможете добиться большего, но это хорошая начальная реализация, которую легко запомнить и реализовать. Обратите внимание, что если есть вероятность, что вы соберете сборку с пометкой «проверка на арифметическое переполнение / недополнение», вы должны поместить все это в блок без контроля. (Переполнение подходит для этого алгоритма.)

Answer 2

Вот возможный подход, который учитывает порядок. (Второй метод определяется как метод расширения.)

public int GetHashCode()
{
    return a.GetHashcode() ^ b.GetHashcode().RotateLeft(16);
}

public static uint RotateLeft(this uint value, int count)
{
    return (value << count) | (value >> (32 - count))
}

Было бы, конечно, интересно посмотреть, как класс * .NET 4.0 * делает это.

Answer 3

Один стандартный способ это:

hashcode = 23
hashcode = (hashcode * 37) + v1
hashcode = (hashcode * 37) + v2

23 и 37 взаимно просты, но вы можете использовать и другие числа.

Answer 4

@ JonSkeet предоставляет справедливый алгоритм общего назначения для вычисления хеш-кода из n хеш-кодов, но предполагает, что вы уже знаете, какие элементы объекта должны быть хеш-значениями, знаете, что делать с нулевыми элементами, и пропускаете реализацию для п произвольных предметов. Итак, расширим его ответ:

1. Только открытые, неизменяемые свойства и поля должны вносить вклад в хеш-код объекта. Они должны быть общедоступными (или изоморфными общедоступным), поскольку мы должны иметь возможность рассчитывать на два объекта с одинаковой видимой поверхностью, имеющих одинаковый хэш-код (намекающий на связь между равенством объектов и равенством хеш-кода), и они должны быть неизменными, поскольку хеш-код объекта никогда не должен изменяться в течение времени его жизни (с тех пор вы можете получить объект в неправильном слоте хеш-таблицы!).
2. нулевые члены должны хешироваться как константа, например 0
3. @ Алгоритм JonSkeet является примером из учебника для применения функции высшего порядка функционального программирования, обычно называемой fold (Aggregate в C # LINQ), где 23 - наше начальное число, а <hash accumulator> * 31 + <current item hash> - наша функция сворачивания. :

В F #

let computeHashCode items =
    items
    |> Seq.map (fun item -> if item = null then 0 else item.GetHashCode())
    |> Seq.fold (fun hash itemHash -> hash * 31 + itemHash) 23

In C #

Func<IEnumerable<Object>, int> computeHashCode = items =>
    items
    .Select(item => item == null ? 0 : item.GetHashCode())
    .Aggregate(23, (hash, itemHash) => hash * 31 + itemHash);

Answer 5

Что по этому поводу:

(a.GetHashcode() + b).GetHashcode()

Дает вам другой код для (a, b) и (b, a), плюс это не так уж и красиво.

Answer 6

Все зависит от того, чего вы пытаетесь достичь. Если хеши предназначены для таких хеш-структур, как Dictionary, то вы должны сбалансировать частоту столкновений и скорость хеширования . Чтобы получить идеальный хеш без коллизий, потребуется больше времени. Точно так же самый быстрый алгоритм хеширования будет иметь относительно больше коллизий. Найти идеальный баланс - вот ключ. Также вы должны принять во внимание насколько большим может быть ваш эффективный хеш, и если хеширование должно быть обратимым ! Подход Нолдорина дает вам идеальный хэш (не читайте коллизии), если ваши действительные и мнимые части вашего комплексного числа всегда положительны. Это подойдет даже для отрицательных чисел, если вы в порядке с редкими столкновениями. Но я обеспокоен диапазоном значений, которые он может дать, довольно большой на мой вкус.

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