Buena excepción GetHashCode () para la lista de objetos Foo respetando el orden

EnumerableObject : IEnumerable

envuelve una List

Si EnumerableObject a.SequenceEquals( EnumerableObject b) , entonces son iguales.

Por lo tanto, se debe implementar un GetHashCode . El problema es XORing cada elemento en la lista devolverá el mismo código hash para cualquier lista con todos y solo los mismos elementos, independientemente de la orden. Esto está bien en términos de que funciona, pero dará lugar a muchas colisiones, lo que ralentizará la recuperación, etc.

¿Cuál es un método GetHashCode bueno y rápido para las listas de objetos que depende del pedido?

Lo haría de la misma manera que normalmente combino los códigos hash, con una sum y una multiplicación:

 public override int GetHashCode() { unchecked { int hash = 19; foreach (var foo in foos) { hash = hash * 31 + foo.GetHashCode(); } return hash; } } 

(Tenga en cuenta que no debe agregar nada a la lista después de que se haya utilizado para la clave en una tabla hash de cualquier descripción, ya que el hash cambiará. Esto también supone que no hay entradas nulas, si es posible, Necesito tener en cuenta eso.

En primer lugar, verifique que necesita un código hash en absoluto. ¿Vas a poner estas listas en una estructura hash-mapped (por ejemplo, diccionario, hashset, etc.)? Si no, olvídate de eso.

Ahora, asumiendo que quiere decir que EnumerableObject ya anula Equals(object) (y con suerte, también implementa IEquatable ) por alguna razón, entonces esto es realmente necesario. Desea equilibrar la velocidad con la distribución de bits.

Un buen punto de partida es un mult + add o un shift + xor como:

 public override int GetHashCode() { int res = 0x2D2816FE; foreach(var item in this) { res = res * 31 + (item == null ? 0 : item.GetHashCode()); } return res; } 

(Esto supone que está utilizando item.Equals () para su comparación de igualdad de secuencia, si está utilizando un igual de IEqualityComparer tendrá que llamar a su código hash).

Desde allí podemos optimizar.

Si no se permiten elementos nulos, elimine la verificación nula (tenga cuidado, esto hará que el código arroje si alguna vez encuentra un nulo).

Si las listas muy grandes son comunes, debemos reducir el número examinado, al mismo tiempo que intentamos no generar muchas colisiones. Compare las siguientes implementaciones diferentes:

 public override int GetHashCode() { int res = 0x2D2816FE; int max = Math.Min(Count, 16); for(int i = 0, i != max; ++i) { var item = this[i]; res = res * 31 + (item == null ? 0 : item.GetHashCode()); } return res; } public override int GetHashCode() { int res = 0x2D2816FE; int min = Math.Max(-1, Count - 16); for(int i = Count -1, i != min; --i) { var item = this[i]; res = res * 31 + (item == null ? 0 : item.GetHashCode()); } return res; } public override int GetHashCode() { int res = 0x2D2816FE; int step = Count / 16 + 1; for(int i = 0, i < Count; i += step) { var item = this[i]; res = res * 31 + (item == null ? 0 : item.GetHashCode()); } return res; } 

Cada uno de estos restringe la cantidad total de elementos examinados, lo que acelera la ejecución pero corre el riesgo de tener valores hash de calidad más pobres. Cuál (si corresponde) es mejor depende de si las colecciones con el mismo inicio o el mismo final son más probables.

Al cambiar el número 16 de arriba se ajusta el equilibrio; más pequeño es más rápido pero más alto es mejor calidad de hash con un menor riesgo de colisiones hash.

Editar: Y ahora puedes usar mi implementación de SpookyHash v. 2 :

 public override int GetHashCode() { var hasher = new SpookyHash();//use methods with seeds if you need to prevent HashDos foreach(var item in this) hasher.Update(item.GetHashCode());//or relevant feeds of item, etc. return hasher.Final().GetHashCode(); } 

Esto creará una distribución mucho mejor que mult + add o shift + xor, a la vez que es particularmente rápido (especialmente en procesos de 64 bits ya que el algoritmo está optimizado para eso, aunque también funciona bien en 32 bits).

El método .GetHashCode() generalmente solo devuelve un hash basado en la referencia del objeto (dirección del puntero). Esto se debe a que el cálculo del código hash de cada elemento en una lista enumerable puede requerir mucho tiempo. En lugar de sobreescribir el comportamiento existente, prefiero usar un método de extensión y usarlo solo cuando el código hash debe determinarse determinísticamente:

 public static class EnumerableExtensions { public static int GetSequenceHashCode(this IEnumerable list) { if (list == null) return 0; const int seedValue = 0x2D2816FE; const int primeNumber = 397; return list.Aggregate(seedValue, (current, item) => (current * primeNumber) + (Equals(item, default(TItem)) ? 0 : item.GetHashCode())); } } 

Esta es prácticamente la respuesta de Jon Skeet, pero con un mejor rendimiento. Descubrí que usar el código hash de cada elemento es costoso e innecesario para crear un buen hash. Esta versión solo usa el código hash de cada elemento de “poder de 2” (0, 1, 3, 7, etc.).

 static int GetHashCode(IReadOnlyList list) { unchecked { int hash = 19 * list.Count; int i = 1; while (i <= list.Count) { hash = (hash * 31) + list[i - 1].GetHashCode(); i *= 2; } return hash; } }