objective c - tributarios - Mejores prácticas para anular isEqual: y hash

terminos tributarios en ingles

Question

¿Cómo anula correctamente isEqual: en Objective-C? La "captura" parece ser que si dos objetos son iguales (según lo determinado por el método isEqual: , deben tener el mismo valor de hash.

La sección de Introspection de la Guía de isEqual: básicos de Cocoa tiene un ejemplo sobre cómo anular isEqual: copiado de la siguiente manera, para una clase llamada MyWidget :

- (BOOL)isEqual:(id)other {
    if (other == self)
        return YES;
    if (!other || ![other isKindOfClass:[self class]])
        return NO;
    return [self isEqualToWidget:other];
}

- (BOOL)isEqualToWidget:(MyWidget *)aWidget {
    if (self == aWidget)
        return YES;
    if (![(id)[self name] isEqual:[aWidget name]])
        return NO;
    if (![[self data] isEqualToData:[aWidget data]])
        return NO;
    return YES;
}

Verifica la igualdad del puntero, luego la igualdad de clase y, finalmente, compara los objetos utilizando isEqualToWidget: que solo verifica el name y data propiedades de los data . Lo que el ejemplo no muestra es cómo anular el hash .

Supongamos que hay otras propiedades que no afectan la igualdad, digamos la age . ¿No debería hash método hash para que solo el name y los data afecten al hash? Y si es así, ¿cómo harías eso? ¿Simplemente añadir los hashes de name y data ? Por ejemplo:

- (NSUInteger)hash {
    NSUInteger hash = 0;
    hash += [[self name] hash];
    hash += [[self data] hash];
    return hash;
}

¿Es eso suficiente? ¿Hay una técnica mejor? ¿Qué pasa si tienes primitivos, como int ? ¿Convertirlos a NSNumber para obtener su hash? ¿O estructuras como NSRect ?

( Pedo cerebral : originalmente escribió "bitwise OR" para ellos junto con |= . Significado agregar).

Answer 1

Un XOR simple sobre los valores hash de propiedades críticas es suficiente el 99% del tiempo.

Por ejemplo:

if (![(id)[self name] isEqual:[aWidget name]])
    return NO;

Solución encontrada en http://nshipster.com/equality/ por Mattt Thompson (¡que también hizo referencia a esta pregunta en su publicación!)

Answer 2

¡Esto me ayudó mucho! Podría ser la respuesta que buscas. Implementando la igualdad y el hashing.

Answer 3

Combinando la respuesta de @ tcurdt con la respuesta de @ oscar-gomez para obtener nombres de propiedades , podemos crear una solución de fácil acceso tanto para isEqual como para hash:

NSArray *PropertyNamesFromObject(id object)
{
    unsigned int propertyCount = 0;
    objc_property_t * properties = class_copyPropertyList([object class], &propertyCount);
    NSMutableArray *propertyNames = [NSMutableArray arrayWithCapacity:propertyCount];

    for (unsigned int i = 0; i < propertyCount; ++i) {
        objc_property_t property = properties[i];
        const char * name = property_getName(property);
        NSString *propertyName = [NSString stringWithUTF8String:name];
        [propertyNames addObject:propertyName];
    }
    free(properties);
    return propertyNames;
}

BOOL IsEqualObjects(id object1, id object2)
{
    if (object1 == object2)
        return YES;
    if (!object1 || ![object2 isKindOfClass:[object1 class]])
        return NO;

    NSArray *propertyNames = PropertyNamesFromObject(object1);
    for (NSString *propertyName in propertyNames) {
        if (([object1 valueForKey:propertyName] != [object2 valueForKey:propertyName])
            && (![[object1 valueForKey:propertyName] isEqual:[object2 valueForKey:propertyName]])) return NO;
    }

    return YES;
}

NSUInteger MagicHash(id object)
{
    NSUInteger prime = 31;
    NSUInteger result = 1;

    NSArray *propertyNames = PropertyNamesFromObject(object);

    for (NSString *propertyName in propertyNames) {
        id value = [object valueForKey:propertyName];
        result = prime * result + [value hash];
    }

    return result;
}

Ahora, en tu clase personalizada puedes implementar fácilmente isEqual: y hash :

- (NSUInteger)hash
{
    return MagicHash(self);
}

- (BOOL)isEqual:(id)other
{
    return IsEqualObjects(self, other);
}

Answer 4

Disculpe si me arriesgo a emitir un boffin completo aquí, pero ... ... nadie se molestó en mencionar que para seguir las "mejores prácticas" definitivamente no debe especificar un método igual que NO tenga en cuenta todos los datos que posee su objeto objetivo, por ejemplo, lo que sea. los datos se agregan a su objeto, en lugar de un asociado de él, deben tenerse en cuenta al implementar iguales. Si no quiere tomarlo en cuenta, diga ''age'' en una comparación, entonces debe escribir un comparador y usarlo para realizar sus comparaciones en lugar de isEqual :.

Si define un método isEqual: que realiza una comparación de igualdad de manera arbitraria, corre el riesgo de que otro desarrollador, o incluso usted mismo, utilice incorrectamente este método una vez que haya olvidado el "giro" en su interpretación de iguales.

Ergo, aunque esta es una excelente pregunta y respuesta sobre el hash, normalmente no es necesario que redefinamos el método de hashing, probablemente debería definir un comparador ad-hoc.

Answer 5

Empezar con

 NSUInteger prime = 31;
 NSUInteger result = 1;

Entonces por cada primitivo que hagas.

 result = prime * result + var

Para 64 bits también puede cambiar y xor.

 result = prime * result + (int) (var ^ (var >>> 32));

Para los objetos usas 0 para nil y de lo contrario su código hash.

 result = prime * result + [var hash];

Para los booleanos usas dos valores diferentes

 result = prime * result + (var)?1231:1237;

Explicación y Atribución

Este no es un trabajo de tcurdt, y los comentarios pedían más explicaciones, así que creo que una edición para atribución es justa.

Este algoritmo se popularizó en el libro "Java efectiva", y el capítulo relevante se puede encontrar actualmente en línea aquí . Ese libro popularizó el algoritmo, que ahora es el predeterminado en varias aplicaciones Java (incluido Eclipse). Sin embargo, se derivó de una implementación aún más antigua que se atribuye a Dan Bernstein o Chris Torek. Ese algoritmo anterior originalmente flotaba en Usenet, y cierta atribución es difícil. Por ejemplo, hay algunos comentarios interesantes en este código de Apache (búsqueda de sus nombres) que hacen referencia a la fuente original.

La conclusión es que este es un algoritmo de hashing muy antiguo y simple. No es el más eficaz, y ni siquiera se ha demostrado matemáticamente que sea un algoritmo "bueno". Pero es simple, y mucha gente lo ha usado durante mucho tiempo con buenos resultados, por lo que tiene mucho apoyo histórico.

Answer 6

Encontré este hilo extremadamente útil al proporcionar todo lo que necesitaba para obtener mis isEqual: y hash implementados con un solo retén. Al probar las variables de instancia de objeto en isEqual: el código de ejemplo usa:

if (![nil isEqual: nil])
    return NO;

Esto falló repetidamente ( es decir , devolvió NO ) sin error, cuando supe que los objetos eran idénticos en mi prueba de unidad. La razón fue que una de las variables de instancia de NSString era nula, por lo que la declaración anterior era:

[nil isEqual: nil]

y como nil responderá a cualquier método, esto es perfectamente legal pero

if ([self name] != [aWidget name] && ![(id)[self name] isEqual:[aWidget name]])
    return NO;

devuelve nil , que es NO , por lo tanto, cuando tanto el objeto como el objeto que se probó tenían un objeto nulo , se considerarían no iguales ( es decir , isEqual: devolvería NO ).

Esta solución simple fue cambiar la instrucción if a:

- (NSUInteger)hash
{
    return [self.name hash] ^ [self.data hash];
}

De esta manera, si sus direcciones son las mismas, omite la llamada al método, no importa si ambas son nulas o ambas apuntan al mismo objeto, pero si no es nula o apuntan a objetos diferentes, entonces se llama apropiadamente al comparador.

Espero que esto le salve a alguien unos minutos de rascarse la cabeza.

Answer 7

Espera, seguramente una forma mucho más fácil de hacer esto es anular primero la - (NSString )description y proporcionar una representación de cadena de tu estado de objeto (debes representar el estado completo de tu objeto en esta cadena).

Luego, simplemente proporcione la siguiente implementación de hash :

- (NSUInteger)hash {
    return [[self description] hash];
}

Esto se basa en el principio de que "si dos objetos de cadena son iguales (según lo determinado por el método isEqualToString:), deben tener el mismo valor hash".

Fuente: Referencia de la clase NSString

Answer 8

Esto no responde directamente a tu pregunta (en absoluto), pero he usado MurmurHash antes para generar hashes: murmurhash

Supongo que debería explicar por qué: murmurhash es muy rápido ...

Answer 9

He encontrado que esta página es una guía útil para anular los métodos de tipo igual y hash. Incluye un algoritmo decente para calcular códigos hash. La página está orientada hacia Java, pero es bastante fácil adaptarla a Objective-C / Cocoa.

Answer 10

La forma fácil pero ineficiente es devolver el mismo valor de -hash para cada instancia. De lo contrario, sí, debe implementar el hash basado únicamente en objetos que afectan la igualdad. Esto es complicado si usa comparaciones laxas en -isEqual: (por ejemplo, comparaciones de cadenas que no distinguen entre mayúsculas y minúsculas). Para los ints, generalmente puede usar el int, a menos que esté comparando con NSNumbers.

No utilice | =, sin embargo, se saturará. Utilice ^ = en su lugar.

Dato divertido aleatorio: [[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]] , pero [[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash] . (rdar: // 4538282, abierto desde el 05 de mayo de 2006)

Answer 11

La función hash debe crear un valor semi-único que probablemente no colisione o coincida con el valor hash de otro objeto.

Aquí está la función hash completa, que puede adaptarse a las variables de instancia de sus clases. Utiliza NSUInteger en lugar de int para la compatibilidad en aplicaciones de 64/32 bits.

Si el resultado se convierte en 0 para diferentes objetos, corre el riesgo de colisionar hashes. La acumulación de hashes puede provocar un comportamiento inesperado del programa cuando se trabaja con algunas de las clases de colección que dependen de la función de hash. Asegúrese de probar su función hash antes de usarla.

-(NSUInteger)hash {
    NSUInteger result = 1;
    NSUInteger prime = 31;
    NSUInteger yesPrime = 1231;
    NSUInteger noPrime = 1237;

    // Add any object that already has a hash function (NSString)
    result = prime * result + [self.myObject hash];

    // Add primitive variables (int)
    result = prime * result + self.primitiveVariable; 

    // Boolean values (BOOL)
    result = prime * result + self.isSelected?yesPrime:noPrime;

    return result;
}

Answer 12

Los contratos iguales y hash están bien especificados e investigados exhaustivamente en el mundo de Java (consulte la respuesta de @mipardi), pero todas las mismas consideraciones deberían aplicarse a Objective-C.

Eclipse realiza un trabajo confiable al generar estos métodos en Java, así que aquí hay un ejemplo de Eclipse portado a mano a Objective-C:

- (BOOL)isEqual:(id)object {
    if (self == object)
        return true;
    if ([self class] != [object class])
        return false;
    MyWidget *other = (MyWidget *)object;
    if (_name == nil) {
        if (other->_name != nil)
            return false;
    }
    else if (![_name isEqual:other->_name])
        return false;
    if (_data == nil) {
        if (other->_data != nil)
            return false;
    }
    else if (![_data isEqual:other->_data])
        return false;
    return true;
}

- (NSUInteger)hash {
    const NSUInteger prime = 31;
    NSUInteger result = 1;
    result = prime * result + [_name hash];
    result = prime * result + [_data hash];
    return result;
}

Y para una subclase YourWidget que agrega una propiedad serialNo :

- (BOOL)isEqual:(id)object {
    if (self == object)
        return true;
    if (![super isEqual:object])
        return false;
    if ([self class] != [object class])
        return false;
    YourWidget *other = (YourWidget *)object;
    if (_serialNo == nil) {
        if (other->_serialNo != nil)
            return false;
    }
    else if (![_serialNo isEqual:other->_serialNo])
        return false;
    return true;
}

- (NSUInteger)hash {
    const NSUInteger prime = 31;
    NSUInteger result = [super hash];
    result = prime * result + [_serialNo hash];
    return result;
}

Esta implementación evita algunos errores de subclasificación en el ejemplo isEqual: de Apple:

• La prueba de clase de Apple es other isKindOfClass:[self class] es asimétrica para dos subclases diferentes de MyWidget . La igualdad debe ser simétrica: a = b si y solo si b = a. Esto podría solucionarse fácilmente cambiando la prueba a other isKindOfClass:[MyWidget class] , entonces todas MyWidget subclases MyWidget serían mutuamente comparables.
• El uso de isKindOfClass: prueba de subclase evita que las subclases isEqual: con una prueba de igualdad refinada. Esto se debe a que la igualdad debe ser transitiva: si a = b y a = c entonces b = c. Si una instancia de MyWidget compara con dos instancias de YourWidget , entonces esas instancias de YourWidget deben compararse iguales entre sí, incluso si su número de serie es serialNo .

El segundo problema puede solucionarse considerando que los objetos son iguales si pertenecen a la misma clase, por lo tanto, la prueba [self class] != [object class] aquí. Para las clases de aplicación típicas, este parece ser el mejor enfoque.

Sin embargo, ciertamente hay casos en los que es preferible la prueba isKindOfClass: Esto es más típico de las clases de marco que de las clases de aplicación. Por ejemplo, cualquier NSString debe compararse igual a cualquier otra NSString con la misma secuencia de caracteres subyacente, independientemente de la distinción NSString / NSMutableString , y también independientemente de qué clases privadas están involucradas en el NSString clases NSString .

En tales casos, isEqual: debe tener un comportamiento bien definido y bien documentado, y debe quedar claro que las subclases no pueden invalidar esto. En Java, la restricción de "no anular" se puede aplicar marcando los métodos equals y hashcode como final , pero Objective-C no tiene equivalente.

Answer 13

Quinn se equivoca al decir que la referencia al hash de murmullo es inútil aquí. Quinn tiene razón al querer entender la teoría detrás del hash. El soplo destila mucho de esa teoría en una implementación. Vale la pena explorar cómo aplicar esa implementación a esta aplicación en particular.

Algunos de los puntos clave aquí:

La función de ejemplo de tcurdt sugiere que ''31'' es un buen multiplicador porque es primo. Hay que demostrar que ser primordial es una condición necesaria y suficiente. De hecho, 31 (y 7) probablemente no sean primos particularmente buenos porque 31 == -1% 32. Es probable que un multiplicador impar con la mitad de los bits establecidos y la mitad de los bits libres sea mejor. (La constante de multiplicación de hash de murmullo tiene esa propiedad).

Este tipo de función hash probablemente sería más fuerte si, después de multiplicar, el valor del resultado se ajustara mediante un cambio y un xor. La multiplicación tiende a producir los resultados de muchas interacciones de bits en el extremo superior del registro y los resultados de baja interacción en el extremo inferior del registro. El cambio y xor aumentan las interacciones en el extremo inferior del registro.

Establecer el resultado inicial en un valor donde aproximadamente la mitad de los bits son cero y aproximadamente la mitad de los bits, uno también podría ser útil.

Puede ser útil tener cuidado con el orden en que se combinan los elementos. Probablemente uno debería primero procesar booleanos y otros elementos donde los valores no están fuertemente distribuidos.

Puede ser útil agregar un par de etapas adicionales de aleatorización de bits al final del cálculo.

Si el hash murmur o no es realmente rápido para esta aplicación es una pregunta abierta. El hash murmur premezcla los bits de cada palabra de entrada. Se pueden procesar varias palabras de entrada en paralelo, lo que ayuda a la CPU segmentada de múltiples problemas.

Answer 14

Recuerda que solo necesitas proporcionar un hash que sea igual cuando isEqual sea ​​verdadero. Cuando isEqual es falso, el hash no tiene que ser desigual, aunque es de suponer que lo es. Por lo tanto:

Mantener hash simple. Elija una variable miembro (o algunos miembros) que sea la más distintiva.

Por ejemplo, para CLPlacemark, el nombre solo es suficiente. Sí, hay 2 o 3 marcas CLPlacemark con el mismo nombre, pero son raras. Usa ese hash.

@interface CLPlacemark (equal)
- (BOOL)isEqual:(CLPlacemark*)other;
@end

@implementation CLPlacemark (equal)

...

-(NSUInteger) hash
{
    return self.name.hash;
}


@end

Note que no me molesto en especificar la ciudad, el país, etc. El nombre es suficiente. Tal vez el nombre y CLLocation.

Hash debe ser distribuido uniformemente. Así que puedes combinar la variable de varios miembros usando el símbolo de careta ^ (signo xor)

Así que es algo como

hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash

De esa manera el hash será distribuido uniformemente.

Hash must be O(1), and not O(n)

Entonces, ¿qué hacer en la matriz?

Una vez más, simple. No tienes que hash a todos los miembros de la matriz. Suficiente para marcar el primer elemento, el último elemento, el conteo, tal vez algunos elementos intermedios, y eso es todo.

Answer 15

Solo estoy recogiendo Objective-C, por lo que no puedo hablar de ese idioma específicamente, pero en los otros idiomas que uso si dos instancias son "Igual", deben devolver el mismo hash. De lo contrario, tendrá todo. tipo de problemas al tratar de usarlos como claves en una tabla hash (o cualquier colección de tipo diccionario).

Por otro lado, si 2 instancias no son iguales, pueden o no tener el mismo hash, es mejor si no lo hacen. Esta es la diferencia entre una búsqueda O (1) en una tabla hash y una búsqueda O (N): si todos sus hashes chocan, puede encontrar que buscar en su tabla no es mejor que buscar en una lista.

En términos de mejores prácticas, su hash debería devolver una distribución aleatoria de valores para su entrada. Esto significa que, por ejemplo, si tiene un doble, pero la mayoría de sus valores tienden a agruparse entre 0 y 100, debe asegurarse de que los valores de hash devueltos por esos valores se distribuyan de manera uniforme en todo el rango de valores de valores posibles. . Esto mejorará significativamente su rendimiento.

Hay una serie de algoritmos de hash por ahí, incluyendo varios enumerados aquí. Trato de evitar la creación de nuevos algoritmos hash, ya que puede tener grandes implicaciones en el rendimiento, por lo que usar los métodos hash existentes y hacer una combinación de bits de algún tipo como lo hace en su ejemplo es una buena manera de evitarlo.

Answer 16

También soy un novato de Objective C, pero encontré un excelente artículo sobre identidad frente a igualdad en Objective C here . Desde mi lectura, parece que podría mantener la función hash predeterminada (que debería proporcionar una identidad única) e implementar el método isEqual para que compare los valores de los datos.

Answer 17

Tenga en cuenta que si está creando un objeto que se puede mutar después de la creación, el valor de hash no debe cambiar si el objeto se inserta en una colección. En la práctica, esto significa que el valor de hash debe fijarse desde el punto de creación del objeto inicial. Consulte la documentación de Apple sobre el método de hash del protocolo NSObject para obtener más información:

Si se agrega un objeto mutable a una colección que usa valores hash para determinar la posición del objeto en la colección, el valor devuelto por el método hash del objeto no debe cambiar mientras el objeto esté en la colección. Por lo tanto, el método hash no debe basarse en ninguna información interna del estado del objeto o debe asegurarse de que la información interna del estado del objeto no cambie mientras el objeto esté en la colección. Así, por ejemplo, un diccionario mutable se puede colocar en una tabla hash, pero no debe cambiarlo mientras esté allí. (Tenga en cuenta que puede ser difícil saber si un objeto dado está o no en una colección).

Esto me parece una locura completa ya que potencialmente hace que las búsquedas de hash sean mucho menos eficientes, pero supongo que es mejor errar por el lado de la precaución y seguir lo que dice la documentación.