Какой лучший алгоритм для переопределения GetHashCode?

В .NET GetHashCodeметод используется во многих местах в библиотеках базовых классов .NET. Для правильной его реализации особенно важно быстро находить элементы в коллекции или при определении равенства.

Существуют ли стандартные алгоритмы или рекомендации по реализации GetHashCodeпользовательских классов, чтобы я не снижал производительность?

4.11.2008 20:53:19
Прочитав этот вопрос и статью ниже, я смог реализовать переопределение GetHashCode. Я надеюсь, что это будет полезно для других. Руководство и правила для GetHashCode, написанные Эриком Липпертом
rene 22.03.2012 21:59:52
«или определить равенство»: нет! Два объекта с одинаковым хеш-кодом не обязательно равны.
Thomas Levesque 2.09.2015 22:03:36
@ThomasLevesque Вы правы, два объекта с одинаковым хеш-кодом не обязательно равны. Но все еще GetHashCode()используется в очень многих реализациях Equals(). Вот что я имел в виду под этим утверждением. GetHashCode()inside Equals()часто используется как ярлык для определения неравенства , потому что, если два объекта имеют различный хеш-код, они должны быть объектами, которые не равны, а остальная часть проверки на равенство не должна выполняться.
bitbonk 2.09.2015 22:27:43
@bitbonk Обычно обоим GetHashCode()и Equals()нужно смотреть на все поля обоих объектов (это должен делать Equals, если хеш-коды равны или не проверены). Из-за этого вызов GetHashCode()внутрь Equals()часто избыточен и может снизить производительность. Equals()может также быть в состоянии короткого замыкания, делая это намного быстрее - однако в некоторых случаях хеш-коды могут быть кэшированы, что делает GetHashCode()проверку быстрее и стоит. Смотрите этот вопрос для более.
NotEnoughData 2.04.2017 03:52:37
ОБНОВЛЕНИЕ ЯНВАРЬ 2020: блог Эрика Липперта, расположенный по адресу: docs.microsoft.com/en-us/archive/blogs/ericlippert/…
Rick Davin 15.01.2020 14:06:22
20 ОТВЕТОВ
РЕШЕНИЕ

Обычно я использую что-то вроде реализации, описанной в сказочной « Эффективной Java» Джоша Блоха . Это быстро и создает довольно хороший хеш, который вряд ли вызовет столкновения. Выберите два разных простых числа, например, 17 и 23, и выполните:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

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

Это лучше, чем обычная практика использования XORхэш-кодов по двум основным причинам. Предположим, у нас есть тип с двумя intполями:

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

Кстати, более ранний алгоритм в настоящее время используется компилятором C # для анонимных типов.

Эта страница дает довольно много вариантов. Я думаю, что в большинстве случаев вышесказанное «достаточно хорошо», и его невероятно легко запомнить и понять правильно. ФПНА альтернатива является аналогично простой, но использует различные константы и XORвместо того , чтобы в ADDкачестве операции комбинирования. Он выглядит примерно так, как показано ниже, но обычный алгоритм FNV работает с отдельными байтами, поэтому для этого потребуется модификация для выполнения одной итерации на байт вместо 32-битного хеш-значения. FNV также предназначен для переменных длин данных, тогда как мы используем его здесь всегда для одного и того же числа значений полей. Комментарии к этому ответу предполагают, что код здесь на самом деле не работает (в тестируемом примере), как подход к добавлению, описанный выше.

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ field1.GetHashCode();
        hash = (hash * 16777619) ^ field2.GetHashCode();
        hash = (hash * 16777619) ^ field3.GetHashCode();
        return hash;
    }
}

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

Согласно документации :

Вы можете переопределить GetHashCode для неизменяемых ссылочных типов. В общем, для изменяемых ссылочных типов вы должны переопределить GetHashCode, только если:

  • Вы можете вычислить хеш-код из полей, которые не являются изменяемыми; или
  • Вы можете гарантировать, что хеш-код изменяемого объекта не изменится, пока объект содержится в коллекции, которая опирается на свой хеш-код.
1589
22.01.2019 18:57:40
Алгоритм, описанный в упомянутой вами книге, на самом деле немного более детален, он, в частности, описывает, что делать с различными типами данных полей. Например: для полей типа long используйте (int) (field ^ f >>> 32) вместо простого вызова GetHashcode. Long.GetHashCodes реализован таким образом?
bitbonk 4.11.2008 21:44:52
Да, Int64.GetHashCode делает именно это. На Java это, конечно, потребует бокса. Это напоминает мне - пора добавить ссылку на книгу ...
Jon Skeet 4.11.2008 21:51:04
23 не является хорошим выбором, поскольку (начиная с .net 3.5 SP1) Dictionary<TKey,TValue>предполагается хорошее распределение по модулю определенных простых чисел. И 23 является одним из них. Так что если у вас есть словарь с Capacity 23, только последний вклад GetHashCodeвлияет на составной хеш-код. Поэтому я бы предпочел использовать 29 вместо 23.
CodesInChaos 21.11.2010 22:41:24
@CodeInChaos: только корзина влияет на последний вклад, так что в худшем случае, возможно, придется просмотреть все 23 записи в словаре. Он по-прежнему будет проверять фактический хэш-код каждой записи, что будет дешево. Если у вас есть такой маленький словарь, он вряд ли будет иметь большое значение.
Jon Skeet 21.11.2010 23:14:07
@Vajda: я обычно использую 0 в качестве эффективного хеш-кода для null- что не то же самое, что игнорирование поля.
Jon Skeet 22.01.2013 16:49:04

Большая часть моей работы выполняется с подключением к базе данных, что означает, что все мои классы имеют уникальный идентификатор из базы данных. Я всегда использую идентификатор из базы данных для генерации хэш-кода.

// Unique ID from database
private int _id;

...    
{
  return _id.GetHashCode();
}
3
5.11.2008 05:03:24
Это означает, что если у вас есть объекты Person и Account и они оба имеют и ID = 1, они будут иметь одинаковый хэш-код. И это не хорошо.
Petar Repac 22.03.2010 15:28:48
На самом деле комментарий выше неверен. Всегда будет возможность столкновения хеш-кода (хеш-код определяет только область, а не отдельный объект). Таким образом, такая реализация - для хеш-кода, содержащего смешанные объекты - приведет к большому количеству коллизий, что нежелательно, но было бы абсолютно нормально, если бы в ваших хеш-таблицах были только объекты одного типа. Кроме того, он не распределяется равномерно, однако базовая реализация также не распространяется на system.object, поэтому я бы не стал слишком сильно беспокоиться об этом ...
piers7 29.03.2010 02:14:20
Хеш-код может быть просто идентификатором, поскольку идентификатор является целым числом. Нет необходимости вызывать GetHashCode для целого числа (это функция тождества)
Darrel Lee 23.11.2012 19:18:54
@DarrelLee, но его _id может быть Guid. Это хорошая практика кодирования, так _id.GetHashCodeкак цель ясна.
nawfal 14.04.2013 12:57:06
@ 1224 в зависимости от модели использования это может быть ужасно по той причине, которую вы даете, но также может быть и великолепно; если у вас есть последовательность таких чисел без дырок, то у вас есть идеальный хеш, который лучше, чем любой алгоритм. Если вы знаете, что это так, вы можете даже рассчитывать на это и пропустить проверку на равенство.
Jon Hanna 14.01.2014 18:29:48

У меня есть класс Hashing в библиотеке Helper, который я использую для этой цели.

/// <summary> 
/// This is a simple hashing function from Robert Sedgwicks Hashing in C book.
/// Also, some simple optimizations to the algorithm in order to speed up
/// its hashing process have been added. from: www.partow.net
/// </summary>
/// <param name="input">array of objects, parameters combination that you need
/// to get a unique hash code for them</param>
/// <returns>Hash code</returns>
public static int RSHash(params object[] input)
{
    const int b = 378551;
    int a = 63689;
    int hash = 0;

    // If it overflows then just wrap around
    unchecked
    {
        for (int i = 0; i < input.Length; i++)
        {
            if (input[i] != null)
            {
                hash = hash * a + input[i].GetHashCode();
                a = a * b;
            }
        }
    }

    return hash;
}

Тогда просто вы можете использовать его как:

public override int GetHashCode()
{
    return Hashing.RSHash(_field1, _field2, _field3);
}

Я не оценивал его производительность, поэтому любые отзывы приветствуются.

64
22.06.2016 12:00:19
Ну, это вызовет бокс, если поля являются типами значений.
nightcoder 4.04.2010 15:39:24
"может быть улучшено позже путем перехвата OverflowException" Весь смысл в том unchecked, чтобы избежать исключений при переполнении, которое желательно при GetHashCode. Так что это не правильно, если значение переполняется, intи это совсем не больно.
Tim Schmelter 24.02.2014 13:06:41
Одна из проблем этого алгоритма заключается в том, что любой массив, полный нулей, всегда будет возвращать 0, независимо от его длины
Nathan Adams 17.04.2015 12:12:41
Этот вспомогательный метод также выделяет новый объект []
James Newton-King 20.07.2016 12:35:47
Как упоминает @NathanAdams, тот факт, что nullон пропущен полностью, может дать вам неожиданные результаты. Вместо того, чтобы пропускать их, вы должны просто использовать некоторое постоянное значение, а не input[i].GetHashCode()когда оно input[i]равно NULL.
David Schwartz 28.10.2016 19:04:03

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

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

И последний совет: не надейтесь, что GetHashCode () будет стабильным в течение нескольких запусков приложений . Многие типы .Net не гарантируют, что их хэш-коды останутся прежними после перезапуска, поэтому вы должны использовать только значение GetHashCode () для структур данных памяти.

29
23.02.2009 11:55:44
«В большинстве случаев, когда Equals () сравнивает несколько полей, на самом деле не имеет значения, хеширует ли GetHash () одно поле или несколько». Это опасный совет, потому что для объектов, которые различаются только в полях без хеширования, вы получите коллизии хеша. Если это происходит часто, производительность коллекций на основе хеша (HashMap, HashSet и т. Д.) Будет снижаться (в худшем случае до O (n)).
sleske 15.04.2010 15:44:29
На самом деле это произошло в Java: в ранних версиях JDK String.hashCode () рассматривал только начало строки; это приводит к проблемам с производительностью, если вы используете Strings в качестве ключей в HashMaps, которые отличаются только в конце (что обычно для URL). Поэтому алгоритм был изменен (в JDK 1.2 или 1.3 я считаю).
sleske 15.04.2010 15:51:57
Если это одно поле «обеспечивает хорошее распределение» (последняя часть моего ответа), тогда достаточно одного поля. Если оно не обеспечивает хорошего распределения , тогда (и только тогда) вам нужно другое вычисление. (Например , просто использовать другое поле , которое делает обеспечить распределение хорошо, или использовать несколько полей)
Bert Huijben 16.04.2010 09:12:51
Я не думаю, что есть проблема с GetHashCodeвыполнением выделения памяти, при условии, что это происходит только при первом использовании (с последующими вызовами просто возвращают кэшированный результат). Важно не то, что нужно избегать коллизий, а что нужно избегать «системных» коллизий. Если тип имеет два intполя oldXи newXчасто различаются по одному, хеш-значение oldX^newXбудет присваивать 90% таких хеш-значений записей 1, 2, 4 или 8. Использование oldX+newX[непроверенная арифметика] может вызвать больше коллизий ...
supercat 7.09.2013 21:02:32
... чем более сложная функция, но набор из 1 000 000 вещей, которые имеют 500 000 различных значений хеш-функции, будет очень хорош, если каждое хэш-значение имеет две связанные вещи, и очень плохо, если одно хеш-значение имеет 500 001 вещи, а другие имеют по одной.
supercat 7.09.2013 21:04:17

Вот мой помощник хеш-кода.
Преимущество состоит в том, что он использует аргументы универсального типа и поэтому не будет вызывать бокс:

public static class HashHelper
{
    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
         unchecked
         {
             return 31 * arg1.GetHashCode() + arg2.GetHashCode();
         }
    }

    public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            return 31 * hash + arg3.GetHashCode();
        }
    }

    public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, 
        T4 arg4)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            hash = 31 * hash + arg3.GetHashCode();
            return 31 * hash + arg4.GetHashCode();
        }
    }

    public static int GetHashCode<T>(T[] list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    public static int GetHashCode<T>(IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    /// <summary>
    /// Gets a hashcode for a collection for that the order of items 
    /// does not matter.
    /// So {1, 2, 3} and {3, 2, 1} will get same hash code.
    /// </summary>
    public static int GetHashCodeForOrderNoMatterCollection<T>(
        IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            int count = 0;
            foreach (var item in list)
            {
                hash += item.GetHashCode();
                count++;
            }
            return 31 * hash + count.GetHashCode();
        }
    }

    /// <summary>
    /// Alternative way to get a hashcode is to use a fluent 
    /// interface like this:<br />
    /// return 0.CombineHashCode(field1).CombineHashCode(field2).
    ///     CombineHashCode(field3);
    /// </summary>
    public static int CombineHashCode<T>(this int hashCode, T arg)
    {
        unchecked
        {
            return 31 * hashCode + arg.GetHashCode();   
        }
    }

Также он имеет метод расширения для обеспечения свободного интерфейса, так что вы можете использовать его следующим образом:

public override int GetHashCode()
{
    return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}

или вот так:

public override int GetHashCode()
{
    return 0.CombineHashCode(Manufacturer)
        .CombineHashCode(PartN)
        .CombineHashCode(Quantity);
}
105
25.03.2011 15:29:38
Не нужно T[]отдельно, как это ужеIEnumerable<T>
nawfal 14.04.2013 12:43:57
Вы можете реорганизовать эти методы и ограничить основную логику одной функцией
nawfal 14.04.2013 13:06:32
Кстати, 31 - это сдвиг и вычитание на процессоре, который является чрезвычайно быстрым.
Chui Tey 22.08.2013 23:14:42
@ nightcoder вы могли бы использовать params .
ANeves 9.02.2015 13:54:47
@ChuiTey Это то, что объединяет все простые числа Мерсенна .
Pharap 12.06.2015 03:11:00

Это хороший:

/// <summary>
/// Helper class for generating hash codes suitable 
/// for use in hashing algorithms and data structures like a hash table. 
/// </summary>
public static class HashCodeHelper
{
    private static int GetHashCodeInternal(int key1, int key2)
    {
        unchecked
        {
           var num = 0x7e53a269;
           num = (-1521134295 * num) + key1;
           num += (num << 10);
           num ^= (num >> 6);

           num = ((-1521134295 * num) + key2);
           num += (num << 10);
           num ^= (num >> 6);

           return num;
        }
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="arr">An array of objects used for generating the 
    /// hash code.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode(params object[] arr)
    {
        int hash = 0;
        foreach (var item in arr)
            hash = GetHashCodeInternal(hash, item.GetHashCode());
        return hash;
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <param name="obj4">The fourth object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and
    /// data structures like a hash table.
    /// </returns>
    public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
        T4 obj4)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
    {
        return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
    }
}

А вот как это использовать:

private struct Key
{
    private Type _type;
    private string _field;

    public Type Type { get { return _type; } }
    public string Field { get { return _field; } }

    public Key(Type type, string field)
    {
        _type = type;
        _field = field;
    }

    public override int GetHashCode()
    {
        return HashCodeHelper.GetHashCode(_field, _type);
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Key))
            return false;
        var tf = (Key)obj;
        return tf._field.Equals(_field) && tf._type.Equals(_type);
    }
}
13
2.12.2011 14:20:42
Как определяются ключи? GetHashCode () не принимает никаких параметров, поэтому необходимо вызвать его с двумя ключами, которые нужно как-то определить. Извините, без дальнейшего объяснения это выглядит только умно, но не так хорошо.
Michael Stum♦ 7.10.2010 17:28:19
И зачем вам общие перегрузки? Тип не важен (и не используется в вашем коде), поскольку у всех объектов есть GetHashCode()метод, поэтому вы всегда можете использовать метод с paramsпараметром массива. Или я что-то здесь упускаю?
gehho 8.10.2010 09:31:53
Когда вы будете использовать объект вместо шаблонов, вы получите бокс и распределение памяти, что вам не нужно в GetHashCode. Так что дженерики - это путь.
CodesInChaos 21.11.2010 22:26:26
h += (h << 10); h ^= (h >> 6); h += (h << 3); h ^= (h >> 11); h += (h << 15);Конечные шаги shift / xor ( имеют кодовую запятую: они не зависят ни от каких входных данных и выглядят ужасно избыточными для меня.
sehe 22.04.2011 19:54:08
@ Магнус, да, верно, я удалю свой оригинальный комментарий. Просто небольшое замечание, что это может быть не так быстро, как некоторые другие решения, но, как вы говорите, не должно иметь значения. Распределение отличное, лучше, чем большинство решений здесь, так что +1 от меня! :)
nawfal 25.12.2012 11:28:38

Анонимный тип

Microsoft уже предоставляет хороший универсальный генератор HashCode: просто скопируйте значения вашего свойства / поля в анонимный тип и хешируйте его:

new { PropA, PropB, PropC, PropD }.GetHashCode();

Это будет работать для любого количества свойств. Он не использует бокс. Он просто использует алгоритм, уже реализованный в рамках для анонимных типов.

ValueTuple - обновление для C # 7

Как упоминает @cactuaroid в комментариях, можно использовать кортеж значения. Это экономит несколько нажатий клавиш и, что более важно, выполняется исключительно в стеке (без мусора):

(PropA, PropB, PropC, PropD).GetHashCode();

(Примечание: оригинальная техника, использующая анонимные типы, по-видимому, создает объект в куче, т.е. мусор, поскольку анонимные типы реализованы как классы, хотя это может быть оптимизировано компилятором. Было бы интересно сравнить эти параметры, но Вариант кортежа должен быть лучше.)

424
16.08.2018 14:13:51
Да, анонимная GetHashCodeреализация очень эффективна (кстати, она такая же, как в ответе Джона Скита), но единственная проблема с этим решением состоит в том, что вы генерируете новый экземпляр при любом GetHashCodeвызове. В частности, в случае интенсивного доступа к большим хэшированным коллекциям это может быть немного
digEmAll 8.01.2011 09:50:49
@digEmAll Хорошо, я не думал о накладных расходах на создание нового объекта. Ответ Джона Скита является наиболее эффективным и не будет использовать бокс. (@Kumba Чтобы решить непроверенную в VB, просто используйте Int64 (long) и обрежьте его после вычислений.)
Rick Love 2.04.2011 17:30:54
могли бы просто сказать , new { PropA, PropB, PropC, PropD }.GetHashCode()тоже
sehe 22.04.2011 19:51:59
VB.NET должен использовать ключ при создании анонимного типа: в New With {Key PropA}.GetHashCode()противном случае GetHashCode не будет возвращать один и тот же хеш-код для разных объектов с одинаковыми «идентифицирующими» свойствами.
David Osborne 20.08.2014 15:58:52
@ В этом случае я бы посоветовал сохранить IEnumerable в виде значения списка, а не перечислять его каждый раз, когда вычисляется хэш-код. Сжатие ToList каждый раз внутри GetHashCode может снизить производительность во многих ситуациях.
Rick Love 20.10.2015 20:40:53

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

Используется так:

public override int GetHashCode()
{
    HashBuilder b = new HashBuilder();
    b.AddItems(this.member1, this.member2, this.member3);
    return b.Result;
} 

А вот класс острых строителей:

internal class HashBuilder
{
    private const int Prime1 = 17;
    private const int Prime2 = 23;
    private int result = Prime1;

    public HashBuilder()
    {
    }

    public HashBuilder(int startHash)
    {
        this.result = startHash;
    }

    public int Result
    {
        get
        {
            return this.result;
        }
    }

    public void AddItem<T>(T item)
    {
        unchecked
        {
            this.result = this.result * Prime2 + item.GetHashCode();
        }
    }

    public void AddItems<T1, T2>(T1 item1, T2 item2)
    {
        this.AddItem(item1);
        this.AddItem(item2);
    }

    public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
    }

    public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3, 
        T4 item4)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
    }

    public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3, 
        T4 item4, T5 item5)
    {
        this.AddItem(item1);
        this.AddItem(item2);
        this.AddItem(item3);
        this.AddItem(item4);
        this.AddItem(item5);
    }        

    public void AddItems<T>(params T[] items)
    {
        foreach (T item in items)
        {
            this.AddItem(item);
        }
    }
}
8
15.04.2013 06:18:32
вы можете избежать создания объекта внутри функции gethashcode, как в ответе Мангуса. Просто вызовите эти чертовы статические хэш-функции (кого волнует начальный хеш). Кроме того, вы можете использовать AddItems<T>(params T[] items)метод чаще в классе помощника (чем вызов AddItem(T)каждый раз).
nawfal 14.04.2013 12:52:27
И какую пользу вы получаете, this.result * Prime2 * item.GetHashCode()когда часто используете this.result * Prime2 + item.GetHashCode()?
nawfal 14.04.2013 12:54:32
Я не могу использовать AddItems<T>(params T[] items)чаще, потому что typeof(T1) != typeof(T2)и т. Д.
bitbonk 15.04.2013 06:25:24
о да, я пропустил это.
nawfal 15.04.2013 06:54:16

Microsoft ведет несколько способов хеширования ...

//for classes that contain a single int value
return this.value;

//for classes that contain multiple int value
return x ^ y;

//for classes that contain single number bigger than int    
return ((int)value ^ (int)(value >> 32)); 

//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();

//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode(); 

Я могу догадаться, что для нескольких больших int вы можете использовать это:

int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;

И то же самое для мультитипа : все преобразованные сначала в intиспользование, а GetHashCode()затем значения int будут xor'ed, и результатом будет ваш хеш.

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

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

1
6.04.2018 11:48:24
Ксоринг целых чисел для создания хеш-кода является хорошо известным антипаттерном, который имеет тенденцию приводить к особенно большому количеству коллизий с реальными значениями.
Jon Hanna 14.01.2014 09:36:05
Каждый из них использует целое число, и никогда не было никакой гарантии, что хеш-код будет одинаковым, он просто пытался измениться настолько, насколько мало коллизий.
deadManN 16.09.2015 05:59:14
Да, но ваш второй и пятый не пытаются избежать столкновений.
Jon Hanna 16.09.2015 08:44:13
Да, этот антипаттерн довольно распространен.
Jon Hanna 19.09.2015 14:06:33
Там есть баланс, чтобы достичь. Используйте действительно хороший хеш-код, такой как Spookyhash, и вы получите намного лучшее предотвращение столкновений, но у него будет намного больше времени для вычислений, чем у любого из них (но когда дело доходит до хеширования очень больших объемов данных, Spookyhash очень быстр). Простой переход на одно из значений перед ксорингом - это лишь незначительные дополнительные затраты для хорошего уменьшения коллизий. Умножение простых чисел снова увеличивает время и качество. То, что лучше между сменой или мультом, поэтому является спорным. Обычный xor, хотя очень часто имеет много коллизий на реальных данных и его лучше избегать
Jon Hanna 20.09.2015 16:57:27

Вот мой вспомогательный класс, использующий реализацию Джона Скита .

public static class HashCode
{
    public const int Start = 17;

    public static int Hash<T>(this int hash, T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked((hash * 31) + h);
    }
}

Использование:

public override int GetHashCode()
{
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)
        .Hash(_field3);
}

Если вы хотите избежать написания метода расширения для System.Int32:

public readonly struct HashCode
{
    private readonly int _value;

    public HashCode(int value) => _value = value;

    public static HashCode Start { get; } = new HashCode(17);

    public static implicit operator int(HashCode hash) => hash._value;

    public HashCode Hash<T>(T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked(new HashCode((_value * 31) + h));
    }

    public override int GetHashCode() => _value;
}

Он по-прежнему избегает выделения кучи и используется точно так же:

public override int GetHashCode()
{
    // This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
    // And the result is implicitly converted to `Int32`.
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)     
        .Hash(_field3);
}

Редактировать (май 2018 г.): EqualityComparer<T>.Defaultтеперь метод get является внутренним свойством JIT - запрос на извлечение упомянут Стивеном Тубом в этом сообщении в блоге .

57
14.02.2020 23:43:03
Я бы поменял строку с третичным оператором так:var h = Equals(obj, default(T)) ? 0 : obj.GetHashCode();
Bill Barry 5.09.2014 17:12:59
Я считаю, что троичный оператор with obj != nullскомпилирует boxинструкцию, которая выделит память, если Tэто тип значения. Вместо этого вы можете использовать, obj.Equals(null)который будет компилироваться для виртуального вызова Equalsметода.
Martin Liversage 13.09.2014 23:00:02
Потому что this.hashCode != h. Это не вернуло бы то же значение.
Şafak Gür 15.06.2015 08:01:08
Извините, мне удалось удалить мой комментарий, а не редактировать его. Разве выгоднее создать новую структуру, затем изменить hashCode на non-readonly и сделать: "unchecked {this.hashCode ^ = h * 397;} вернуть this;" например?
Erik Karlsson 15.06.2015 08:28:13
Неизменность имеет свои преимущества ( Почему изменчивые структуры являются злом? ). Что касается производительности, то, что я делаю, довольно дешево, так как оно не выделяет места в куче.
Şafak Gür 15.06.2015 10:35:50

До недавнего времени мой ответ был бы очень близок к ответу Джона Скита. Однако недавно я запустил проект, в котором использовались хеш-таблицы степени двойки, то есть хеш-таблицы, где размер внутренней таблицы равен 8, 16, 32 и т. Д. Есть веская причина для предпочтения размеров простых чисел, но есть Есть некоторые преимущества для степени двух размеров.

И это в значительной степени отстой. Поэтому после небольшого количества экспериментов и исследований я начал перефразировать свои хэши следующим образом:

public static int ReHash(int source)
{
  unchecked
  {
    ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
    ulong d = 0xE2ADBEEFDEADBEEF ^ c;
    ulong a = d += c = c << 15 | c >> -15;
    ulong b = a += d = d << 52 | d >> -52;
    c ^= b += a = a << 26 | a >> -26;
    d ^= c += b = b << 51 | b >> -51;
    a ^= d += c = c << 28 | c >> -28;
    b ^= a += d = d << 9 | d >> -9;
    c ^= b += a = a << 47 | a >> -47;
    d ^= c += b << 54 | b >> -54;
    a ^= d += c << 32 | c >> 32;
    a += d << 25 | d >> -25;
    return (int)(a >> 1);
  }
}

А потом мой хэш-стол с степенью двойки больше не сосал.

Это беспокоило меня, потому что выше не должно работать. Или, точнее, он не должен работать, если оригинал не GetHashCode()был очень плохим.

Повторное смешивание хеш-кода не может улучшить отличный хеш-код, потому что единственный возможный эффект - это введение нескольких коллизий.

Повторное смешивание хеш-кода не может улучшить ужасный хеш-код, потому что единственный возможный эффект - это изменение, например, большого количества коллизий со значением 53 на большое число со значением 18,3487,291.

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

Редактировать: я также использовал открытую адресацию, что также увеличило бы чувствительность к столкновениям, возможно, даже больше, чем факт, что это была степень двойки.

И, конечно же, меня беспокоило, насколько можно улучшить string.GetHashCode()реализацию в .NET (или изучать здесь ) (порядка тестов, выполняющихся примерно в 20-30 раз быстрее из-за меньшего количества коллизий), и больше беспокоило, насколько сильно мои собственные хеш-коды может быть улучшено (гораздо больше).

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

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

В конце концов я остановился на портировании SpookyHash на .NET. Действительно, приведенный выше код является версией быстрого использования SpookyHash для получения 32-битного вывода из 32-битного ввода.

Теперь SpookyHash - это не просто быстрый фрагмент кода для запоминания. Мой порт этого еще меньше, потому что я вручную его ввел для лучшей скорости *. Но для этого и нужно повторное использование кода.

Затем я отложил этот проект в сторону, потому что так же, как исходный проект породил вопрос о том, как создать лучший хеш-код, так и этот проект поставил вопрос о том, как создать лучшую .NET memcpy.

Затем я вернулся и произвел много перегрузок, чтобы легко передать почти все нативные типы (кроме decimal†) в хэш-код.

Это быстро, за что Боб Дженкинс заслуживает большей части уважения, потому что его оригинальный код, с которого я портировал, еще быстрее, особенно на 64-битных машинах, алгоритм которых оптимизирован для ‡.

Полный код можно увидеть по адресу https://bitbucket.org/JonHanna/spookilysharp/src, но учтите, что приведенный выше код является его упрощенной версией.

Однако, поскольку он уже написан, его можно использовать проще:

public override int GetHashCode()
{
  var hash = new SpookyHash();
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

Он также принимает начальные значения, поэтому, если вам нужно иметь дело с ненадежным вводом и хотите защитить от атак Hash DoS, вы можете установить начальное время на основе времени безотказной работы или аналогичного, а также сделать результаты непредсказуемыми для злоумышленников:

private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
  //produce different hashes ever time this application is restarted
  //but remain consistent in each run, so attackers have a harder time
  //DoSing the hash tables.
  var hash = new SpookyHash(hashSeed0, hashSeed1);
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

* Большой сюрприз в этом заключается в том, что метод вращения вручную, который возвращает (x << n) | (x >> -n)улучшенные вещи. Я был бы уверен, что дрожание указало бы на это для меня, но профилирование показало обратное.

decimalне является родным с точки зрения .NET, хотя это с C #. Проблема с этим состоит в том, что его собственная GetHashCode()трактует точность как значимую, а собственная Equals()- нет. Оба являются допустимыми, но не смешанными. При реализации своей собственной версии вам нужно выбрать одну или другую, но я не могу знать, что вы хотите.

‡ Для сравнения. При использовании в строке SpookyHash на 64 битах значительно быстрее, чем string.GetHashCode()на 32 битах, что немного быстрее, чем string.GetHashCode()на 64 битах, что значительно быстрее, чем SpookyHash на 32 битах, хотя все еще достаточно быстро, чтобы быть разумным выбором.

23
4.04.2018 21:11:03
При объединении нескольких хеш-значений в одно, я склонен использовать longзначения для промежуточных результатов, а затем уменьшать конечный результат до значения int. Это кажется хорошей идеей? Меня беспокоит то, что кто-то использует, например, hash = (hash * 31) + nextField, тогда пары совпадающих значений будут влиять только на верхние 27 бит хеша. Разрешение вычисления распространяется на a longи оборачивая вещи, минимизирует эту опасность.
supercat 24.04.2014 21:31:31
@supercat, это зависит от того, как вы распределились. Библиотека SpookilySharp обеспечит хорошее распределение, в идеале (поскольку она не требует создания объекта), передав указатель на тип blittable или передав один из перечислимых элементов, которые он обрабатывает напрямую, но если у вас еще нет blittable данные или подходящее перечисление, тогда вызов .Update()с несколькими значениями согласно ответу выше сделает свое дело.
Jon Hanna 24.04.2014 22:48:41
@JonHanna Хотели бы вы быть более точным с проблемным поведением, с которым вы столкнулись? Я пытаюсь реализовать библиотеку, которая делает реализацию объектов-значений тривиальной ( ValueUtils ), и мне бы хотелось, чтобы набор тестов демонстрировал плохую смешиваемость хэшей в хеш-таблицах с степенью двойки.
Eamon Nerbonne 1.06.2014 14:19:24
@EamonNerbonne У меня нет ничего более точного, чем «общее время было медленнее». Как я добавил в редактировании, тот факт, что я использовал открытую адресацию, мог быть важнее, чем фактор степени двух. Я планирую провести несколько тестовых случаев для конкретного проекта, где я буду сравнивать несколько разных подходов, поэтому после этого у меня может быть лучший ответ, хотя это не является приоритетным (личный проект без острой необходимости). так что я доберусь до него, когда доберусь до него ...)
Jon Hanna 2.06.2014 14:01:09
@JonHanna: да, я знаю, как проходит персональный график проекта - удачи! В любом случае, я вижу, что не очень хорошо сформулировал этот последний комментарий: я хотел спросить о проблемной информации, а не обязательно о деталях возникших проблем. Я хотел бы использовать это в качестве тестового набора (или вдохновения для тестового набора). В любом случае - удачи вашему любимому проекту :-).
Eamon Nerbonne 2.06.2014 15:23:39

Вот еще одна свободная реализация алгоритма, опубликованная выше Джоном Скитом , но которая не включает в себя операции выделения или упаковки:

public static class Hash
{
    public const int Base = 17;

    public static int HashObject(this int hash, object obj)
    {
        unchecked { return hash * 23 + (obj == null ? 0 : obj.GetHashCode()); }
    }

    public static int HashValue<T>(this int hash, T value)
        where T : struct
    {
        unchecked { return hash * 23 + value.GetHashCode(); }
    }
}

Использование:

public class MyType<T>
{
    public string Name { get; set; }

    public string Description { get; set; }

    public int Value { get; set; }

    public IEnumerable<T> Children { get; set; }

    public override int GetHashCode()
    {
        return Hash.Base
            .HashObject(this.Name)
            .HashObject(this.Description)
            .HashValue(this.Value)
            .HashObject(this.Children);
    }
}

Компилятор гарантирует, что HashValueон не вызывается с классом из-за ограничения общего типа. Но компилятор не поддерживается, HashObjectпоскольку добавление универсального аргумента также добавляет операцию упаковки.

10
23.05.2017 10:31:37

Я столкнулся с проблемой с плавающей запятой и десятичной дробью, используя реализацию, выбранную в качестве ответа выше.

Этот тест не пройден (с плавающей запятой; хэш-код такой же, хотя я переключил 2 значения на отрицательные):

        var obj1 = new { A = 100m, B = 100m, C = 100m, D = 100m};
        var obj2 = new { A = 100m, B = 100m, C = -100m, D = -100m};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

Но этот тест проходит (с целыми числами):

        var obj1 = new { A = 100m, B = 100m, C = 100, D = 100};
        var obj2 = new { A = 100m, B = 100m, C = -100, D = -100};
        var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
        var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
        Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different   hash1:{0}  hash2:{1}",hash1,hash2));

Я изменил свою реализацию, чтобы не использовать GetHashCode для примитивных типов, и кажется, что она работает лучше

    private static int InternalComputeHash(params object[] obj)
    {
        unchecked
        {
            var result = (int)SEED_VALUE_PRIME;
            for (uint i = 0; i < obj.Length; i++)
            {
                var currval = result;
                var nextval = DetermineNextValue(obj[i]);
                result = (result * MULTIPLIER_VALUE_PRIME) + nextval;

            }
            return result;
        }
    }



    private static int DetermineNextValue(object value)
    {
        unchecked
        {

                int hashCode;
                if (value is short
                    || value is int
                    || value is byte
                    || value is sbyte
                    || value is uint
                    || value is ushort
                    || value is ulong
                    || value is long
                    || value is float
                    || value is double
                    || value is decimal)
                {
                    return Convert.ToInt32(value);
                }
                else
                {
                    return value != null ? value.GetHashCode() : 0;
                }
        }
    }
1
28.09.2014 16:44:25
В случае , если иное намерение uncheckedНЕ влияет на Convert.ToInt32: uint, long, float, doubleи decimalвсе это может Переполнение здесь.
Mark Hurd 30.09.2014 04:28:04

Очень похоже на решение ночного кодера, за исключением того, что проще поднимать простые числа, если хотите.

PS: Это один из тех случаев, когда вы немного рвете, зная, что это может быть преобразовано в один метод с 9 значениями по умолчанию, но это будет медленнее, поэтому вы просто закрываете глаза и пытаетесь забыть об этом.

/// <summary>
/// Try not to look at the source code. It works. Just rely on it.
/// </summary>
public static class HashHelper
{
    private const int PrimeOne = 17;
    private const int PrimeTwo = 23;

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9, T10 arg10)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();
            hash = hash * PrimeTwo + arg9.GetHashCode();
            hash = hash * PrimeTwo + arg10.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();
            hash = hash * PrimeTwo + arg9.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();
            hash = hash * PrimeTwo + arg8.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();
            hash = hash * PrimeTwo + arg7.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5, T6>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();
            hash = hash * PrimeTwo + arg6.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4, T5>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();
            hash = hash * PrimeTwo + arg5.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, T4 arg4)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();
            hash = hash * PrimeTwo + arg4.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();
            hash = hash * PrimeTwo + arg3.GetHashCode();

            return hash;
        }
    }

    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
        unchecked
        {
            int hash = PrimeOne;
            hash = hash * PrimeTwo + arg1.GetHashCode();
            hash = hash * PrimeTwo + arg2.GetHashCode();

            return hash;
        }
    }
}
3
21.10.2014 17:49:34
Не обрабатывает нули.
JJS 27.12.2016 17:09:28

Пользователи ReSharper могут генерировать GetHashCode, Equals и другие с помощью ReSharper -> Edit -> Generate Code -> Equality Members.

// ReSharper's GetHashCode looks like this
public override int GetHashCode() {
    unchecked {
        int hashCode = Id;
        hashCode = (hashCode * 397) ^ IntMember;
        hashCode = (hashCode * 397) ^ OtherIntMember;
        hashCode = (hashCode * 397) ^ (RefMember != null ? RefMember.GetHashCode() : 0);
        // ...
        return hashCode;
    }
}
5
5.04.2018 14:19:15

Начиная с https://github.com/dotnet/coreclr/pull/14863 , существует новый способ генерации хеш-кодов, который очень прост! Просто пиши

public override int GetHashCode()
    => HashCode.Combine(field1, field2, field3);

Это сгенерирует качественный хеш-код, не беспокоясь о деталях реализации.

10
23.11.2017 15:06:05
Это похоже на приятное дополнение ... любой способ узнать, какая версия .NET Core будет поставляться?
Dan J 14.12.2017 00:37:50
@DanJ Какое счастливое совпадение, HashCodeизменения для corefx были объединены всего за пару часов до вашего комментария :) Тип планируется отправить в .NET Core 2.1.
James Ko 14.12.2017 00:41:08
Это потрясающе - и вполне подходящее время. Upvoted. :)
Dan J 14.12.2017 00:48:03
@DanJ Еще лучшая новость - она ​​должна быть доступна прямо сейчас на ночных сборках CoreFX, размещенных на корне dotnet-core MyGet.
James Ko 15.12.2017 23:44:28
Сладкое - это не помогает мне в работе, так как мы не совсем , что кровотечение края, но хорошо знать. Ура!
Dan J 17.12.2017 22:18:18

Если у нас есть не более 8 свойств (надеюсь), здесь есть другая альтернатива.

ValueTupleявляется структурой и, кажется, имеет твердую GetHashCodeреализацию.

Это означает, что мы могли бы просто сделать это:

// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();

Давайте посмотрим на текущую реализацию .NET Core для ValueTuples GetHashCode.

Это из ValueTuple:

    internal static int CombineHashCodes(int h1, int h2)
    {
        return HashHelpers.Combine(HashHelpers.Combine(HashHelpers.RandomSeed, h1), h2);
    }

    internal static int CombineHashCodes(int h1, int h2, int h3)
    {
        return HashHelpers.Combine(CombineHashCodes(h1, h2), h3);
    }

И это из HashHelper:

    public static readonly int RandomSeed = Guid.NewGuid().GetHashCode();

    public static int Combine(int h1, int h2)
    {
        unchecked
        {
            // RyuJIT optimizes this to use the ROL instruction
            // Related GitHub pull request: dotnet/coreclr#1830
            uint rol5 = ((uint)h1 << 5) | ((uint)h1 >> 27);
            return ((int)rol5 + h1) ^ h2;
        }
    }

По-английски:

  • Поворот влево (круговое смещение) h1 на 5 позиций.
  • Добавьте результат и h1 вместе.
  • XOR результат с h2.
  • Начните с выполнения вышеуказанной операции с {static random seed, h1}.
  • Для каждого следующего элемента выполните операцию с предыдущим результатом и следующим элементом (например, h2).

Было бы неплохо узнать больше о свойствах этого алгоритма хеширования ROL-5.

К сожалению, откладывать на ValueTupleсебя, GetHashCodeвозможно, не так быстро, как хотелось бы и ожидать. Этот комментарий в связанном обсуждении показывает, что прямой вызов HashHelpers.Combineболее производительный. С другой стороны, это внутреннее, поэтому нам пришлось бы копировать код, жертвуя большей частью того, что мы получили здесь. Кроме того, мы будем ответственны за то, что сначала запомнили Combineслучайное семя. Я не знаю, каковы будут последствия, если мы пропустим этот шаг.

4
15.05.2018 12:00:46
Предполагая, h1 >> 27что 0 игнорирует это, h1 << 5равно, h1 * 32следовательно, это то же самое, что и h1 * 33 ^ h2. Согласно этой странице , он называется «Модифицированный Бернштейн».
cactuaroid 17.08.2018 14:28:16

Это статический вспомогательный класс, который реализует реализацию Джоша Блоха; и обеспечивает явные перегрузки для «предотвращения» бокса, а также для реализации хеша специально для длинных примитивов.

Вы можете передать сравнение строк, соответствующее вашей реализации equals.

Поскольку выход Hash всегда является int, вы можете просто связывать вызовы Hash.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.CompilerServices;


namespace Sc.Util.System
{
    /// <summary>
    /// Static methods that allow easy implementation of hashCode. Example usage:
    /// <code>
    /// public override int GetHashCode()
    ///     => HashCodeHelper.Seed
    ///         .Hash(primitiveField)
    ///         .Hsh(objectField)
    ///         .Hash(iEnumerableField);
    /// </code>
    /// </summary>
    public static class HashCodeHelper
    {
        /// <summary>
        /// An initial value for a hashCode, to which is added contributions from fields.
        /// Using a non-zero value decreases collisions of hashCode values.
        /// </summary>
        public const int Seed = 23;

        private const int oddPrimeNumber = 37;


        /// <summary>
        /// Rotates the seed against a prime number.
        /// </summary>
        /// <param name="aSeed">The hash's first term.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int rotateFirstTerm(int aSeed)
        {
            unchecked {
                return HashCodeHelper.oddPrimeNumber * aSeed;
            }
        }


        /// <summary>
        /// Contributes a boolean to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aBoolean">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, bool aBoolean)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + (aBoolean
                                ? 1
                                : 0);
            }
        }

        /// <summary>
        /// Contributes a char to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aChar">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, char aChar)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + aChar;
            }
        }

        /// <summary>
        /// Contributes an int to the developing HashCode seed.
        /// Note that byte and short are handled by this method, through implicit conversion.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aInt">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, int aInt)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + aInt;
            }
        }

        /// <summary>
        /// Contributes a long to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aLong">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, long aLong)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + (int)(aLong ^ (aLong >> 32));
            }
        }

        /// <summary>
        /// Contributes a float to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aFloat">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, float aFloat)
        {
            unchecked {
                return HashCodeHelper.rotateFirstTerm(aSeed)
                        + Convert.ToInt32(aFloat);
            }
        }

        /// <summary>
        /// Contributes a double to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aDouble">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, double aDouble)
            => aSeed.Hash(Convert.ToInt64(aDouble));

        /// <summary>
        /// Contributes a string to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aString">The value to contribute.</param>
        /// <param name="stringComparison">Optional comparison that creates the hash.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(
                this int aSeed,
                string aString,
                StringComparison stringComparison = StringComparison.Ordinal)
        {
            if (aString == null)
                return aSeed.Hash(0);
            switch (stringComparison) {
                case StringComparison.CurrentCulture :
                    return StringComparer.CurrentCulture.GetHashCode(aString);
                case StringComparison.CurrentCultureIgnoreCase :
                    return StringComparer.CurrentCultureIgnoreCase.GetHashCode(aString);
                case StringComparison.InvariantCulture :
                    return StringComparer.InvariantCulture.GetHashCode(aString);
                case StringComparison.InvariantCultureIgnoreCase :
                    return StringComparer.InvariantCultureIgnoreCase.GetHashCode(aString);
                case StringComparison.OrdinalIgnoreCase :
                    return StringComparer.OrdinalIgnoreCase.GetHashCode(aString);
                default :
                    return StringComparer.Ordinal.GetHashCode(aString);
            }
        }

        /// <summary>
        /// Contributes a possibly-null array to the developing HashCode seed.
        /// Each element may be a primitive, a reference, or a possibly-null array.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aArray">CAN be null.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, IEnumerable aArray)
        {
            if (aArray == null)
                return aSeed.Hash(0);
            int countPlusOne = 1; // So it differs from null
            foreach (object item in aArray) {
                ++countPlusOne;
                if (item is IEnumerable arrayItem) {
                    if (!object.ReferenceEquals(aArray, arrayItem))
                        aSeed = aSeed.Hash(arrayItem); // recursive call!
                } else
                    aSeed = aSeed.Hash(item);
            }
            return aSeed.Hash(countPlusOne);
        }

        /// <summary>
        /// Contributes a possibly-null array to the developing HashCode seed.
        /// You must provide the hash function for each element.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aArray">CAN be null.</param>
        /// <param name="hashElement">Required: yields the hash for each element
        /// in <paramref name="aArray"/>.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash<T>(this int aSeed, IEnumerable<T> aArray, Func<T, int> hashElement)
        {
            if (aArray == null)
                return aSeed.Hash(0);
            int countPlusOne = 1; // So it differs from null
            foreach (T item in aArray) {
                ++countPlusOne;
                aSeed = aSeed.Hash(hashElement(item));
            }
            return aSeed.Hash(countPlusOne);
        }

        /// <summary>
        /// Contributes a possibly-null object to the developing HashCode seed.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="aObject">CAN be null.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Hash(this int aSeed, object aObject)
        {
            switch (aObject) {
                case null :
                    return aSeed.Hash(0);
                case bool b :
                    return aSeed.Hash(b);
                case char c :
                    return aSeed.Hash(c);
                case int i :
                    return aSeed.Hash(i);
                case long l :
                    return aSeed.Hash(l);
                case float f :
                    return aSeed.Hash(f);
                case double d :
                    return aSeed.Hash(d);
                case string s :
                    return aSeed.Hash(s);
                case IEnumerable iEnumerable :
                    return aSeed.Hash(iEnumerable);
            }
            return aSeed.Hash(aObject.GetHashCode());
        }


        /// <summary>
        /// This utility method uses reflection to iterate all specified properties that are readable
        /// on the given object, excluding any property names given in the params arguments, and
        /// generates a hashcode.
        /// </summary>
        /// <param name="aSeed">The developing hash code, or the seed: if you have no seed, use
        /// the <see cref="Seed"/>.</param>
        /// <param name="aObject">CAN be null.</param>
        /// <param name="propertySelector"><see cref="BindingFlags"/> to select the properties to hash.</param>
        /// <param name="ignorePropertyNames">Optional.</param>
        /// <returns>A hash from the properties contributed to <c>aSeed</c>.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashAllProperties(
                this int aSeed,
                object aObject,
                BindingFlags propertySelector
                        = BindingFlags.Instance
                        | BindingFlags.Public
                        | BindingFlags.GetProperty,
                params string[] ignorePropertyNames)
        {
            if (aObject == null)
                return aSeed.Hash(0);
            if ((ignorePropertyNames != null)
                    && (ignorePropertyNames.Length != 0)) {
                foreach (PropertyInfo propertyInfo in aObject.GetType()
                        .GetProperties(propertySelector)) {
                    if (!propertyInfo.CanRead
                            || (Array.IndexOf(ignorePropertyNames, propertyInfo.Name) >= 0))
                        continue;
                    aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
                }
            } else {
                foreach (PropertyInfo propertyInfo in aObject.GetType()
                        .GetProperties(propertySelector)) {
                    if (propertyInfo.CanRead)
                        aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
                }
            }
            return aSeed;
        }


        /// <summary>
        /// NOTICE: this method is provided to contribute a <see cref="KeyValuePair{TKey,TValue}"/> to
        /// the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
        /// this method has a different name since it will not be automatically invoked by
        /// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
        /// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
        /// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
        /// the generated hash code will not be consistent. This method itself ALSO will not invoke
        /// this method on the Key or Value here if that itself is a KeyValuePair.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="keyValuePair">The value to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashKeyAndValue<TKey, TValue>(this int aSeed, KeyValuePair<TKey, TValue> keyValuePair)
            => aSeed.Hash(keyValuePair.Key)
                    .Hash(keyValuePair.Value);

        /// <summary>
        /// NOTICE: this method is provided to contribute a collection of <see cref="KeyValuePair{TKey,TValue}"/>
        /// to the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
        /// this method has a different name since it will not be automatically invoked by
        /// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
        /// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
        /// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
        /// the generated hash code will not be consistent. This method itself ALSO will not invoke
        /// this method on a Key or Value here if that itself is a KeyValuePair or an Enumerable of
        /// KeyValuePair.
        /// </summary>
        /// <param name="aSeed">The developing HashCode value or seed.</param>
        /// <param name="keyValuePairs">The values to contribute.</param>
        /// <returns>The new hash code.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int HashKeysAndValues<TKey, TValue>(
                this int aSeed,
                IEnumerable<KeyValuePair<TKey, TValue>> keyValuePairs)
        {
            if (keyValuePairs == null)
                return aSeed.Hash(null);
            foreach (KeyValuePair<TKey, TValue> keyValuePair in keyValuePairs) {
                aSeed = aSeed.HashKeyAndValue(keyValuePair);
            }
            return aSeed;
        }
    }
}
1
9.05.2019 00:16:59
Дайпс: я нашел ошибку! HashKeysAndValuesМетод был зафиксирован: он вызывает HashKeyAndValue.
Steven Coco 9.05.2019 00:14:50

.NET Standard 2.1 и выше

Если вы используете .NET Standard 2.1 или выше, вы можете использовать структуру System.HashCode . Есть два способа его использования:

HashCode.Combine

CombineМетод может быть использован для создания хэш - код, данные до восьми объектов.

public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);

HashCode.Add

AddМетод поможет вам справиться с коллекциями:

public override int GetHashCode()
{
    var hashCode = new HashCode();
    hashCode.Add(this.object1);
    foreach (var item in this.collection)
    {
        hashCode.Add(item);
    }
    return hashCode.ToHashCode();
}

GetHashCode Made Easy

Вы можете прочитать полный пост в блоге « GetHashCode Made Easy » для более подробной информации и комментариев.

Пример использования

public class SuperHero
{
    public int Age { get; set; }
    public string Name { get; set; }
    public List<string> Powers { get; set; }

    public override int GetHashCode() =>
        HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers);
}

Реализация

public struct HashCode : IEquatable<HashCode>
{
    private const int EmptyCollectionPrimeNumber = 19;
    private readonly int value;

    private HashCode(int value) => this.value = value;

    public static implicit operator int(HashCode hashCode) => hashCode.value;

    public static bool operator ==(HashCode left, HashCode right) => left.Equals(right);

    public static bool operator !=(HashCode left, HashCode right) => !(left == right);

    public static HashCode Of<T>(T item) => new HashCode(GetHashCode(item));

    public static HashCode OfEach<T>(IEnumerable<T> items) =>
        items == null ? new HashCode(0) : new HashCode(GetHashCode(items, 0));

    public HashCode And<T>(T item) => 
        new HashCode(CombineHashCodes(this.value, GetHashCode(item)));

    public HashCode AndEach<T>(IEnumerable<T> items)
    {
        if (items == null)
        {
            return new HashCode(this.value);
        }

        return new HashCode(GetHashCode(items, this.value));
    }

    public bool Equals(HashCode other) => this.value.Equals(other.value);

    public override bool Equals(object obj)
    {
        if (obj is HashCode)
        {
            return this.Equals((HashCode)obj);
        }

        return false;
    }

    public override int GetHashCode() => this.value.GetHashCode();

    private static int CombineHashCodes(int h1, int h2)
    {
        unchecked
        {
            // Code copied from System.Tuple a good way to combine hashes.
            return ((h1 << 5) + h1) ^ h2;
        }
    }

    private static int GetHashCode<T>(T item) => item?.GetHashCode() ?? 0;

    private static int GetHashCode<T>(IEnumerable<T> items, int startHashCode)
    {
        var temp = startHashCode;

        var enumerator = items.GetEnumerator();
        if (enumerator.MoveNext())
        {
            temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));

            while (enumerator.MoveNext())
            {
                temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
            }
        }
        else
        {
            temp = CombineHashCodes(temp, EmptyCollectionPrimeNumber);
        }

        return temp;
    }
}

Что делает хороший алгоритм?

скорость

Алгоритм, который вычисляет хеш-код, должен быть быстрым. Простой алгоритм обычно будет быстрее.

детерминистический

Алгоритм хеширования должен быть детерминированным, т. Е. При одинаковых входных данных он всегда должен давать одинаковые выходные данные.

Уменьшить коллизии

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

Хорошая хеш-функция должна отображать ожидаемые входные данные как можно более равномерно по всему выходному диапазону. Это должно иметь единообразие.

Предотвратить DoS

В .NET Core каждый раз при перезапуске приложения вы получаете разные хеш-коды. Это функция безопасности для предотвращения атак типа «отказ в обслуживании» (DoS). Для .NET Framework вы должны включить эту функцию, добавив следующий файл App.config:

<?xml version ="1.0"?>  
<configuration>  
   <runtime>  
      <UseRandomizedStringHashAlgorithm enabled="1" />  
   </runtime>  
</configuration>

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

Подробнее об этом читайте здесь .

Криптографически безопасно?

Алгоритм не должен быть криптографической хеш-функцией . Это означает, что он не должен удовлетворять следующим условиям:

  • Невозможно сгенерировать сообщение, которое выдает заданное хеш-значение
  • Невозможно найти два разных сообщения с одинаковым хеш-значением
  • Небольшое изменение в сообщении должно настолько сильно изменить значение хеш-функции, что новое значение хеш-функции кажется некоррелированным со старым значением хеш-функции (лавинный эффект).
28
16.01.2020 09:25:32

Если вы хотите, чтобы polyfill HashCodeотnetstandard2.1

public static class HashCode
{
    public static int Combine(params object[] instances)
    {
        int hash = 17;

        foreach (var i in instances)
        {
            hash = unchecked((hash * 31) + (i?.GetHashCode() ?? 0));
        }

        return hash;
    }
}

Примечание: если используется с struct, он будет выделять память из-за бокса

0
20.04.2020 04:54:54