Lo que sería una buena hashCode para una clase DateRange

Question

Tengo la siguiente clase

public class DateRange
{
    private DateTime startDate;
    private DateTime endDate;
    public override bool Equals(object obj)
    {
        DateRange other = (DateRange)obj;
        if (startDate != other.startDate)
            return false;
        if (endDate != other.endDate)
            return false;
        return true;
    }
    ...
}

necesito para almacenar algunos valores en un diccionario vehículo con un DateRange como:

Dictionary<DateRange, double> tddList;

¿Cómo debo reemplazar el método de la clase GetHashCode() DateRange?

Answer 1

Depende de los valores que cabe esperar para ver lo que solía con.

Si se va a más a menudo tienen diferentes valores de día, en lugar de diferentes momentos en el mismo día, y estaban dentro de un siglo de ahora, me gustaría utilizar:

unchecked
{
    int hash = startDate.Year + endDate.Year - 4007;
    hash *= 367 + startDate.DayOfYear;
    return hash * 367 + endDate.DayOfYear;
}

Esto distribuye los bits bien con los valores esperados, mientras que reduce el número de bits perdidos en el desplazamiento. Nota que si bien hay casos en los que la dependencia de los números primos pueden ser sorprendentemente malo en colisiones (esp., Cuando el hash se alimenta en algo que se utiliza un módulo de la misma privilegiada en tratar de colisiones deben evitarse en la producción de un hash todavía de menor a distribuir entre sus cubos ) he optado por ir por encima de los números primos para las opciones más obvias, ya que están justo por encima y así sigue siendo bastante "apretado" para el bit-distribución. No me preocupa mucho acerca de cómo utilizar el mismo primer dos veces, ya que son tan "ajustado" de esta manera, pero hace daño si no tienes una colección basada en hash con 367 cubos. Este ofertas también (pero no tan bien) con fechas bien en el pasado o en el futuro, pero es terrible si el supuesto de que habrá pocos o ningún rangos dentro del mismo día (que difieren en el tiempo) es incorrecto ya que esa información se pierde por completo.

Si yo esperaba (o escribiendo para uso general por otras partes, y no es capaz de asumir lo contrario) me gustaría ir a:

int startHash = startDate.GetHashCode();
return (((startHash >> 24) & 0x000000FF) | ((startHash >> 8) & 0x0000FF00) | ((startHash << 8) & 0x00FF0000) | (unchecked((int)((startHash << 24) & 0xFF000000)))) ^ endDate.GetHashCode();

Cuando el primer método funciona en el supuesto de que el GetHashCode de propósito general en DateTime no es tan buena como queremos, éste depende de que sea bueno, pero las mezclas en torno a los bits de un valor.

Es bueno en el tratamiento de los casos difíciles más obvias, como los dos valores es la misma, o una distancia común entre sí (lotes por ejemplo de 1 día o 1 hora rangos). No es tan bueno en los casos en que el primer ejemplo que mejor funciona, pero el primero totalmente chupa si hay un montón de rangos utilizando el mismo día, pero diferentes momentos.

---

Editar: Para dar una respuesta más detallada a la preocupación de Dour:

Dour señala, con razón, que algunas de las respuestas en esta página los datos de perder. El hecho es que todos ellos se pierdan datos.

La clase se define en la pregunta tiene 8,96077483 × 10 ³⁷ diferentes estados válidos (o 9,95641648 × 10 ³⁶ si no nos preocupamos por la DateTimeKind de cada fecha) , y la salida de GetHashCode tiene 4294967296 estados posibles (uno de los cuales - cero - también va a ser utilizado como el código hash de un valor nulo, que puede estar comúnmente en comparación con en código real). Hagamos lo que hagamos, reducimos la información mediante una escala de 2,31815886 × 10 ²⁷ . Eso es una gran cantidad de información que ha perdido!

Es probablemente cierto que podemos perder más con unos que en otros. Sin duda, es fácil probar algunas soluciones puede perder más que otros por escribir un válido, pero muy pobre, respuesta.

(La solución válida peor posible es return 0; que es válido, ya que nunca los errores o desajustes en los objetos iguales, pero tan pobre como sea posible, ya que choca para todos los valores. El rendimiento de una colección basada en hash se convierte en O (n), y lento como O (n) va, como las constantes implicados son más altos que tales O (n) las operaciones como la búsqueda una lista desordenada).

Es difícil medir cuánto se pierde. ¿Cuánto más cambiante de algunos bits antes de perder que XORing bits de intercambio, teniendo en cuenta que XOR reduce a la mitad la cantidad de información dada. Incluso el x ^ y ingenuo no pierde más de un swap-y-xor, simplemente choca más en valores comunes; de cambiar y xor chocarán en los valores donde plain-xor no lo hace.

Una vez que tenemos una elección entre las soluciones que no están perdiendo mucha más información que sea posible, pero que regresan 4294967296 4294967296 o cerca de los valores posibles con una buena distribución entre esos valores, entonces la pregunta ya no es cuánto información se pierde (la respuesta que sólo 4,31376821 × 10 ^-28 de los restos de información originales) pero que información es Lost.

Esta es la razón por encima de mi primera sugerencia componentes ignora el tiempo. Hay 864000000000 "tics" (los 100nanosecond unidades DateTime tiene una resolución de) en un día, y me tiro de dos trozos de esas garrapatas (7,46496 × 10 ²³ posibles valores entre los dos) a propósito porque estoy pensando en un escenario en el que la información no se utiliza de todos modos. En este caso me ha estructurado deliberadamente el mecanismo de una manera tal como para recoger , que la información se pierde, que mejora el hash para una situación dada, pero hace que sea absolutamente inútil si tuviéramos valores diferentes, todos con fechas de inicio y final sin que suceden los mismos días pero en momentos diferentes.

Del mismo modo x ^ y no pierde más información que cualquiera de los otros, pero la información que no se pierde es más probable que sea significativo que con otras opciones.

En ausencia de cualquier forma de predecir qué información es probable que sea de importancia (esp. Si su clase será público y su código hash utilizado por código externo), entonces estamos más restringida en los supuestos que con seguridad puede hacer .

En su conjunto prime-multi o en métodos prime-mod son mejores en los que la información se pierden que los métodos basados ??en turnos, excepto cuando el mismo primer se utiliza en un hash, además, que puede tener lugar dentro de un método basado en hash, irónicamente con el mismo objetivo en mente (sin número de primos entre sí! primos pares), en cuyo caso son mucho peores. Por otro lado los métodos basados ??en turnos realmente caen si se alimenta en una dispersión adicional basada en turno. No hay ninguna hash perfecta para datos arbitrarios y uso arbitrario (excepto cuando una clase tiene pocos valores válidos y que coincide con todos ellos, en cuyo caso es más estrictamente una codificación de un hash que producimos).

En resumen, usted va a perder información de todo lo que hacemos, es , que a perder eso es importante.

Answer 2

Yo uso este enfoque desde Java eficaz para combinar los hashes:

unchecked
{
    int hash = 17;
    hash = hash * 31 + field1.GetHashCode();
    hash = hash * 31 + field2.GetHashCode();
    ...
    return hash;
}

No hay razón por la que no debería trabajar bien en esta situación.

Answer 3

Bien, considere cuáles son las características de una buena función hash debe tener. Es debe

• estar de acuerdo con los iguales - es decir, si iguales es cierto para los dos objetos a continuación, los dos códigos hash tienen que ser también el mismo
.
• Nunca bloquee

Y debe

• ser muy rápido
• dar resultados diferentes para las entradas similares

Lo que quiero hacer es llegar a un algoritmo muy simple; por ejemplo, tomando los 16 bits del código hash de la primera y 16 bits del código hash de la segunda, y la combinación de ellos juntos. Haga usted mismo un caso de prueba de representativas muestras; intervalos de tiempo que es probable que sean realmente utilizadas, y ver si este algoritmo da una buena distribución.

Una opción común es la función XOR de los dos valores hash juntos. Esto no es necesariamente una buena idea para este tipo, ya que parece probable que alguien va a querer representar el rango de longitud cero que va desde X a X. Si XOR los hashes de dos DateTime iguales que siempre obtenga cero, lo que parece una receta para una gran cantidad de colisiones hash.

Answer 4

Hay que cambiar un extremo de la gama, de lo contrario serán iguales dos fechas de hash a cero, un escenario bastante común que imaginar:

return startDate.GetHashCode() ^ (endDate.GetHashCode() << 4);

Answer 5

return startDate.GetHashCode() ^ endDate.GetHashCode();

podría ser un buen comienzo. Usted tiene que comprobar que se obtiene una buena distribución cuando hay la misma distancia entre startDate y endDate, pero diferentes fechas.