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

Ответ 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, вероятно, вы, вероятно, сможете сделать лучше, но это хорошая начальная реализация, которую легко запомнить и реализовать. Обратите внимание, что если есть вероятность, что вы построите сборку с отметкой "Проверить арифметическое переполнение/недополнение", вы должны поместить все это в неконтролируемый блок. (Переполнение отлично подходит для этого алгоритма.)

Ответ 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))
}

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

Ответ 3

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

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

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

Ответ 4

Как насчет этого:

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

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

Ответ 5

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

• Только общедоступные, неизменяемые свойства и поля должны вносить вклад в хэш-код объектов. Они должны быть общедоступными (или изоморфными публике), так как мы должны иметь возможность рассчитывать на два объекта с одинаковой видимой поверхностью, имеющей один и тот же хэш-код (намекая на отношение между равенством объектов и равенством хеш-кода), и они должны быть неизменными, поскольку хеш-код объекта никогда не должен меняться в течение его жизненного цикла (так как тогда вы можете оказаться в объекте в неправильном слоте хеш-таблицы!).
• null члены должны хэш как константа, например 0
• @JonSkeet-алгоритм представляет собой пример текстовой книги для применения функции более высокого порядка функционального программирования, обычно называемой fold (Aggregate в С# 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

В С#

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

Ответ 6

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

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