Implementazione -hash / -isEqual: / -isEqualTo …: per le raccolte Objective-C

Nota: le seguenti domande su SO sono correlate, ma né loro né le risorse collegate sembrano rispondere pienamente alle mie domande, in particolare in relazione all’implementazione di test di uguaglianza per raccolte di oggetti .

  • Best practice per l’override -isEqual: e -hash
  • Tecniche per implementare -hash su oggetti mutevoli di cocoa

sfondo

NSObject fornisce implementazioni predefinite di -hash (che restituisce l’indirizzo dell’istanza, come (NSUInteger)self ) e -isEqual: (che restituisce NO meno che gli indirizzi del ricevitore e il parametro siano identici). Questi metodi sono progettati per essere sovrascritti secondo necessità, ma la documentazione chiarisce che è necessario fornire entrambi o nessuno dei due. Inoltre, se -isEqual: restituisce YES per due oggetti, quindi il risultato di -hash per quegli oggetti deve essere lo stesso. In caso contrario, possono verificarsi problemi quando gli oggetti devono essere uguali, ad esempio due istanze di stringa per cui -compare: restituisce NSOrderedSame – vengono aggiunti a una raccolta Cocoa o confrontati direttamente.

Contesto

Sviluppo CHDataStructures.framework , una libreria open-source di strutture dati Objective-C. Ho implementato una serie di raccolte e attualmente sto perfezionando e migliorando le loro funzionalità. Una delle funzionalità che voglio aggiungere è la possibilità di confrontare le raccolte per l’uguaglianza con un’altra.

Piuttosto che confrontare solo gli indirizzi di memoria, questi confronti dovrebbero considerare gli oggetti presenti nelle due raccolte (incluso l’ordine, se applicabile). Questo approccio ha un precedente in Cocoa e generalmente utilizza un metodo separato, tra cui:

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

Voglio rendere le mie raccolte personalizzate solide ai test di uguaglianza, in modo che possano essere aggiunte (e prevedibilmente) in modo sicuro ad altre raccolte e consentire ad altri (come un NSSet) di determinare se due collezioni sono uguali / equivalenti / duplicati.

    I problemi

    An -isEqualTo...: metodo funziona alla grande da solo, ma le classi che definiscono questi metodi di solito sovrascrivono -isEqual: per invocare [self isEqualTo...:] se il parametro è della stessa class (o forse sottoclass) come il ricevitore, o [super isEqual:] altrimenti. Ciò significa che la class deve anche definire -hash tale che restituisca lo stesso valore per istanze disparate che hanno lo stesso contenuto.

    Inoltre, la documentazione di Apple per -hash stabilisce quanto segue: (sottolineatura mia)

    “Se un object mutevole viene aggiunto a una raccolta che utilizza valori hash per determinare la posizione dell’object nella raccolta, il valore restituito dal metodo hash dell’object non deve cambiare mentre l’object si trova nella raccolta. Pertanto, il metodo hash non deve fare affidamento su nessuna delle informazioni di stato interne dell’object o è necessario assicurarsi che le informazioni sullo stato interno dell’object non cambino mentre l’object si trova nella raccolta, ad esempio un dizionario mutabile può essere inserito in una tabella hash ma è necessario non cambiarlo mentre è lì dentro. (Si noti che può essere difficile sapere se un dato object si trova o meno in una collezione). “

    Edit: Capisco perfettamente il motivo per cui è necessario e totalmente d’accordo con il ragionamento – ho menzionato qui per fornire un contesto aggiuntivo e ho discusso il motivo del perché è il caso per brevità.

    Tutte le mie raccolte sono mutabili e l’hash dovrà considerare almeno alcuni dei contenuti, quindi l’unica opzione qui è considerarla un errore di programmazione per mutare una raccolta memorizzata in un’altra raccolta. (Le mie collezioni adottano NSCopying , quindi le raccolte come NSDictionary possono fare una copia da usare come chiave, ecc.)

    Per me è -isEqual: implementare -isEqual: e -hash , poiché (per esempio) un utente indiretto di una delle mie classi potrebbe non conoscere lo specifico -isEqualTo...: metodo da chiamare, o anche preoccuparsi se due oggetti sono istanze della stessa class Dovrebbero essere in grado di chiamare -isEqual: o -hash su qualsiasi variabile di id di tipo e ottenere il risultato previsto.

    A differenza di -isEqual: (che ha accesso a due istanze confrontate), -hash deve restituire un risultato “cieco”, con accesso solo ai dati all’interno di una particolare istanza. Dal momento che non può sapere per cosa viene usato l’hash, il risultato deve essere coerente per tutte le possibili istanze che dovrebbero essere considerate uguali / identiche e deve sempre concordare con -isEqual: (Modifica: Questo è stato sfatato dalle risposte sottostanti, e certamente rende la vita più facile.) Inoltre, scrivere buone funzioni di hash non è banale – garantire l’unicità è una sfida, specialmente quando si ha solo un NSUInteger (32/64 bit) in cui rappresentarlo.

    Domande

    1. Ci sono buone pratiche quando si implementano confronti di uguaglianza -hash per le collezioni?
    2. Ci sono delle peculiarità da pianificare nelle collezioni Objective-C e Cocoa-esque?
    3. Ci sono dei buoni approcci per i test unitari -hash con un ragionevole grado di sicurezza?
    4. Qualche suggerimento sull’implementazione -hash per concordare con -isEqual: per le raccolte contenenti elementi di tipi arbitrari? Quali trappole dovrei sapere? ( Modifica: non è così problematico come pensavo – come sottolinea @kperryua , “i valori di uguale -hash non implicano -isEqual: “).

    Edit: Avrei dovuto chiarire che non sono confuso su come implementare -isEqual: o -isEqualTo …: per le raccolte, è semplice. Penso che la mia confusione derivasse principalmente dal pensare (erroneamente) che -hash DEVE restituire un valore diverso se -isEqual: restituisce NO. Avendo fatto la crittografia in passato, stavo pensando che gli hash per valori diversi DEVONO essere diversi. Tuttavia, le risposte sottostanti mi hanno fatto capire che una “buona” funzione di hash consiste proprio nel minimizzare le collisioni con le benne e il concatenamento per le raccolte che usano -hash . Mentre gli hash unici sono preferibili, non sono un requisito rigoroso.

    Penso che provare a trovare qualche funzione di hash generalmente utile che genererà valori hash univoci per le raccolte è un esercizio inutile. Il suggerimento di U62 di combinare gli hash di tutti i contenuti non si ridimensionerà bene, poiché rende la funzione di hash O (n). Le funzioni di hash dovrebbero essere effettivamente O (1) per assicurare una buona prestazione, altrimenti lo scopo dell’hash sarà sconfitto. (Si consideri il comune costrutto di plists di Cocoa, che sono dizionari contenenti matrici e altri dizionari, potenzialmente fino alla nausea. Il tentativo di prendere l’hash del dizionario di livello superiore di un plist di grandi dimensioni sarebbe terribilmente lento se le funzioni di hash delle raccolte fossero O ( n).)

    Il mio suggerimento non sarebbe di preoccuparsi molto dell’hash di una collezione. Come hai affermato, -isEqual: implica valori pari -hash . D’altra parte, i valori di uguale -hash non implicano -isEqual: Questo fatto ti dà un sacco di margine per creare un semplice hash.

    Se sei davvero preoccupato per le collisioni (e hai prove concrete di situazioni reali che confermano che è qualcosa di cui preoccuparsi), potresti comunque seguire il consiglio di U62 in una certa misura. Ad esempio, puoi prendere l’hash di, ad esempio, il primo e / o l’ultimo elemento della raccolta e combinarlo con, ad esempio, il -count della raccolta. Questo è sufficiente per fornire un hash decente.

    Spero che risponda ad almeno una delle tue domande.

    Per quanto riguarda No. 1: Implementare -isEqual: è abbastanza tagliato e asciutto. Enumerare il contenuto e controllare isEqual: su ciascuno degli elementi.

    C’è una cosa a cui prestare attenzione che potrebbe influire su ciò che decidi di fare per le funzioni -hash tue raccolte. I clienti delle tue raccolte devono anche comprendere le regole che governano -isEqual: e -hash . Se si utilizza il contenuto ‘ -hash nella raccolta -hash , la raccolta si interromperà se il contenuto’ isEqual: e -hash non è d’accordo. È colpa del cliente, naturalmente, ma questo è un altro argomento contro il basare il tuo -hash sui contenuti della collezione.

    Il n. 2 è un po ‘vago. Non sono sicuro di quello che hai in mente lì.

    Due raccolte devono essere considerate uguali se contengono gli stessi elementi e, inoltre, se le raccolte sono ordinate, gli elementi sono nello stesso ordine.

    A proposito di hash per le collezioni, dovrebbe essere sufficiente combinare gli hash degli elementi in qualche modo (XOR o modulo aggiungerli). Nota che mentre le regole stabiliscono che due oggetti uguali secondo IsEqual devono restituire lo stesso hash, l’opposto non vale: sebbene l’unicità degli hash sia desiderabile, non è necessaria per la correttezza della soluzione. Quindi una raccolta ordinata non deve prendere in considerazione l’ordine degli elementi.

    L’estratto dalla documentazione di Apple è una restrizione necessaria a proposito. Un object non è in grado di mantenere lo stesso valore di hash sotto la mutazione, garantendo allo stesso tempo che gli oggetti con lo stesso valore abbiano lo stesso hash. Questo vale sia per gli oggetti più semplici che per le collezioni. Naturalmente di solito importa solo che l’hash di un object cambi quando è all’interno di un contenitore che usa l’hash per organizzare i suoi elementi. Il risultato di tutto ciò è che le raccolte mutabili non devono mutare se collocate all’interno di un altro contenitore, ma in tal caso nessuno dovrebbe avere una vera funzione hash.

    Ho svolto alcune indagini sull’implementazione hash predefinita di NSArray e NSMutableArray e (a meno che non abbia frainteso qualcosa) sembra che Apple non segua le proprie regole:

    Se un object mutabile viene aggiunto a una raccolta che utilizza valori hash per determinare la posizione dell’object nella raccolta, il valore restituito dal metodo hash dell’object non deve cambiare mentre l’object si trova nella raccolta. Pertanto, il metodo hash non deve fare affidamento su nessuna delle informazioni sullo stato interno dell’object oppure è necessario assicurarsi che le informazioni sullo stato interno dell’object non cambino mentre l’object si trova nella raccolta. Ad esempio, un dizionario mutabile può essere inserito in una tabella hash ma non è necessario cambiarlo mentre è lì dentro. (Si noti che può essere difficile sapere se un determinato object si trova o meno in una raccolta).

    Ecco il mio codice di prova

     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); 

    L’output è:

     Hash Before: 3 Hash After : 2 

    Quindi sembra che l’implementazione predefinita per il metodo Hash su NSArray e NSMutableArray sia il conteggio dell’array e non importa se è all’interno di una raccolta o meno.