objective c - Implementando-hash/-isEqual:/-isEqualTo...: para colecciones Objective-C

cocoa data-structures

Question

Nota: Las siguientes preguntas SO están relacionadas, pero ni ellos ni los recursos vinculados parecen responder completamente mis preguntas, particularmente en relación con la implementación de pruebas de igualdad para colecciones de objetos .

• Mejores prácticas para anular -isEqual: y -hash
• Técnicas para implementar -hash en objetos de cacao mutables

Fondo

NSObject proporciona implementaciones predeterminadas de -hash (que devuelve la dirección de la instancia, como (NSUInteger)self ) y -isEqual: (que devuelve NO menos que las direcciones del receptor y el parámetro sean idénticas). Estos métodos están diseñados para anularse según sea necesario, pero la documentación deja en claro que debe proporcionar ambos o ninguno. Además, si -isEqual: devuelve YES para dos objetos, entonces el resultado de -hash para esos objetos debe ser el mismo. De lo contrario, pueden surgir problemas cuando los objetos deben ser iguales, como dos instancias de cadena para las cuales -compare: returns NSOrderedSame se agregan a una colección Cocoa o se comparan directamente.

Contexto

Desarrollo CHDataStructures.framework , una biblioteca de código abierto de estructuras de datos Objective-C. Implementé varias colecciones y actualmente estoy perfeccionando y mejorando su funcionalidad. Una de las características que quiero agregar es la capacidad de comparar colecciones para la igualdad con otro.

En lugar de comparar solo direcciones de memoria, estas comparaciones deben considerar los objetos presentes en las dos colecciones (incluido el orden, si corresponde). Este enfoque tiene un gran precedente en Cocoa, y generalmente utiliza un método diferente, que incluye lo siguiente:

• -[NSArray isEqualToArray:]
• -[NSDate isEqualToDate:]
• -[NSDictionary isEqualToDictionary:]
• -[NSNumber isEqualToNumber:]
• -[NSSet isEqualToSet:]
• -[NSString isEqualToString:]
• -[NSValue isEqualToValue:]

Quiero que mis colecciones personalizadas sean robustas para las pruebas de igualdad, por lo que se pueden agregar de manera segura (y predecible) a otras colecciones, y permitir que otras (como un NSSet) determinen si dos colecciones son iguales / equivalentes / duplicadas.

Problemas

Un método -isEqualTo...: funciona muy bien por sí mismo, pero las clases que definen estos métodos generalmente también anulan -isEqual: para invocar [self isEqualTo...:] si el parámetro es de la misma clase (o tal vez subclase) que el receptor, o [super isEqual:] contrario. Esto significa que la clase también debe definir -hash manera que devuelva el mismo valor para las instancias dispares que tienen el mismo contenido.

Además, la documentación de Apple para -hash estipula lo siguiente: (énfasis mío)

"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 confiar en ninguna información de estado interno del objeto o debe asegurarse de que la información de estado interno del objeto no cambie mientras el objeto está en la colección. Así, por ejemplo, un diccionario mutable puede colocarse en una tabla hash pero debe no lo cambie mientras esté allí. (Tenga en cuenta que puede ser difícil saber si un objeto dado está o no en una colección).

Editar: definitivamente entiendo por qué esto es necesario y estoy totalmente de acuerdo con el razonamiento; lo mencioné aquí para proporcionar un contexto adicional, y eludí el tema de por qué es el caso en aras de la brevedad.

Todas mis colecciones son mutables, y el hash tendrá que considerar al menos algunos de los contenidos, por lo que la única opción aquí es considerarlo un error de programación para mutar una colección almacenada en otra colección. (Todas mis colecciones adoptan NSCopying , por lo que las colecciones como NSDictionary pueden hacer una copia para utilizarla como clave, etc.).

Tiene sentido para mí implementar -isEqual: y -hash , ya que (por ejemplo) un usuario indirecto de una de mis clases puede no conocer el -isEqualTo...: específico -isEqualTo...: para llamar, o incluso importar si dos objetos son instancias de la misma clase. Deberían poder llamar -isEqual: o -hash en cualquier variable de tipo id y obtener el resultado esperado.

A diferencia de -isEqual: (que tiene acceso a dos instancias que se comparan), -hash debe devolver un resultado "a ciegas", con acceso solo a los datos dentro de una instancia particular. Como no puede saber para qué se utiliza el hash, el resultado debe ser coherente para todas las instancias posibles que se deben considerar iguales / idénticas, y siempre debe estar de acuerdo con -isEqual: (Editar: Esto ha sido desacreditado por las respuestas a continuación, y ciertamente hace la vida más fácil.) Además, escribir buenas funciones hash no es trivial, garantizar la singularidad es un desafío, especialmente cuando solo tienes un NSUInteger (32/64 bits) para representarlo

Preguntas

1. ¿Existen mejores prácticas al implementar comparaciones de igualdad, -hash a las colecciones?
2. ¿Hay alguna peculiaridad para planear en las colecciones Objective-C y Cocoa-esque?
3. ¿Hay algún buen enfoque para las pruebas -hash con un grado razonable de confianza?
4. ¿Alguna sugerencia sobre la implementación -hash para estar de acuerdo con -isEqual: para colecciones que contienen elementos de tipos arbitrarios? ¿Qué peligros debería saber? ( Editar: No es tan problemático como pensé por primera vez, como señala @kperryua , "los valores de igual valor no implican -isEqual: ".)

Editar: Debería haber aclarado que no estoy confundido acerca de cómo implementar -isEqual: o -isEqualTo ...: para las colecciones, eso es sencillo. Creo que mi confusión se debió principalmente a (erróneamente) pensar que -shsh DEBE devolver un valor diferente si -isEqual: devuelve NO. Habiendo hecho criptografía en el pasado, estaba pensando que los valores hash para diferentes valores DEBEN ser diferentes. Sin embargo, las respuestas a continuación me hicieron darme cuenta de que una función de hash "buena" se trata realmente de minimizar las colisiones de cubos y encadenar las colecciones que usan -hash . Si bien los hashes únicos son preferibles, no son un requisito estricto.

Answer 1

Creo que tratar de encontrar una función hash generalmente útil que genere valores hash únicos para colecciones es un ejercicio inútil. La sugerencia de U62 de combinar los hash de todos los contenidos no se escalará bien, ya que hace que la función hash O (n). Las funciones hash realmente deberían ser O (1) para asegurar un buen rendimiento, de lo contrario, el propósito del hash es derrotado. (Considere la construcción común de Cocoa de plists, que son diccionarios que contienen matrices y otros diccionarios, potencialmente ad nauseum. Intentar tomar el hash del diccionario de alto nivel de un plist grande sería terriblemente lento si las funciones hash de las colecciones fueran O ( norte).)

Mi sugerencia sería no preocuparse demasiado por el hash de una colección. Como dijiste, -isEqual: implica valores iguales -hash . Por otro lado, los valores de igual valor no implican -isEqual: Este hecho te da mucha libertad de acción para crear un hash simple.

Sin embargo, si estás realmente preocupado por las colisiones (y tienes pruebas en medidas concretas de situaciones del mundo real que confirman que es algo de lo que temer), aún podrías seguir el consejo de U62 hasta cierto punto. Por ejemplo, puede tomar el hash de, por ejemplo, el primer y / o último elemento de la colección y combinarlo con, por ejemplo, la -count de la colección. Eso será suficiente para proporcionar un hash decente.

Espero que responda al menos una de tus preguntas.

En cuanto al No. 1: Implementando -isEqual: es bastante cortante y seco. Usted enumera los contenidos y marca isEqual: en cada uno de los elementos.

Hay una cosa a tener en cuenta que puede afectar lo que decida hacer para las funciones de sus colecciones. Los clientes de sus colecciones también deben comprender las reglas que rigen -isEqual: y -hash . Si utiliza los contenidos '' -hash de su colección, su colección se romperá si el contenido'' es isEqual: y -hash no concuerdan. Es culpa del cliente, por supuesto, pero ese es otro argumento en contra de basar su -hash fuera del contenido de la colección.

No. 2 es un poco vago. No estoy seguro de lo que tienes en mente allí.

Answer 2

Dos colecciones deben considerarse iguales si contienen los mismos elementos y, además, si las colecciones están ordenadas, los elementos están en el mismo orden.

En el tema de los hash para las colecciones, debería ser suficiente combinar los hash de los elementos de alguna manera (XOR ellos o módulo agregarlos). Tenga en cuenta que si bien las reglas establecen que dos objetos que son iguales según IsEqual necesitan devolver el mismo hash, no sucede lo contrario: aunque la singularidad de los hashes es deseable, no es necesario para la corrección de la solución. Por lo tanto, una colección ordenada no necesita tener en cuenta el orden de los elementos.

El extracto de la documentación de Apple es una restricción necesaria por cierto. Un objeto no puede mantener el mismo valor de hash bajo mutación al tiempo que garantiza que los objetos con el mismo valor tengan el mismo hash. Eso se aplica para el más simple de los objetos, así como colecciones. Por supuesto, normalmente solo importa que el hash de un objeto cambie cuando está dentro de un contenedor que usa el hash para organizar sus elementos. El resultado de todo esto es que las colecciones mutables no deben mutar cuando se colocan dentro de otro contenedor, pero tampoco debe hacerlo ningún objeto que tenga una verdadera función hash.

Answer 3

He investigado un poco sobre la implementación de hash predeterminada de NSArray y NSMutableArray y (a menos que haya entendido mal algo) parece que Apple no sigue sus propias reglas:

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 de estado interno del objeto o debe asegurarse de que la información de estado interno del objeto no cambie mientras el objeto está en la colección. Por lo tanto, por ejemplo, un diccionario mutable puede colocarse 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).

Aquí está mi código de prueba

NSMutableArray* myMutableArray = [NSMutableArray arrayWithObjects:@"a", @"b", @"c", nil];
NSMutableArray* containerForMutableArray = [NSMutableArray arrayWithObject:myMutableArray];
NSUInteger hashBeforeMutation = [[containerForMutableArray objectAtIndex:0] hash];
[[containerForMutableArray objectAtIndex:0] removeObjectAtIndex:1];
NSUInteger hashAfterMutation = [[containerForMutableArray objectAtIndex:0] hash];
NSLog(@"Hash Before: %d", hashBeforeMutation);
NSLog(@"Hash After : %d", hashAfterMutation);

El resultado es:

Hash Before: 3
Hash After : 2

Por lo tanto, parece que la implementación predeterminada para el método Hash en NSArray y NSMutableArray es el recuento de la matriz y no le importa si está dentro de una colección o no.