Qual é o melhor algoritmo para uma System.Object.GetHashCode substituído?

https://stackoverflow.com/questions/263400

06-07-2019
|

Pergunta

método System.Object.GetHashCode Em .NET é usado em um monte de lugares, em todas as bibliotecas de classes base do .NET. Especialmente quando encontrar itens em uma coleção rápida ou para determinar a igualdade. Existe um padrão / melhores práticas algoritmo sobre como implementar a substituição GetHashCode por meus classes personalizadas então eu faço o desempenho não degrade?

Solução

Eu costumo ir com algo parecido com a implementação dada em fabuloso Effective Java. É rápido e cria um muito bom de hash que é pouco provável de causar colisões. Escolha dois números primos diferentes, v.g. 17 e 23, e fazer:

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; } }

Como observado nos comentários, você pode achar que é melhor para escolher um grande privilegiada para multiplicar por vez. Aparentemente 486187739 é bom ... e embora a maioria dos exemplos que eu vi com pequenos números tendem a primos de uso, há pelo menos algoritmos semelhantes onde os números não primos são muitas vezes utilizados. No exemplo não-quite- FNV mais tarde , por exemplo, eu usei números que aparentemente funcionam bem - mas o valor inicial não é primo. (A constante multiplicação é nobre embora. Eu não sei bem como isso é importante.)

Este é melhor do que a prática comum de XORing hashcodes por duas razões principais. Suponha que temos um tipo com dois campos int:

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

Pela maneira, o algoritmo anterior é aquele usado atualmente pelo compilador C # para tipos anônimos.

Esta página dá muito poucas opções. Eu acho que para a maioria dos casos acima é "suficientemente bom" e é incrivelmente fácil de lembrar e acertar. O FNV alternativa é semelhante simples, mas utiliza diferentes constantes e XOR em vez de como ADD uma operação combinando. Parece algo como o código abaixo, mas o algoritmo FNV normais opera em bytes individuais, de modo que este exigiria a modificação para executar uma iteração por byte, em vez de por valor hash de 32 bits. FNV também é projetado para comprimentos variáveis ??de dados, ao passo que o caminho que estamos usando aqui é sempre para o mesmo número de valores de campo. Comentários sobre esta resposta sugerem que o código aqui na verdade não funciona bem (no caso da amostra analisada) como a abordagem além acima.

// 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; } }

Note que uma coisa a ter em conta é que, idealmente, você deve evitar que o seu estado (e, portanto, sensível ao hashcode) sensíveis à igualdade de mudar após adicioná-lo a uma coleção que depende do código de hash.

De acordo com a href="https://docs.microsoft.com/en-us/dotnet/api/system.object.gethashcode#notes-to-inheritors" documentação :

Você pode substituir GetHashCode para tipos de referência imutáveis. Em geral, para tipos de referência mutáveis, você deve substituir GetHashCode somente se:

Você pode calcular o código hash de campos que não são mutáveis; ou

Você pode garantir que o código hash de um objeto mutável não muda enquanto o objeto está contido em uma coleção que se baseia em seu código hash.

Outras dicas

Anonymous Tipo

A Microsoft já oferece um bom gerador de HashCode genérica: copiar apenas os seus valores propriedade / campo para um tipo anônimo e haxixe-lo:

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

Isto irá funcionar para qualquer número de propriedades. Ele não usa o boxe. Ele só usa o algoritmo já implementadas no âmbito de tipos anônimos.

ValueTuple - Atualização para o C # 7

Como @cactuaroid menciona nos comentários, um valor tupla pode ser usado. Isso economiza algumas teclas e mais importante executado puramente na pilha (sem lixo):

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

(Nota: A técnica original usando tipos anônimos parece criar um objeto na pilha, ou seja, lixo, já que tipos anônimos são implementados como classes, embora isso possa ser otimizado pelo compilador Seria interessante para aferir estas opções. , mas a opção tupla deve ser superior.)

Aqui está o meu hashcode ajudante.
É de vantagem é que ele usa argumentos de tipo genérico e, portanto, não irá causar boxe:

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(); } }

Também tem método de extensão para fornecer uma interface fluente, para que você possa usá-lo como este:

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

ou menos assim:

public override int GetHashCode() { return 0.CombineHashCode(Manufacturer) .CombineHashCode(PartN) .CombineHashCode(Quantity); }

Eu tenho uma classe Hashing na biblioteca Helper que eu usá-lo para este fim.

/// <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; }

Em seguida, basta você pode usá-lo como:

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

Eu não avaliar o seu desempenho, portanto, qualquer feedback é bem-vinda.

Aqui está minha classe auxiliar usando de Jon Skeet implementação .

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); } }

Uso:

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

Se você quiser evitar escrever um método de extensão para System.Int32:

public 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; }

Ainda é genérico, ele ainda evita qualquer alocação de pilha e é usado exatamente da mesma maneira:

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); }

Update após o comentário de Martin:

obj != null boxe causada por isso eu mudei para o comparador padrão.

Consulte esta resposta em relação ao desempenho do comparador padrão.

Consulte esta questão para uma discussão sobre os códigos de hash de valores nulos.

Editar (maio de 2018):

EqualityComparer<T>.Default getter é agora uma intrínseca JIT - o solicitação de recebimento é mencionado por Stephen Toub em este post .

Na maioria dos casos em Equals () compara vários campos Realmente não importa se seus GetHash () hashes em um campo ou em muitos. Você apenas tem que se certificar de que o cálculo do hash é realmente barato ( Não alocações , por favor) e rápido ( Não pesados ??cálculos certamente não conexões de banco de dados e) e proporciona uma boa distribuição .

O trabalho pesado deve ser parte dos Iguais () Método; o hash deve ser uma operação muito barato para permitir chamando Equals () sobre como poucos itens quanto possível.

E uma dica final: Não confie em GetHashCode () ser estável em várias execuções Aplicação . Muitos tipos .Net não garantem seus códigos de hash para permanecer o mesmo após um reinício, assim você só deve usar o valor de GetHashCode () para em estruturas de dados de memória.

Até recentemente a minha resposta teria sido muito perto de Jon Skeet está aqui. No entanto, recentemente iniciou um projeto que usou potência de duas tabelas de hash, que é tabelas de hash, onde o tamanho da tabela interna é de 8, 16, 32, etc. Há uma boa razão para favorecer tamanhos de números primos, mas há algumas vantagens em tamanhos poder-de-dois também.

E é praticamente sugado. Então, depois de um pouco de experimentação e pesquisa eu comecei a re-hash meus hashes com o seguinte:

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); } }

E então meu tabela hash potência de dois não sugar mais.

Esta me perturbado, porém, porque o acima não deve funcionar. Ou, mais precisamente, ele não deve trabalhar a menos que o GetHashCode() original pobres de uma maneira muito particular.

Re-misturando um hashcode não pode melhorar um grande hashcode, porque o efeito só é possível é que nós apresentamos mais algumas colisões.

Re-mistura um código hash não pode melhorar um código hash terrível, porque o efeito só é possível é que mudar por exemplo um grande número de colisões no valor de 53 a um grande número de valor 18,3487,291.

Re-mistura de um código de hash só pode melhorar um código de hash que fez pelo menos razoavelmente bem para evitar colisões absolutos toda a sua gama (2 ³² valores possíveis) mas mal em evitando colisões quando modulo'd para baixo pelo uso real em uma tabela hash. Enquanto o módulo simples de uma tabela potência de dois fizeram isso mais aparente, ele também estava tendo um efeito negativo com as tabelas de números primos mais comuns, que só não era tão óbvio (o trabalho extra em rehashing superariam o benefício , mas o benefício ainda estaria lá).

Edit:. Eu também estava usando open-endereçamento, o que também teria aumentado a sensibilidade à colisão, talvez mais do que o fato de que era potência de dois

E bem, ele estava perturbando o quanto as implementações string.GetHashCode() em .NET (ou estudo aqui ) podem ser melhorados desta forma (na ordem de cerca de 20-30 ensaios executando tempos mais rápido devido ao menor número de colisões) e mais preocupante quanto os meus próprios códigos de hash pode ser melhorada (muito mais do que isso).

Todo o GetHashCode () implementações que eu codificados no passado, e de fato usados ??como a base de respostas sobre este local, eram muito piores do que eu throught . Grande parte do tempo que era "bom o suficiente" para grande parte dos usos, mas eu queria algo melhor.

Então eu coloquei esse projeto para um lado (que era um projeto de estimação de qualquer maneira) e começou a olhar para a forma de produzir um bom, código hash bem distribuída em .NET rapidamente.

No final, eu liquidada em portar SpookyHash para .NET. Na verdade, o código acima é uma versão fast-path de usar SpookyHash para produzir uma saída de 32 bits a partir de uma entrada de 32 bits.

Agora, SpookyHash não é uma boa rápido para lembrar pedaço de código. Meu porto de que é ainda menos porque eu mão-embutido um monte de que para uma melhor velocidade *. Mas isso é o que a reutilização de código é para.

Então eu coloquei que projeto para um lado, porque, assim como o projeto original tinha produzido a questão de como produzir um melhor código hash, de modo que o projeto produziu a questão de como produzir uma melhor .NET memcpy.

Então eu voltei, e produziu uma série de sobrecargas para facilmente alimentar apenas sobre todos os tipos nativos (exceto decimal †) em um código hash.

É rápido, para a qual Bob Jenkins merece a maior parte do crédito porque seu código original eu portado de é ainda mais rápido, especialmente em máquinas de 64 bits que o algoritmo é otimizado para ‡.

O código completo pode ser visto em https://bitbucket.org/JonHanna/spookilysharp/src , mas consideram that o código acima é uma versão simplificada do mesmo.

No entanto, uma vez que está agora já escrito, pode-se fazer uso dele mais facilmente:

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

Ele também leva valores de semente, por isso, se você precisa lidar com entrada não confiável e deseja proteger contra ataques DoS Hash você pode definir uma semente com base em tempo de atividade ou similar, e tornar os resultados imprevisíveis por atacantes:

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(); }

* A grande surpresa neste processo é que a mão-inlining um método de rotação que (x << n) | (x >> -n) voltou melhorou as coisas. I teria sido se que o jitter teria embutido que para mim, mas Profiling mostrou o contrário.

† decimal não é nativa a partir da perspectiva .NET que seja a partir do C #. O problema com ele é que sua própria precisão GetHashCode() trata como significativa, enquanto a sua própria Equals() não. Ambos são opções válidas, mas não misturado assim. Na execução de sua própria versão, você precisa optar por fazer um, ou o outro, mas eu não posso saber o que você gostaria.

‡ A título de comparação. Se usado em uma corda, o SpookyHash em 64 bits é consideravelmente mais rápido do que string.GetHashCode() em 32 bits que é ligeiramente mais rápido do que string.GetHashCode() em 64 bits, o que é consideravelmente mais rápido do que SpookyHash em 32 bits, embora ainda rápido o suficiente para ser uma escolha razoável.

Este é um bom:

/// <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()); } }

E aqui está como usá-lo:

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); } }

Aqui está outra implementação fluente do o algoritmo postou acima por Jon Skeet , mas que não inclui alocações ou operações de boxe:

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(); } } }

Uso:

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); } }

O compilador irá garantir HashValue não é chamado com uma classe devido ao tipo de restrição genérica. Mas não há nenhum suporte de compilador para HashObject desde a adição de um argumento genérico também adiciona uma operação de boxe.

A partir de https://github.com/dotnet/coreclr/pull/14863, há uma nova maneira de gerar códigos de hash que é super simples! Basta escrever

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

Isso irá gerar um código de qualidade de hash sem que você tenha que se preocupar com os detalhes de implementação.

Aqui está a minha abordagem simplista. Eu estou usando o padrão do construtor clássico para isso. É typesafe (sem boxe / unboxing) e também com compatbile .NET 2.0 (não há métodos de extensão, etc.).

É usado como este:

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

E aqui é a classe construtor acutal:

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); } } }

ReSharper usuários podem gerar GetHashCode, iguais, e outros com 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; } }

A maioria do meu trabalho é feito com a conectividade de banco de dados que significa que minhas aulas todos têm um identificador único do banco de dados. Eu sempre uso o ID do banco de dados para gerar o código hash.

// Unique ID from database private int _id; ... { return _id.GetHashCode(); }

Quase semelhante à solução de nightcoder exceto que é mais fácil de primos raise se você quiser.

PS: Este é um daqueles momentos em que você Puke um pouco em sua boca, sabendo que isso poderia ser reformulado em um método com 9 padrão de mas seria mais lento, então você apenas fechar os olhos e tentar esquecê-la .

/// <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; } } }

Se nós não mais do que 8 propriedades (espero) tem, aqui é outra alternativa.

ValueTuple é um struct e parece ter uma implementação GetHashCode sólida.

Isso significa que nós podemos simplesmente fazer isso:

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

Vamos dar uma olhada implementação atual do .NET Núcleo de ValueTuple de GetHashCode.

Esta é a partir 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); }

E este é de 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; } }

Em Inglês:

rodar para a esquerda (deslocamento circular) h1 por 5 posições.

Adicione o resultado e h1 juntos.

XOR o resultado com h2.

Comece por realizar a operação acima em {semente aleatória estática, h1}.

Para cada produto adicional, efectuar a operação no resultado anterior e o próximo item (por exemplo, H2).

Seria bom para saber mais sobre as propriedades deste algoritmo de código hash ROL-5.

Infelizmente, adiando para ValueTuple para o nosso próprio GetHashCode pode não ser tão rápido como gostaríamos e esperar. Este comentário em uma discussão relacionada ilustra que HashHelpers.Combine chamando diretamente é mais performant . Por outro lado, que um é interno, então nós teríamos que copiar o código, sacrificando muito do que tinha ganho aqui. Além disso, seria responsável por lembrar-se de primeiro Combine com a semente aleatória. Eu não sei quais são as consequências se pular essa etapa.

.NET Núcleo 2.1 e acima

Se você estiver usando .NET núcleo 2.1 ou acima, você pode usar o System.HashCode struct. Existem dois métodos de usá-lo:

HashCode.Combine

O método Combine pode ser usado para criar um código de hash, dado até oito objectos.

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

HashCode.Add

O método Add ajuda você a lidar com coleções:

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

Você pode ler o post completo GetHashCode Made Easy 'para mais detalhes e comentários.

Exemplo de Utilização

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); }

Implementação

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; } }

Eu corri em um problema com carros alegóricos e decimais, utilizando a implementação selecionada como a resposta acima.

Este teste falhar (flutuadores; hash é o mesmo, mesmo que I transferido 2 valores a ser negativo):

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));

Mas isso passa teste (com ints):

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));

Eu mudei de implementação para não usar GetHashCode para os tipos primitivos e parece funcionar melhor

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; } } }

Esta é uma classe auxiliar estática que a implementação de instrumentos de Josh Bloch; e fornece sobrecargas explícitas para "prevenir" o boxe, e também para implementar o hash especificamente para as longas primitivos.

Você pode passar uma comparação de string que corresponde ao seu implementação iguais.

Como a saída Hash é sempre um int, você pode apenas chamadas de hash cadeia.

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; } } }

Microsoft levar para várias formas de hashing ...

//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();

Eu posso adivinhar que para múltiplos grande int você pode usar isto:

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;

E mesmo para multi-tipo: todos convertidos primeiro a int usando GetHashCode() em seguida, os valores int será xor'ed eo resultado é o seu hash.

Para aqueles que usam hash como ID (quero dizer um valor único), hash é naturalmente limitada a um número de dígitos, eu acho que foi 5 bytes para algoritmo de hash, pelo menos MD5.

Você pode transformar vários valores para um valor hash e alguns deles ser o mesmo, por isso não usá-lo como um identificador. (Talvez algum dia eu vou usar o seu componente)

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow