.net - ¿Cuál es el mejor algoritmo para un System.Object.GetHashCode anulado?
algorithm (17)
Tipo Anónimo
Microsoft ya proporciona un buen generador genérico de HashCode: simplemente copie los valores de su propiedad / campo a un tipo anónimo y cítelo:
new { PropA, PropB, PropC, PropD }.GetHashCode();
Esto funcionará para cualquier número de propiedades. No utiliza boxeo. Simplemente utiliza el algoritmo ya implementado en el marco para tipos anónimos.
ValueTuple - Actualización para C # 7
Como @cactuaroid menciona en los comentarios, se puede usar una tupla de valor. Esto guarda algunas pulsaciones de teclas y, lo que es más importante, se ejecuta únicamente en la pila (sin basura):
(PropA, PropB, PropC, PropD).GetHashCode();
(Nota: la técnica original que usa tipos anónimos parece crear un objeto en el montón, es decir, basura, ya que los tipos anónimos se implementan como clases, aunque esto podría ser optimizado por el compilador. Sería interesante comparar estas opciones, pero La opción de tupla debe ser superior.
En el método .NET System.Object.GetHashCode se usa en muchos lugares, a través de las bibliotecas de clase base .NET. Especialmente al encontrar artículos en una colección rápida o para determinar la igualdad. ¿Existe un algoritmo / práctica recomendada estándar sobre cómo implementar la anulación de GetHashCode para mis clases personalizadas para no degradar el rendimiento?
Aquí está mi ayudante de código hash.
Su ventaja es que utiliza argumentos de tipo genérico y, por lo tanto, no causará el boxeo:
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();
}
}
También tiene un método de extensión para proporcionar una interfaz fluida, por lo que puede usarlo así:
public override int GetHashCode()
{
return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}
o así:
public override int GetHashCode()
{
return 0.CombineHashCode(Manufacturer)
.CombineHashCode(PartN)
.CombineHashCode(Quantity);
}
Aquí está mi clase de ayudante usando la implementación de Jon Skeet .
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);
}
Si desea evitar escribir un método de extensión 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;
}
Sigue siendo genérico, aún evita cualquier asignación de almacenamiento dinámico y se usa exactamente de la misma manera:
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);
}
Actualización después del comentario de Martin:
obj != null causó boxeo, así que cambié al comparador predeterminado.
- Ver esta respuesta en relación con el rendimiento del comparador predeterminado.
- Vea esta pregunta para una discusión sobre los códigos hash de valores nulos.
Edición (mayo 2018):
EqualityComparer<T>.Default getter ahora es un intrínseco de JIT; Stephen Toub menciona la solicitud de extracción en esta publicación del blog .
Aquí hay otra implementación fluida del algoritmo publicado anteriormente por Jon Skeet , pero que no incluye asignaciones ni operaciones de boxeo:
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);
}
}
El compilador asegurará HashValueque no se llame con una clase debido a la restricción de tipo genérico. Pero no hay soporte para el compilador HashObjectya que agregar un argumento genérico también agrega una operación de boxeo.
En la mayoría de los casos en los que Equals () compara varios campos, en realidad no importa si el hash de GetHash () aparece en un campo o en muchos. Solo tiene que asegurarse de que el cálculo del hash sea realmente barato ( sin asignaciones , por favor) y rápido ( sin cómputos pesados y ciertamente no hay conexiones de base de datos) y proporciona una buena distribución.
El levantamiento de pesas debe ser parte del método Equals (); El hash debe ser una operación muy barata para permitir llamar a Equals () en la menor cantidad de elementos posible.
Y un último consejo: no confíe en que GetHashCode () sea estable en múltiples ejecuciones de aplicaciones . Muchos tipos de .Net no garantizan que sus códigos hash permanezcan iguales después de un reinicio, por lo que solo debe usar el valor de GetHashCode () para las estructuras de datos de memoria.
Este es bueno:
/// <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());
}
}
Y aquí está cómo usarlo:
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);
}
}
Hasta hace poco mi respuesta habría sido muy cercana a la de Jon Skeet. Sin embargo, recientemente comencé un proyecto que usaba tablas hash de potencia de dos, es decir, tablas hash donde el tamaño de la tabla interna es 8, 16, 32, etc. Hay una buena razón para favorecer los tamaños de los números primos, pero Son algunas de las ventajas del poder de dos tamaños también.
Y bastante chupó. Entonces, después de un poco de experimentación e investigación, comencé a volver a hacer hash con mis hashes con lo siguiente:
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);
}
}
Y entonces mi tabla hash de poder de dos ya no apestaba más.
Esto me molestó, sin embargo, porque lo anterior no debería funcionar. O más precisamente, no debería funcionar a menos que el GetHashCode() original fuera pobre de una manera muy particular.
Volver a mezclar un código hash no puede mejorar un buen código hash, porque el único efecto posible es que introduzcamos algunas colisiones más.
Volver a mezclar un código hash no puede mejorar un código hash terrible, porque el único efecto posible es que cambiemos, por ejemplo, un gran número de colisiones en el valor 53 a un gran número de valor 18,3487,291.
Volver a mezclar un código hash solo puede mejorar un código hash que funcionó al menos bastante bien para evitar colisiones absolutas a lo largo de su rango (2 32 valores posibles) pero mal para evitar colisiones cuando el módulo está inactivo para su uso real en una tabla hash. Si bien el módulo más simple de una tabla de potencia de dos hizo esto más evidente, también tuvo un efecto negativo con las tablas de números primos más comunes, eso no fue tan obvio (el trabajo adicional en remashing sería mayor que el beneficio , pero el beneficio aún estaría allí).
Edit: También estaba usando direccionamiento abierto, lo que también habría aumentado la sensibilidad a la colisión, quizás más que el hecho de que era el poder de dos.
Y bueno, fue perturbador la forma en que las implementaciones de string.GetHashCode() en .NET (o estudio here ) podrían mejorarse de esta manera (en el orden de las pruebas que se ejecutan entre 20 y 30 veces más rápido debido a menos colisiones) y más perturbador cómo muchos de mis propios códigos hash podrían mejorarse (mucho más que eso).
Todas las implementaciones de GetHashCode () que codifiqué en el pasado, y que de hecho usé como base de las respuestas en este sitio, fueron mucho peores de lo que había logrado . La mayor parte del tiempo fue "lo suficientemente bueno" para muchos de los usos, pero quería algo mejor.
Así que dejé ese proyecto a un lado (de todos modos era un proyecto favorito) y comencé a ver cómo producir un código hash bueno y bien distribuido en .NET rápidamente.
Al final me decidí por portar SpookyHash a .NET. De hecho, el código anterior es una versión de ruta rápida que utiliza SpookyHash para producir una salida de 32 bits a partir de una entrada de 32 bits.
Ahora, SpookyHash no es un pedazo de código fácil de recordar. Mi puerto es aún menos porque entregué a mano mucho para una mejor velocidad *. Pero para eso es la reutilización del código.
Luego puse ese proyecto a un lado, porque así como el proyecto original produjo la pregunta de cómo producir un mejor código hash, ese proyecto produjo la pregunta de cómo producir un mejor memcpy de .NET.
Luego regresé y produje muchas sobrecargas para alimentar fácilmente casi todos los tipos nativos (excepto el decimal †) en un código hash.
Es rápido, por lo que Bob Jenkins merece la mayor parte del crédito porque su código original que porté es aún más rápido, especialmente en máquinas de 64 bits para las cuales el algoritmo está optimizado para ‡.
El código completo se puede ver en https://bitbucket.org/JonHanna/spookilysharp/src pero considere que el código anterior es una versión simplificada de este.
Sin embargo, como ya está escrito, se puede utilizar más fácilmente:
public override int GetHashCode()
{
var hash = new SpookyHash();
hash.Update(field1);
hash.Update(field2);
hash.Update(field3);
return hash.Final().GetHashCode();
}
También toma valores iniciales, por lo que si necesita lidiar con información no confiable y desea protegerse contra los ataques Hash DoS, puede establecer una semilla basada en el tiempo de actividad o similar, y hacer que los atacantes no puedan predecir los resultados:
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();
}
* Una gran sorpresa en esto es que alineó manualmente un método de rotación que devolvió (x << n) | (x >> -n) (x << n) | (x >> -n) cosas mejoradas. Hubiera estado seguro de que la fluctuación de fase hubiera incluido eso para mí, pero el perfil mostró lo contrario.
† decimal no es nativo desde la perspectiva de .NET aunque es de C #. El problema con esto es que su propio GetHashCode() considera la precisión como significativa, mientras que su propio Equals() no lo hace. Ambas son elecciones válidas, pero no se mezclan así. Al implementar su propia versión, debe elegir hacer una u otra, pero no puedo saber cuál desearía.
‡ A modo de comparación. Si se usa en una cadena, SpookyHash en 64 bits es considerablemente más rápido que string.GetHashCode() en 32 bits, que es ligeramente más rápido que string.GetHashCode() en 64 bits, que es considerablemente más rápido que SpookyHash en 32 bits, aunque aún es rápido suficiente para ser una elección razonable.
Por lo general, prefiero algo como la implementación dada en la fabulosa Java efectiva de Josh Bloch. Es rápido y crea un hash bastante bueno que es poco probable que cause colisiones. Elija dos números primos diferentes, por ejemplo, 17 y 23, y haga:
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 se señaló en los comentarios, es posible que sea mejor elegir un primo grande para multiplicar por. Aparentemente, 486187739 es bueno ... y aunque la mayoría de los ejemplos que he visto con números pequeños tienden a usar números primos, existen al menos algoritmos similares en los que a menudo se usan números no primos. Por ejemplo, en el ejemplo no muy FNV más adelante, he usado números que aparentemente funcionan bien, pero el valor inicial no es primo. (Sin embargo, la constante de multiplicación es primordial. No sé cuán importante es eso).
Esto es mejor que la práctica común de los códigos hash XOR por dos razones principales. Supongamos que tenemos un tipo con dos campos int :
XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y
Por cierto, el algoritmo anterior es el utilizado actualmente por el compilador de C # para tipos anónimos.
Esta página da bastantes opciones. Creo que para la mayoría de los casos, lo anterior es "suficientemente bueno" y es increíblemente fácil de recordar y hacer bien. La alternativa FNV es igualmente simple, pero usa diferentes constantes y XOR lugar de ADD como una operación de combinación. Se parece al código que se muestra a continuación, pero el algoritmo FNV normal opera en bytes individuales, por lo que esto requeriría una modificación para realizar una iteración por byte, en lugar de un valor hash de 32 bits. FNV también está diseñado para longitudes de datos variables, mientras que la forma en que lo estamos utilizando aquí es siempre para el mismo número de valores de campo. Los comentarios sobre esta respuesta sugieren que el código aquí en realidad no funciona tan bien (en el caso de muestra probado) como el enfoque de adición anterior.
// 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;
}
}
Tenga en cuenta que una cosa a tener en cuenta es que, idealmente, debería evitar que su estado sensible a la igualdad (y, por lo tanto, sensible al código hash) cambie después de agregarlo a una colección que depende del código hash.
Según la documentation :
Puede anular GetHashCode para tipos de referencia inmutables. En general, para los tipos de referencia mutables, debe reemplazar GetHashCode solo si:
- Puede calcular el código hash de campos que no son mutables; o
- Puede asegurarse de que el código hash de un objeto mutable no cambie mientras el objeto esté contenido en una colección que se base en su código hash.
Tengo una clase de Hashing en la biblioteca de Helper, la uso para este propósito.
/// <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;
}
Entonces, simplemente puedes usarlo como:
public override int GetHashCode()
{
return Hashing.RSHash(_field1, _field2, _field3);
}
No evalué su desempeño, así que cualquier comentario es bienvenido.
ReSharper usuarios de ReSharper pueden generar GetHashCode, Equals y otros con 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;
}
}
Bastante similar a la solución de Nightcoder, excepto que es más fácil aumentar los números primos si lo desea.
PD: Este es uno de esos momentos en los que vomitas un poco en tu boca, sabiendo que esto podría ser refaccionado en un solo método con 9 valores predeterminados pero sería más lento, así que solo cierras los ojos y tratas de olvidarlo.
/// <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;
}
}
}
Me encontré con un problema con flotantes y decimales utilizando la implementación seleccionada como la respuesta anterior.
Esta prueba falla (floats; hash es el mismo a pesar de que cambié 2 valores para 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));
Pero esta prueba pasa (con 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));
Cambié mi implementación para no usar GetHashCode para los tipos primitivos y parece funcionar mejor
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;
}
}
}
Microsoft lideró varias formas de hash ...
//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();
Puedo adivinar que para múltiples int grandes puedes usar esto:
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;
Y lo mismo para el multitipo : todos los convertidos primero en intusar, GetHashCode()luego los valores int serán xorados y el resultado será su hash.
Para aquellos que usan el hash como ID (me refiero a un valor único), el hash está naturalmente limitado a un número de dígitos, creo que eran 5 bytes para el algoritmo de hashing, al menos MD5.
Puede convertir varios valores en un valor hash y algunos de ellos serán iguales, así que no lo use como un identificador. (Tal vez algún día voy a usar tu componente)
Si no tenemos más de 8 propiedades (con suerte), aquí hay otra alternativa.
ValueTupleEs una estructura y parece tener una GetHashCodeimplementación sólida .
Eso significa que simplemente podríamos hacer esto:
// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();
Vamos a echar un vistazo a la aplicación actual de .NET Core de ValueTuple''s GetHashCode.
Esto es de 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);
}
Y esto es 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;
}
}
En inglés:
- Gire a la izquierda (desplazamiento circular) h1 por 5 posiciones.
- Suma el resultado y h1 juntos.
- XOR el resultado con h2.
- Comience realizando la operación anterior en {semilla aleatoria estática, h1}.
- Para cada elemento adicional, realice la operación en el resultado anterior y en el siguiente elemento (por ejemplo, h2).
Sería bueno saber más sobre las propiedades de este algoritmo de código hash ROL-5.
Lamentablemente, el aplazamiento ValueTuplede lo nuestro GetHashCodepuede no ser tan rápido como nos gustaría y esperamos. Este comentario en una discusión relacionada ilustra que la llamada directa HashHelpers.Combinees más eficaz. Por otro lado, ese es interno, así que tendríamos que copiar el código, sacrificando mucho de lo que habíamos ganado aquí. Además, seríamos responsables de recordar primero Combinecon la semilla aleatoria. No sé cuáles son las consecuencias si saltamos ese paso.
A partir de https://github.com/dotnet/coreclr/pull/14863 , hay una nueva forma de generar códigos hash que es muy simple. Solo escribe
public override int GetHashCode()
=> HashCode.Combine(field1, field2, field3);
Esto generará un código hash de calidad sin que tenga que preocuparse por los detalles de la implementación.
Aquí está mi enfoque simplista. Estoy usando el patrón clásico del constructor para esto. Es de tipo seguro (sin boxeo / unboxing) y también compatible con .NET 2.0 (sin métodos de extensión, etc.)
Se usa así:
public override int GetHashCode()
{
HashBuilder b = new HashBuilder();
b.AddItems(this.member1, this.member2, this.member3);
return b.Result;
}
Y aquí está la clase de constructor de 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);
}
}
}
La mayoría de mi trabajo se realiza con conectividad de base de datos, lo que significa que todas mis clases tienen un identificador único de la base de datos. Siempre uso el ID de la base de datos para generar el código hash.
// Unique ID from database
private int _id;
...
{
return _id.GetHashCode();
}