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

.net algorithm

24952 просмотра

6 ответа

10689 Репутация автора

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

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

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

Автор: JDunkerley Источник Размещён: 21.05.2009 12:06

Ответы (6)


5 плюса

51780 Репутация автора

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

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

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

Автор: Welbog Размещён: 21.05.2009 12:09

14 плюса

118925 Репутация автора

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

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 делает это.

Автор: Noldorin Размещён: 21.05.2009 12:11

84 плюса

1143421 Репутация автора

Решение

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

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

Автор: Jon Skeet Размещён: 21.05.2009 12:12

11 плюса

307830 Репутация автора

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

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

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

Автор: angry person Размещён: 21.05.2009 12:12

0 плюса

47330 Репутация автора

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

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

Автор: nawfal Размещён: 15.12.2012 08:31

5 плюса

19254 Репутация автора

@JonSkeet предоставляет справедливый алгоритм общего назначения для вычисления хеш-кода из n хеш-кодов, но предполагает, что вы уже знаете, какие элементы объекта должны быть хеш-значениями, знаете, что делать с нулевыми элементами, и пропускаете реализацию для 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

В C #

Func<IEnumerable<Object>, int> computeHashCode = items =>
    items
    .Select(item => item == null ? 0 : item.GetHashCode())
    .Aggregate(23, (hash, itemHash) => hash * 31 + itemHash);
Автор: Stephen Swensen Размещён: 20.05.2013 02:06
Вопросы из категории :
32x32