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

Question

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

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

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

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

710 6

.net algorithm

6 ответов:

Comments

Ничего не найдено.

Jon Skeet · Accepted Answer · 2009-05-21 15:12:30

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

Noldorin · Accepted Answer · 2009-05-21 15:11:50

вот возможный подход, который учитывает порядок. (Второй метод определяется как метод расширения.)
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 делает это.

Lasse Vågsæther Karlsen · Accepted Answer · 2009-05-21 15:12:55

один стандартный способ заключается в следующем:
hashcode = 23
hashcode = (hashcode * 37) + v1
hashcode = (hashcode * 37) + v2
23 и 37 являются coprime, но вы можете использовать и другие номера, а также.

Welbog · Accepted Answer · 2009-05-21 15:09:54

Как насчет этого:
(a.GetHashcode() + b).GetHashcode()
дает вам другой код для (a,b) и (b, a) плюс это не совсем то, что фантазии.

Stephen Swensen · Accepted Answer · 2013-05-20 17:06:32

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

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

нулевые члены должны хэшироваться как константа, например 0

алгоритм@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
В C#
Func<IEnumerable<Object>, int> computeHashCode = items =>
    items
    .Select(item => item == null ? 0 : item.GetHashCode())
    .Aggregate(23, (hash, itemHash) => hash * 31 + itemHash);

nawfal · Accepted Answer · 2017-05-23 14:47:09

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

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