Создать значение хэша в списке? - PullRequest
Новая
       27

Создать значение хэша в списке?

10 голосов
/ 02 сентября 2011

У меня есть List<MyRichObject> с 50 экземплярами в нем.Каждый из экземпляров имеет 1 или 2 уникальных свойства, но в некотором смысле все они уникальны, потому что в списке есть только одна позиция и т. Д.

Я бы хотел найти уникальный способ "хэш "этот список, поэтому он уникален среди всех других списков.Есть ли разумный способ сделать это в .NET 4?

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

Спасибо.

Ответы [ 2 ]

27 голосов
/ 10 июня 2015

TL; DR 

public static int GetSequenceHashCode<T>(this IList<T> sequence)
{
    const int seed = 487;
    const int modifier = 31;

    unchecked
    {
        return sequence.Aggregate(seed, (current, item) =>
            (current*modifier) + item.GetHashCode());
    }            
}

Зачем беспокоиться о другом ответе?

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

var a = new []{ "foo" };
var b = new []{ "foo", "bar" };
var c = new []{ "foo", "bar", "spam" };
var d = new []{ "seenoevil", "hearnoevil", "speaknoevil" };

Все они дают разные результаты, предполагая, что все они являются уникальными коллекциями. Большой! Теперь давайте попробуем с дубликатом: 

var e = new []{ "foo", "bar", "spam" };

GetSequenceHashCode должен давать одинаковый результат для c и e - и это так. Все идет нормально. Теперь давайте попробуем с элементами вне последовательности: 

var f = new []{ "spam", "bar", "foo" };

Э-э-э ... GetSequenceHashCode означает, что f равно как c, так и e, что не равно. Почему это происходит? Сначала разбейте его на фактические значения хеш-кода, используя в качестве примера c: 

int hashC = "foo".GetHashCode() ^ 
            "bar".GetHashCode() ^ 
            "spam".GetHashCode();

Поскольку точные числа здесь не очень важны, и для большей наглядности давайте представим, что хэш-коды трех строк - foo=8, bar=16 и spam=32. Итак: 

int hashC = 8 ^ 16 ^ 32;

или разбить его на двоичное представление: 

8 ^ 16 ^ 32 == 56;

//  8 = 00001000
//  ^
// 16 = 00010000
//  ^
// 32 = 00100000
//  =
// 56   00111000

Теперь вы должны увидеть, почему порядок реализации элементов в списке игнорируется этой реализацией, т.е. 8^16^32 = 16^8^32 = 32^16^8 и т. Д.

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

var a = new []{ "foo", "bar", "spam" };
var b = new []{ "foo", "bar", "spam", "foo" };
var c = new []{ "foo", "bar", "spam", "foo", "foo" };
var d = new []{ "foo", "bar", "spam", "foo", "foo", "spam", "foo", "spam", "foo" };

Хотя a и b генерируют различные хэши последовательностей, GetSequenceHashCode предполагает, что a, c и d одинаковы. Зачем?

Если вы XOR номер с самим собой, вы по существу отменяете его, т. Е. 

8 ^ 8 == 0;

//  8 = 00001000
//  ^
//  8 = 00001000
//  =
//  0 = 00000000

XOR с тем же номером снова дает вам исходный результат, то есть 

8 ^ 8 ^ 8 == 8;

//  8 = 00001000
//  ^
//  8 = 00001000
//  ^
//  8 = 00001000
//  =
//  8 = 00001000

Итак, если мы посмотрим на a и c снова, подставив упрощенные хеш-коды: 

var a = new []{ 8, 16, 32 };
var c = new []{ 8, 16, 32, 8, 8 };

хеш-коды рассчитываются как: 

int hashA = 8 ^ 16 ^ 32;         // = 56
int hashC = 8 ^ 16 ^ 32 ^ 8 ^ 8; // = 56
                       // ↑   ↑ 
                       // these two cancel each other out

и аналогично с d, где каждая пара foo и spam обнуляется.

2 голосов
/ 02 сентября 2011

Должен ли хеш быть представителем содержимого списка?Другими словами, вы будете использовать хеш для определения потенциального равенства?Если нет, то просто создайте новый Guid и используйте его.

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

Вот пример того, как я реализовал бы получение хэшакод для List<T>.Прежде всего, если вы собираетесь получить хеш-код для конкретного объекта, вам действительно следует убедиться, что этот объект не изменится.Если этот объект действительно изменяется, то ваш хэш-код больше не годится.

Лучший способ работать со списком, который можно «заморозить» (т.е. без добавления или удаления элементов после определенного момента), это вызватьAsReadOnly.Это даст вам ReadOnlyCollection<T>.Приведенная ниже реализация зависит от ReadOnlyCollection<T> просто для безопасности, так что имейте в виду: 

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;

class Example
{
    static void Main()
    {
        var seqOne = new List<int> { 1, 2, 3, 4, 5, 6 };
        var seqTwo = new List<int> { 6, 5, 4, 3, 2, 1 };

        var seqOneCode = seqOne.AsReadOnly().GetSequenceHashCode();
        var seqTwoCode = seqTwo.AsReadOnly().GetSequenceHashCode();

        Console.WriteLine(seqOneCode == seqTwoCode);
    }
}

static class Extensions
{
    public static int GetSequenceHashCode<T>(this ReadOnlyCollection<T> sequence)
    {
        return sequence
            .Select(item => item.GetHashCode())
            .Aggregate((total, nextCode) => total ^ nextCode);
    }
}

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

...