¿Hay una manera de obtener un código hash de un flotador con épsilon?

Question

Es bien sabido que la comparación de balsas por == suele ser un error. En una clase de 3D-vector (con componentes de flotador X, Y, Z) que escribí, dos vectores se consideran iguales si su distancia se considera cero.

    public override bool Equals(object obj)
    {
        if (obj == null) {
            return false;
        }

        if (GetType () != obj.GetType ()) {
            return false;
        }

        float d = DistSq ((Vec) obj);

        return IsConsideredZero (d);
    }

    public float DistSq(Vec p)
    {
        Vec d = this - p;
        return d.LengthSq ();
    }

    public float LengthSq()
    {
        return X * X + Y * Y + Z * Z;
    }

    private const float VEC_COMPARE_EPSILON_ABS = 1E-05f;
    public static bool IsConsideredZero(float f)
    {
        return Math.Abs (f) < VEC_COMPARE_EPSILON_ABS;
    }

Hasta ahora, todo funcionaba bien. Sin embargo, ahora me gustaría obtener un código hash del vector. Puedo ver que algo como hash = (int)X^(int)Y^(int)Z está destinada al fracaso.

Lo mejor que podía ocurrió fue:

    public override int GetHashCode()
    {
        return 0;
    }

Esto, por supuesto, una especie de chupa. ¿Hay alguna manera de obtener un código hash razonable? NANS valores especiales y otros son posibles, pero poco probable, en caso de que eso es importante.

Answer 1

Es imposible asumir que desea tener las propiedades normales código hash / igualdad:

• Si X = Y y Y = Z entonces X = Z (transitividad)
• Si X = Y entonces Y = X (commutivity)
• X = X para todas las X (reflexividad)

La primera regla es el problema - porque si cada valor se considera "igual" a la siguiente mayor número representable, se termina con todos los números que son iguales. Por ejemplo, supongamos que un número se considera igual a otro que están dentro de 0,1:

0 es igual a 0,08   0,08 es igual a 0,16   0,16 es igual a 0,24

=> 0 es igual a 0,16 por la regla de transitividad   => 0 es igual a 0,24 por la regla de transitividad

(etc)

Si ignora la regla de transitividad, entonces todavía (presumiblemente) desea que los valores "iguales" a hashcodes tienen iguales. Esto hace cumplir eficazmente la regla de transitividad - en el ejemplo anterior, 0 y 0,08 tienen que tener iguales hashcodes, al igual que 0 y 0,16. Por lo tanto 0 y 0,16 tienen que tener los mismos hashcodes, y así sucesivamente. Por lo tanto se puede tener sin utilidad código hash -. Que tiene que ser una constante

Answer 2

No creo que se puede tener un código hash que es consistente con su método de comparación debido a que el último no es transitiva: por cualquiera de los tres vectores A, B, C, si A.Equals(B) y B.Equals(C) son ciertas, podrían todavía ser el caso A.Equals(C) que es falsa. (Imagínese si la distancia entre A y B es 6e-6, entre B y C es 6e-6, y entre A y C es 1.2e-5) Sin embargo, la igualdad de hashcodes siempre es transitivo, ya que son sólo números.

En este caso, que acababa de crear un método de código hash que calcula el hash basado en los valores exactos de las coordenadas de punto flotante, y la mención en la documentación que es inconsistente con los iguales. Yo sé que no es realmente una solución, pero teniendo en cuenta que no creo que existe una solución real, es mejor tener un código hash no trivial de sólo 0.

Answer 3

Me temo que no es en el caso general. Un bosquejo de una prueba es el siguiente:

Tome cualquier dos números a y b. Deje que la diferencia entre ellos será d. A continuación, si crea los números d / épsilon con un paso épsilon en el medio, cada paso debe ser "igual" al paso antes, que por la semántica código hash tienen el mismo código hash. Así que todos los números deben tener el mismo código hash.

Sólo se puede resolver este problema si se añade alguna otra restricción.

Como acotación al margen, que la definición de Iguales está mal, así, ya que puede ser cierto que a.Equals (b) y (c) b.Equals pero no a.Equals (c), lo que es malo para los iguales. Esto se conoce como romper el transitividad propiedad.

¿Qué puedo hacer entonces?

La solución depende de lo que está utilizando el hash para. Una solución podría ser la introducción de una red conceptual. Cambiar las iguales y código hash por lo que dos números son iguales si en el mismo cubo de rejilla, mediante el redondeo a un número constante de cifras decimales, a continuación, teniendo iguales y código hash en el número redondeado. Si ser cercano a cero es un caso importante, añadir un desplazamiento de épsilon / 2 antes del redondeo, por lo que el cero es el centro del cubo. Esto es correcto, pero se puede tener dos números de cerrar arbitrariamente entre sí (dentro de los límites de flotación) sin ser iguales. Así que para algunas aplicaciones que va a estar bien, otros no lo serán. Esto es similar a una idea de mghie .

Answer 4

Todo el mundo es correcto ...

Sin embargo, una cosa que a menudo se hace es extender el concepto de hash de un poco. Considere una partición de su espacio 3d con los rectángulos con un lado >> épsilon.

El hash de un punto es el cuadro que pertenece. Cuando desee para buscar un punto, no marca el punto a la casilla correspondiente (como lo haría para un hash regular) pero para las cajas vecinas también. En 3d que debe salir con un máximo de 8 cajas.

Answer 5

Cualquiera que sea la técnica que utilice tendrá problemas debido a que usted plantea algo que no es posible resolver.

Lo que queremos es 1) de hash uniformemente repartida de modo que durante la mayor números a y b, donde a! = B entonces a.GetHashCode ()! = B.GetHashCode (), pero 2) donde a == b continuación a.GetHashCode () == b.GetHashCode () debe ser verdad.

Volviendo una constante fulfills (2), pero no (1).

Puede demostrar que el redondeo al 1E-5 límites y usar eso como un hash viola Cumple (1), pero viola (2). Tome 1E y 2E-5-5, por ejemplo. Redondeo produciría dos valores hash diferentes pero igual comparación. Esto viola la restricción (2) anterior. Se puede generalizar fácilmente esto para demostrar que cualquier redondeo del número se encontrará con un problema similar.

Te recomiendo que elige un enfoque diferente. Supongo que el problema subyacente es determinar si algún punto está cerca de un punto que ya tiene. Recomiendo recusively dividiendo el espacio de coordenadas en medio (donde los puntos a lo largo de la frontera (es decir <= 1E-5 a partir de un límite) en ambas mitades). Si se divide progresivamente el espacio (piensa árbol binario) se puede construir una estructura de datos que rápidamente se devolverá el resultado que desee y sea bastante fácil de construir.

Si perdí mi conjetura y debe utilizar un hash a continuación, puede hacer lo que quiera con dos valores hash cada redondeo a 1E-5, pero compensado por 5E-6. Todos los puntos igual compararán igual en uno de los dos valores hash. Para ello sería necesario que introduzca el punto en la tabla hash dos veces, una para cada rutina de hash.