Usando o campo de um objeto como uma chave de Dicionário genérica

120

Se eu quiser usar objetos como chaves para a Dictionary, quais métodos precisarei substituir para fazê-los comparar de uma maneira específica?

Digamos que eu tenho uma classe que possui propriedades:

class Foo {
    public string Name { get; set; }
    public int FooID { get; set; }

    // elided
} 

E eu quero criar um:

Dictionary<Foo, List<Stuff>>

Quero que Fooobjetos com o mesmo FooIDsejam considerados o mesmo grupo. Quais métodos precisarei substituir na Fooclasse?

Para resumir: eu quero categorizar Stuffobjetos em listas, agrupadas por Fooobjetos. Stuffos objetos terão um FooIDpara vinculá-los à sua categoria.

Dana
fonte

Respostas:

151

Por padrão, os dois métodos importantes são GetHashCode()e Equals(). É importante que, se duas coisas forem iguais ( Equals()retorna verdadeiro), elas tenham o mesmo código hash. Por exemplo, você pode "retornar o FooID;" como GetHashCode()se você quiser isso como a correspondência. Você também pode implementar IEquatable<Foo>, mas isso é opcional:

class Foo : IEquatable<Foo> {
    public string Name { get; set;}
    public int FooID {get; set;}

    public override int GetHashCode() {
        return FooID;
    }
    public override bool Equals(object obj) {
        return Equals(obj as Foo);
    }
    public bool Equals(Foo obj) {
        return obj != null && obj.FooID == this.FooID;
    }
}

Finalmente, outra alternativa é fornecer um IEqualityComparer<T>para fazer o mesmo.

Marc Gravell
fonte
5
+1 e não pretendo seqüestrar esse segmento, mas fiquei com a impressão de que GetHashCode () deve retornar FooId.GetHashCode (). Esse não é o padrão certo?
11119 Ken Browning
8
@ Ken - bem, ele só precisa retornar um int que forneça os recursos necessários. Qual FooID fará tão bem quanto FooID.GetHashCode (). Como um detalhe de implementação, Int32.GetHashCode () é "return this;". Para outros tipos (string etc), sim: .GetHashCode () seria muito útil.
Marc Gravell
2
Obrigado! Fui com o IEqualityComparer <T>, pois era apenas para o Dicarionário que eu precisava dos métodos substituídos.
Dana
1
Você deve estar ciente de que o desempenho de contêineres com base em tabelas de hash (Dictionary <T>, Dictionary, HashTable etc.) depende da qualidade da função de hash usada. Se você simplesmente FooID como o código de hash, os contêineres podem ter um desempenho muito ruim.
Jørgen Fogh
2
@ JørgenFogh Estou muito ciente disso; o exemplo apresentado é consistente com a intenção declarada. Há muitas preocupações relacionadas à imutabilidade de hash; os IDs mudam com menos frequência do que os nomes e geralmente são confiáveis ​​e únicos indicadores de equivalência. Um assunto não trivial, no entanto.
Marc Gravell
33

Como você deseja FooIDque seja o identificador do grupo, use-o como chave no dicionário, em vez do objeto Foo:

Dictionary<int, List<Stuff>>

Se você usasse o Fooobjeto como chave, implementaria apenas o método GetHashCodee Equalspara considerar apenas a FooIDpropriedade A Namepropriedade teria um peso morto no que Dictionarydizia respeito, então você usaria apenas Foocomo um invólucro para um int.

Portanto, é melhor usar o FooIDvalor diretamente e, assim, você não precisa implementar nada, Dictionaryjá que ele já suporta o uso de uma intchave.

Editar:
se você quiser usar a Fooclasse como chave de qualquer maneira, IEqualityComparer<Foo>é fácil implementar:

public class FooEqualityComparer : IEqualityComparer<Foo> {
   public int GetHashCode(Foo foo) { return foo.FooID.GetHashCode(); }
   public bool Equals(Foo foo1, Foo foo2) { return foo1.FooID == foo2.FooID; }
}

Uso:

Dictionary<Foo, List<Stuff>> dict = new Dictionary<Foo, List<Stuff>>(new FooEqualityComparer());
Guffa
fonte
1
Mais corretamente, o int já suporta os métodos / interfaces necessários para que ele seja usado como uma chave. O dicionário não tem conhecimento direto de int ou de qualquer outro tipo.
22619 Jim Mischel
Pensei nisso, mas por uma variedade de razões, era mais limpo e conveniente usar os objetos como as teclas do dicionário.
Dana
1
Bem, apenas parece que você está usando o objeto como chave, como realmente está usando apenas o ID como chave.
Guffa
8

Para Foo, você precisará substituir object.GetHashCode () e object.Equals ()

O dicionário chamará GetHashCode () para calcular um intervalo de hash para cada valor e Equals para comparar se dois Foo's são idênticos.

Calcule bons códigos de hash (evite que objetos Foo iguais tenham o mesmo código de hash), mas certifique-se de que dois Foos iguais tenham o mesmo código de hash. Você pode começar com o método Equals e, em seguida, (em GetHashCode ()) ou o código de hash de cada membro que você comparar em iguais.

public class Foo { 
     public string A;
     public string B;

     override bool Equals(object other) {
          var otherFoo = other as Foo;
          if (otherFoo == null)
             return false;
          return A==otherFoo.A && B ==otherFoo.B;
     }

     override int GetHashCode() {
          return 17 * A.GetHashCode() + B.GetHashCode();
     }
}
froh42
fonte
2
Além disso - mas xor (^) faz um péssimo combinador para códigos de hash, pois muitas vezes leva a muitas colisões diagonais (por exemplo, {"foo", "bar"} vs {"bar", "foo"}. a opção é multiplicar e adicionar cada termo - ou seja, 17 * a.GetHashCode () + B.GetHashCode ();
Marc Gravell
2
Marc, entendo o que você quer dizer. Mas como você chega ao número mágico 17? É vantajoso usar um número primo como multiplicador para combinar hashes? Se sim, por quê?
Froh42 11/03/09
Posso sugerir o retorno: (A + B) .GetHashCode () em vez de: 17 * A.GetHashCode () + B.GetHashCode () Isso irá: 1) Ter menos probabilidade de ter uma colisão e 2) garantir que não haja estouro de número inteiro.
Charles Burns
(A + B) .GetHashCode () cria um algoritmo de hash muito ruim, pois conjuntos diferentes de (A, B) podem resultar no mesmo hash se forem concatenados na mesma string; "hellow" + "ned" é o mesmo que "hell" + "possuído" e resultaria no mesmo hash.
kaesve
@kaesve, que tal (A + "" + B) .GetHashCode ()?
Timeless
1

E a Hashtableaula!

Hashtable oMyDic = new Hashtable();
Object oAnyKeyObject = null;
Object oAnyValueObject = null;
oMyDic.Add(oAnyKeyObject, oAnyValueObject);
foreach (DictionaryEntry de in oMyDic)
{
   // Do your job
}

Da maneira acima, você pode usar qualquer objeto (seu objeto de classe) como uma chave genérica do Dicionário :)

Behzad Ebrahimi
fonte
1

Eu tive o mesmo problema. Agora posso usar qualquer objeto que tentei como chave devido à substituição de Equals e GetHashCode.

Aqui está uma classe que eu criei com métodos para usar dentro das substituições de Equals (object obj) e GetHashCode (). Decidi usar genéricos e um algoritmo de hash que deveria cobrir a maioria dos objetos. Informe-me se vir algo aqui que não funcione para alguns tipos de objeto e se você tem uma maneira de aprimorá-lo.

public class Equality<T>
{
    public int GetHashCode(T classInstance)
    {
        List<FieldInfo> fields = GetFields();

        unchecked
        {
            int hash = 17;

            foreach (FieldInfo field in fields)
            {
                hash = hash * 397 + field.GetValue(classInstance).GetHashCode();
            }
            return hash;
        }
    }

    public bool Equals(T classInstance, object obj)
    {
        if (ReferenceEquals(null, obj))
        {
            return false;
        }
        if (ReferenceEquals(this, obj))
        {
            return true;
        }
        if (classInstance.GetType() != obj.GetType())
        {
            return false;
        }

        return Equals(classInstance, (T)obj);
    }

    private bool Equals(T classInstance, T otherInstance)
    {
        List<FieldInfo> fields = GetFields();

        foreach (var field in fields)
        {
            if (!field.GetValue(classInstance).Equals(field.GetValue(otherInstance)))
            {
                return false;
            }
        }

        return true;
    }

    private List<FieldInfo> GetFields()
    {
        Type myType = typeof(T);

        List<FieldInfo> fields = myType.GetTypeInfo().DeclaredFields.ToList();
        return fields;
    }
}

Aqui está como é usado em uma classe:

public override bool Equals(object obj)
    {
        return new Equality<ClassName>().Equals(this, obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return new Equality<ClassName>().GetHashCode(this);
        }
    }
kb4000
fonte