Implementacja-hash/ - isEqual: / - isEqualTo...: dla zbiorów Objective-C

Question

Implementacja-hash/ - isEqual: / - isEqualTo...: dla zbiorów Objective-C

Uwaga: poniższe pytania są ze sobą powiązane, ale ani One, ani powiązane zasoby nie wydają się w pełni odpowiadać na moje pytania, szczególnie w odniesieniu do wdrażania testów równości dla zbiorów obiektów.

Tło

NSObject dostarcza default wdrożenia -hash (który zwraca adres instancji, np. (NSUInteger)self) i -isEqual: (która zwraca NO, chyba że adresy odbiornika i parametr są identyczne). Metody te są zaprojektowane tak, aby były zastępowane w razie potrzeby, ale dokumentacja wyjaśnia, że należy podać obie lub obie. Ponadto, jeśli -isEqual: zwraca YES dla dwóch obiektów, to wynik -hash dla tych obiektów musi być taki sam. Jeśli nie, problemy mogą wystąpić, gdy obiekty, które powinny być takie same - takie jak dwie instancje ciągu znaków, dla których -compare: zwraca NSOrderedSame - są dodawane do kolekcji Cocoa lub porównywane bezpośrednio.

Kontekst

Rozwijam Chdatastruktury.framework , otwarta biblioteka struktur danych Objective-C. Zaimplementowałem szereg kolekcji, a obecnie udoskonalam i zwiększam ich funkcjonalność. Jedną z funkcji, którą chcę dodać, jest możliwość porównywania zbiorów pod kątem równości z kolejny.

Zamiast porównywać tylko adresy pamięci, porównania te powinny uwzględniać obiekty obecne w obu kolekcjach (w tym kolejność, jeśli ma to zastosowanie). Podejście to ma dość precedensowy w Cocoa, i ogólnie używa odrębnej metody, w tym po:

Chcę, aby moje niestandardowe zbiory były odporne na testy równości, aby mogły być bezpiecznie (i przewidywalnie) dodawane do innych zbiorów i pozwalały innym (jak NSSet) określić, czy dwa zbiory są równe/równoważne / duplikaty.

Problemy

Metoda -isEqualTo...: działa świetnie sama w sobie, ale klasy definiujące te metody zwykle zastępują -isEqual:, aby wywołać [self isEqualTo...:], Jeśli parametr należy do tej samej klasy (lub być może podklasy) co odbiornik, lub [super isEqual:] w przeciwnym razie. Oznacza to, że klasa musi również zdefiniować -hash w taki sposób, że zwróci tę samą wartość dla różnych instancji, które mają tę samą zawartość.

Ponadto dokumentacja Apple dla -hash określa following: (emphasis mine)

"jeśli zmienny obiekt zostanie dodany do kolekcji, która używa wartości skrótu do określenia pozycji obiektu w kolekcji, wartość zwracana przez metodę hash obiektu nie może się zmieniać, gdy obiekt znajduje się w kolekcji. Dlatego albo metoda hash nie może polegać na żadnej z wewnętrznych informacji o stanie obiektu lub musisz upewnić się, że wewnętrzne informacje o stanie obiektu Nie ulegną zmianie, podczas gdy obiekt znajduje się w kolekcji. Tak więc, na przykład, zmienny słownik można umieścić w tabeli hash, ale nie wolno go zmieniać, gdy jest tam. (Zauważ, że może być trudno wiedzieć, czy dany obiekt znajduje się w kolekcji.)"

Edytuj: zdecydowanie rozumiem, dlaczego jest to konieczne i całkowicie zgadzam się z rozumowaniem - wspomniałem o tym tutaj, aby podać dodatkowy kontekst, i pominąłem temat, dlaczego tak jest ze względu na zwięzłość.

Wszystkie moje kolekcje są mutowalne, a hash będzie musiał wziąć pod uwagę przynajmniej niektóre zawartości, więc jedyną opcją tutaj jest uznanie za błąd programowania, aby zmutować kolekcję przechowywaną w innej kolekcji. (Wszystkie moje Kolekcje przyjmują NSCopying , więc kolekcje takie jak NSDictionary mogą z powodzeniem wykonać kopię, aby użyć jej jako klucza itp.)

Sensowne jest dla mnie zaimplementowanie -isEqual: i -hash, ponieważ (na przykład) pośredni użytkownik jedna z moich klas może nie znać konkretnej metody wywołania -isEqualTo...:, a nawet nie dbać o to, czy dwa obiekty są instancjami tej samej klasy. Powinny one być w stanie wywołać -isEqual: lub -hash Na dowolnej zmiennej typu id i uzyskać oczekiwany wynik.

W przeciwieństwie do -isEqual: (która ma dostęp do dwóch porównywanych instancji), -hash musi zwracać wynik "na ślepo", z dostępem tylko do danych w danej instancji. ponieważ nie może wiedzieć, do czego jest używany hash, wynik musi być spójny dla wszystkich możliwych przypadków, które powinny być uważane za równe/identyczne i muszą zawsze zgadzać się z -isEqual:. (Edit: to zostało obalone przez Odpowiedzi poniżej, a to z pewnością ułatwia życie.) ponadto pisanie dobrych funkcji hashowych jest nietrywialne-zagwarantowanie wyjątkowości jest wyzwaniem, zwłaszcza gdy masz tylko NSUInteger (32/64 bity), w którym można ją reprezentować.

Pytania

czy istnieją najlepsze praktyki przy wdrażaniu ~~porównania równości~~ -hash do kolekcji?
czy w kolekcjach Objective-C i Cocoa-esque można zaplanować jakieś osobliwości?
czy są jakieś dobre podejścia do testów jednostkowych -hash z rozsądnym stopniem zaufania?
jakieś sugestie dotyczące implementacji -hash do -isEqual: dla zbiorów zawierających elementy dowolnych typów? O jakich pułapkach powinienem wiedzieć? (Edit: nie tak problematyczne jak myślałem - jak @kperryua wskazuje, " równe -hash wartości nie nie implikują -isEqual:".)

Edytuj: powinienem był wyjaśnić, że nie jestem zdezorientowany, jak zaimplementować-isEqual: or-isEqualTo...: dla kolekcji, to proste. Myślę, że moje nieporozumienie wynikło głównie z (omyłkowego) myślenia, że -hash musi zwrócić inną wartość, jeśli-isEqual: zwraca NO. Wykonując kryptografię w przeszłości, myślałem, że hashe dla różnych wartości muszą bądź inny. Jednak poniższe odpowiedzi uświadomiły mi, że "dobra" funkcja haszująca polega na minimalizowaniu kolizji kubełka i łańcuchowaniu zbiorów, które używają -hash. Chociaż unikalne skróty są preferowane, nie są one ścisłym wymogiem.

46

equality objective-c cocoa data-structures chdatastructures

Author: Quinn Taylor, 2009-07-11

Source

3 answers

Dwa zbiory powinny być uważane za równe, jeśli zawierają te same elementy, a ponadto, jeśli zbiory są uporządkowane, że elementy są w tej samej kolejności.

W temacie hashów dla kolekcji, powinno wystarczyć łączenie hashów elementów w jakiś sposób (XOR them lub modulo add them). Zauważ, że podczas gdy reguły mówią, że dwa obiekty, które są równe zgodnie z IsEqual, muszą zwrócić ten sam hash , przeciwieństwo nie posiada: chociaż unikalność hashów jest pożądane, nie jest konieczne dla poprawności rozwiązania. Tak więc uporządkowany zbiór nie musi uwzględniać kolejności elementów.

Fragment dokumentacji Apple jest niezbędnym ograniczeniem przy okazji. Obiekt nie może utrzymać tej samej wartości hash podczas mutacji, jednocześnie zapewniając, że obiekty o tej samej wartości mają ten sam hash. Dotyczy to zarówno najprostszych obiektów, jak i kolekcji. Oczywiście liczy się tylko to, że hash obiektu zmienia się, gdy jest on wewnątrz kontenera, który używa hasha do porządkowania jego elementów. Rezultatem tego wszystkiego jest to, że Kolekcje mutowalne nie powinny mutować się, gdy są umieszczone w innym kontenerze, ale również żaden obiekt, który ma prawdziwą funkcję hashową.

4

Author: U62,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-07-11 00:26:56

Zrobiłem jakieś dochodzenie w nsArray i nsmutablearray domyślnej implementacji hash i (chyba, że coś źle zrozumiałam) szwy jak Apple nie przestrzegać własnych zasad:

Jeśli zmienny obiekt jest dodawany do kolekcji, która używa wartości hash do określić pozycję obiektu w zbiorze, zwracana wartość przy pomocy metody hash obiektu nie może się zmieniać, gdy obiekt jest w kolekcji. Dlatego też metoda hash nie może polegać on którejkolwiek z wewnętrznych informacji o stanie obiektu lub musisz upewnić się wewnętrzna informacja o stanie obiektu nie zmienia się podczas obiekt znajduje się w kolekcji. Tak więc np. słownik zmienny można umieścić w tabeli hash, ale nie wolno go zmieniać, gdy jest w tam. (Zauważ, że może być trudno wiedzieć, czy dany obiekt znajduje się w kolekcji.)

Oto Mój kod testowy

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

Wyjście To:

Hash Before: 3
Hash After : 2

Więc szwy jak Domyślna implementacja metody Hash zarówno w NSArray jak i NSMutableArray jest licznikiem tablicy i nie ma znaczenia, czy jest ona wewnątrz kolekcji, czy nie.

3

Author: Robert,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-07-10 09:53:03

score 18 · Accepted Answer

Myślę, że próba wymyślenia jakiejś ogólnie użytecznej funkcji skrótu, która wygeneruje unikalne wartości skrótu dla kolekcji, jest ćwiczeniem bezcelowym. Sugestia U62 dotycząca łączenia skrótów całej zawartości nie będzie dobrze skalowana, ponieważ sprawia, że funkcja skrótu O (n). Funkcje skrótu powinny być O (1), aby zapewnić dobrą wydajność, w przeciwnym razie cel skrótu zostanie pokonany. (Rozważ powszechną konstrukcję PLIST, które są słownikami zawierającymi tablice i inne słowniki, potencjalnie ad nauseum. Próba wzięcia hasha ze słownika najwyższego poziomu dużego plista byłaby potwornie powolna, gdyby funkcje hashowe zbiorów były O (n).)

Moją sugestią byłoby nie martwić się zbytnio o hash kolekcji. Jak już stwierdziłeś, -isEqual: implikuje równe -hash wartości. Z drugiej strony, równe -hash wartości nie implikują-isEqual:. Ten fakt daje dużo swobody, aby stworzyć prosty hash.

Jeśli naprawdę się martwisz jeśli chodzi o kolizje (i masz dowód w konkretnych pomiarach rzeczywistych sytuacji, które potwierdzają, że jest to coś, o co się martwić), nadal możesz w pewnym stopniu zastosować się do rad U62. Na przykład, możesz wziąć hash, powiedzmy, pierwszego i/lub ostatniego elementu w kolekcji i połączyć go z, powiedzmy, -count kolekcji. To wystarczy, aby zapewnić przyzwoity hash.

Mam nadzieję, że to odpowie na chociaż jedno z twoich pytań.

Co do nr 1: Implementacja -isEqual: jest dość ucięta i sucha. Wymieniasz zawartość i sprawdzasz isEqual: na każdym z elementów.

Jest jedna rzecz, na którą należy uważać, która może mieć wpływ na to, co zdecydujesz się zrobić dla funkcji -hash kolekcji. Klienci Twoich kolekcji muszą również rozumieć zasady rządzące -isEqual: i -hash. Jeśli użyjesz zawartości "-hash w swojej kolekcji -hash, twoja kolekcja pęknie, jeśli zawartość " isEqual: i -hash się nie zgodzą. To oczywiście wina klienta, ale to kolejny argument przeciwko oparciu -hash na zawartości kolekcji.

Nr 2 jest trochę niejasny. Nie wiem, co masz na myśli.