Najlepsze praktyki zastępowania to: Równe: i mieszające

267

Jak poprawnie przesłonić isEqual:cel C? „Złap” wydaje się polegać na tym, że jeśli dwa obiekty są równe (jak określa isEqual:metoda), muszą mieć tę samą wartość skrótu.

Introspekcja odcinek kakao Fundamentals Przewodnik ma przykład, w jaki sposób zastąpić isEqual:, kopiowane następująco, dla klasy o nazwie 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;
}

Sprawdza równość wskaźnika, następnie równość klas, a na koniec porównuje obiekty isEqualToWidget:, które tylko sprawdzają właściwości namei data. W tym przykładzie nie pokazano, jak zastąpić hash.

Załóżmy, że istnieją inne właściwości, które nie wpływają na równość, powiedzmy age. Nie powinien hashmetoda być przesłonięte tak, że tylko namei datawpływać na hash? A jeśli tak, to jak byś to zrobił? Po prostu dodaj skróty namei data? Na przykład:

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

Czy to wystarczy? Czy istnieje lepsza technika? Co jeśli masz prymitywy int? Konwertuj je, aby NSNumberuzyskać skrót? Lub struktury takie jak NSRect?

( Brain fart : Oryginalnie napisałem je „bitowe LUB” razem z nimi |=. Znacząco dodaj.)

Dave Dribin
źródło
2
if (![other isKindOfClass:[self class]])- Technicznie oznacza to, że równość nie będzie przemienna. Tj. A = B nie oznacza B = A (np. Jeśli jedna jest podklasą drugiej)
Robert
Link do dokumentacji nie działa, teraz zarchiwizowany w introspekcji
jedwidz

Odpowiedzi:

111

Zacząć od

 NSUInteger prime = 31;
 NSUInteger result = 1;

Następnie dla każdego prymitywnego robicie

 result = prime * result + var

Dla obiektów używasz 0 dla zera, a poza tym ich hashcode.

 result = prime * result + [var hash];

Dla wartości logicznych używasz dwóch różnych wartości

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

Wyjaśnienie i przypisanie

To nie jest praca tcurdta, a komentarze prosiły o więcej wyjaśnień, więc uważam, że zmiana atrybucji jest uczciwa.

Algorytm ten został spopularyzowany w książce „Skuteczna Java”, a odpowiedni rozdział można obecnie znaleźć w Internecie tutaj . Ta książka spopularyzowała algorytm, który jest teraz domyślny w wielu aplikacjach Java (w tym w Eclipse). Wywodziło się to jednak od jeszcze starszej implementacji, którą w różny sposób przypisuje się Danowi Bernsteinowi lub Chrisowi Torek. Ten starszy algorytm pierwotnie krążył w sieci Usenet i pewne przypisanie jest trudne. Na przykład w tym kodzie Apache jest kilka interesujących komentarzy (szukaj ich nazw), które odwołują się do oryginalnego źródła.

Podsumowując, jest to bardzo stary, prosty algorytm mieszający. Nie jest najbardziej wydajny i nie udowodniono nawet matematycznie, że jest „dobrym” algorytmem. Ale to jest proste i wiele osób używało go od dawna z dobrymi wynikami, więc ma wiele historycznego wsparcia.

tcurdt
źródło
9
Skąd wziął się 1231: 1237? Widzę to również w języku Java Boolean.hashCode (). Czy to magiczne?
David Leonard,
17
Z natury algorytmów mieszających dochodzi do kolizji. Więc nie rozumiem, o co ci chodzi, Paul.
tcurdt
85
Moim zdaniem ta odpowiedź nie odpowiada na rzeczywiste pytanie (najlepsze praktyki zastępowania skrótu NSObject). Zapewnia tylko jeden konkretny algorytm mieszania. Co więcej, rzadkość wyjaśnienia utrudnia zrozumienie bez głębokiej wiedzy na ten temat i może powodować, że ludzie będą go używać, nie wiedząc, co robią. Nie rozumiem, dlaczego to pytanie ma tak wiele pozytywnych opinii.
Ricardo Sanchez-Saez
6
1. problem - (int) jest mały i łatwy do przepełnienia, użyj NSUInteger. Drugi problem - jeśli będziesz nadal mnożyć wynik przez każdy zmienny skrót, wynik zostanie przepełniony. na przykład. [Hash NSString] tworzy duże wartości. Jeśli masz ponad 5 zmiennych, możesz łatwo przepełnić ten algorytm. Spowoduje to odwzorowanie wszystkiego na ten sam skrót, co jest złe. Zobacz moją odpowiedź: stackoverflow.com/a/4393493/276626
Paul Solt
10
@PaulSolt - Przepełnienie nie stanowi problemu w generowaniu skrótu, występuje kolizja. Ale przepełnienie niekoniecznie zwiększa prawdopodobieństwo kolizji, a twoje stwierdzenie o przepełnieniu powodujące odwzorowanie wszystkiego na ten sam skrót jest po prostu niepoprawne.
DougW
81

Po prostu wybieram Objective-C, więc nie mogę mówić konkretnie w tym języku, ale w innych językach, których używam, jeśli dwa wystąpienia są „równe”, muszą zwrócić ten sam skrót - w przeciwnym razie będziesz mieć wszystko rodzaje problemów podczas próby użycia ich jako kluczy w tablicy mieszającej (lub dowolnej kolekcji typu słownikowego).

Z drugiej strony, jeśli 2 instancje nie są równe, mogą mieć lub nie mieć tego samego skrótu - najlepiej, jeśli nie. Jest to różnica między wyszukiwaniem O (1) w tabeli skrótów a wyszukiwaniem O (N) - jeśli wszystkie twoje skróty się zderzą, może się okazać, że wyszukiwanie w tabeli nie jest lepsze niż przeszukiwanie listy.

Jeśli chodzi o najlepsze praktyki, skrót powinien zwracać losowy rozkład wartości dla danych wejściowych. Oznacza to, że na przykład jeśli masz wartość podwójną, ale większość twoich wartości ma tendencję do klastrowania między 0 a 100, musisz upewnić się, że skróty zwracane przez te wartości są równomiernie rozmieszczone w całym zakresie możliwych wartości skrótu . To znacznie poprawi Twoją wydajność.

Istnieje wiele algorytmów mieszających, w tym kilka wymienionych tutaj. Staram się unikać tworzenia nowych algorytmów mieszania, ponieważ może to mieć duży wpływ na wydajność, więc użycie istniejących metod mieszania i wykonanie kombinacji bitowej, tak jak w przykładzie, jest dobrym sposobem na uniknięcie tego.

Brian B.
źródło
4
+1 Doskonała odpowiedź, zasługuje na więcej głosów pozytywnych, zwłaszcza, że ​​tak naprawdę mówi o „najlepszych praktykach” i teorii, dlaczego dobry (unikalny) skrót jest ważny.
Quinn Taylor,
30

Zwykły XOR ponad wartościami mieszania właściwości krytycznych wystarcza na 99% czasu.

Na przykład:

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

Rozwiązanie znalezione na stronie http://nshipster.com/equality/ przez Mattta Thompsona (który również odniósł się do tego pytania w swoim poście!)

Yariv Nissim
źródło
1
Problem z tą odpowiedzią polega na tym, że w ogóle nie bierze ona pod uwagę prymitywnych wartości. A prymitywne wartości mogą również mieć znaczenie dla mieszania.
Vive
@ Vive Większość tych problemów rozwiązuje się w Swift, ale te typy zwykle reprezentują własny skrót, ponieważ są prymitywne.
Yariv Nissim,
1
Chociaż jesteś odpowiedni dla Swift, wciąż istnieje wiele projektów napisanych za pomocą objc. Ponieważ twoja odpowiedź jest poświęcona objc, warto przynajmniej wspomnieć.
Vive
Łączenie wartości skrótu XOR jest złą radą, prowadzi do wielu kolizji skrótów. Zamiast tego pomnóż przez liczbę pierwszą, a następnie dodaj, jak podają inne odpowiedzi.
fishinear
27

Uważam, że ten wątek jest niezwykle pomocny, dostarczając wszystko, czego potrzebowałem, aby uzyskać moje metody isEqual:i hashmetody zaimplementowane za jednym razem. Podczas testowania zmiennych instancji obiektu w isEqual:przykładowym kodzie użyto:

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

To wielokrotnie nie powiodło się ( tj. Zwróciło NO ) bez i błąd, gdy wiedziałem, że obiekty były identyczne w moim testowaniu jednostkowym. Powodem było to, że jedna ze NSStringzmiennych instancji była zerowa, więc powyższa instrukcja brzmiała:

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

a ponieważ zero zareaguje na każdą metodę, jest to całkowicie legalne, ale

[nil isEqual: nil]

Zwraca nil , która jest NIE , więc, gdy zarówno obiekt i jeden testowany był zerowy przedmiotu byłyby uważane jest równe ( tj , isEqual:powróci NO ).

Ta prosta poprawka polegała na zmianie instrukcji if na:

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

W ten sposób, jeśli ich adresy są takie same, pomija wywołanie metody bez względu na to, czy oba są zerowe, czy oba wskazują na ten sam obiekt, ale jeśli albo nie jest zerowy, albo wskazują inne obiekty, wówczas komparator jest odpowiednio wywoływany.

Mam nadzieję, że zaoszczędzi to komuś drapanie w głowie.

LavaSlider
źródło
20

Funkcja skrótu powinna utworzyć częściowo unikalną wartość, która prawdopodobnie nie zderzy się ani nie dopasuje wartości skrótu innego obiektu.

Oto pełna funkcja skrótu, którą można dostosować do zmiennych instancji klas. Używa NSUInteger zamiast int dla kompatybilności z aplikacjami 64 / 32bit.

Jeśli wynik zmienia się na 0 dla różnych obiektów, istnieje ryzyko kolizji skrótów. Kolizje skrótów mogą powodować nieoczekiwane zachowanie programu podczas pracy z niektórymi klasami kolekcji zależnymi od funkcji skrótu. Przed użyciem sprawdź działanie funkcji skrótu.

-(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;
}
Paul Solt
źródło
3
Jeden muszę tutaj: wolę unikać składni kropkowej, więc przekształciłem twoją instrukcję BOOL w (np result = prime * result + [self isSelected] ? yesPrime : noPrime;. ) . Potem stwierdziłem, że ustawienie resultto (np.) 1231, Zakładam, ze względu na pierwszeństwo ?operatora. Rozwiązałem problem, dodając nawiasy kwadratowe:result = prime * result + ([self isSelected] ? yesPrime : noPrime);
Ashley
12

Prostym, ale nieefektywnym sposobem jest zwrócenie tej samej -hashwartości dla każdej instancji. W przeciwnym razie tak, musisz wdrożyć hash oparty tylko na obiektach, które wpływają na równość. Jest to trudne, jeśli używasz lekkich porównań w -isEqual:(np. Porównania ciągów znaków bez rozróżniania wielkości liter). W przypadku liczb całkowitych możesz ogólnie użyć samej liczby wewnętrznej, chyba że będziesz porównywał z numerami NSNumbers.

Nie używaj | =, jednak będzie nasycone. Zamiast tego użyj ^ =.

Ciekawy fakt:, [[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]]ale [[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash]. (rdar: // 4538282, otwarte od 05 maja 2006)

Jens Ayton
źródło
1
Masz rację na | =. Tak naprawdę to nie znaczyło. :) + = i ^ = są dość równoważne. Jak radzisz sobie z prymitywami niecałkowitymi, takimi jak double i float?
Dave Dribin
Ciekawostka: przetestuj na Snow Leopard ... ;-)
Quinn Taylor
Ma rację, używając XOR zamiast OR do łączenia pól w hasz. Jednak nie korzystaj z porady dotyczącej zwracania tej samej wartości -hash dla każdego obiektu - chociaż jest to łatwe, może poważnie obniżyć wydajność wszystkiego , co używa skrótu obiektu. Hash nie musi być odrębny dla obiektów, które nie są równe, ale jeśli możesz to osiągnąć, nic takiego nie jest.
Quinn Taylor
Otwarty raport o błędach radaru jest zamknięty. openradar.me/4538282 Co to znaczy?
JJD
JJD, błąd został naprawiony w Mac OS X 10.6, jak wskazał Quinn. (Uwaga: komentarz ma dwa lata).
Jens Ayton,
9

Pamiętaj, że wystarczy podać skrót, który jest równy, gdy isEqualjest prawdziwy. Kiedy isEqualjest fałszem, skrót nie musi być nierówny, choć prawdopodobnie tak jest. W związku z tym:

Prosty skrót. Wybierz najbardziej charakterystyczną zmienną członka (lub kilku członków).

Na przykład w przypadku CLPlacemark wystarczy sama nazwa. Tak, są 2 lub 3 znaki CLPlacemark o dokładnie takiej samej nazwie, ale są one rzadkie. Użyj tego skrótu.

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

@implementation CLPlacemark (equal)

...

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


@end

Zauważ, że nie zawracam sobie głowy określaniem miasta, kraju itp. Nazwa jest wystarczająca. Być może nazwa i lokalizacja CLL.

Hash powinien być równomiernie rozłożony. Możesz połączyć kilka zmiennych składowych za pomocą znaku karetki ^ (znak xor)

To coś w stylu

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

W ten sposób skrót będzie równomiernie rozłożony.

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

Co więc robić w tablicy?

Znowu proste. Nie musisz mieszać wszystkich członków tablicy. Wystarczy haszować pierwszy element, ostatni element, liczbę, może jakieś środkowe elementy i to wszystko.

użytkownik4951
źródło
Wartości skrótów XORing nie dają równomiernego rozkładu.
fishinear
7

Poczekaj, z pewnością znacznie łatwiejszym sposobem na to jest najpierw przesłonięcie - (NSString )descriptioni przedstawienie ciągu reprezentującego stan obiektu (musisz reprezentować cały stan obiektu w tym ciągu).

Następnie podaj następującą implementację hash:

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

Opiera się to na zasadzie, że „jeśli dwa ciągi znaków są równe (zgodnie z metodą isEqualToString: metoda), muszą mieć tę samą wartość skrótu”.

Źródło: NSString Class Reference

Jonathan Ellis
źródło
1
Zakłada się, że metoda opisu będzie unikalna. Używanie skrótu opisu tworzy zależność, która może nie być oczywista, i zwiększa ryzyko kolizji.
Paul Solt
1
+1 Pozytywne. To jest świetny pomysł. Jeśli obawiasz się, że opisy powodują kolizje, możesz to zmienić.
user4951
Dzięki Jim, nie zaprzeczę, że jest to trochę hack, ale zadziałałoby w każdym razie, o czym myślę - i jak powiedziałem, pod warunkiem, że przesłonisz description, nie rozumiem, dlaczego jest to gorsze od dowolne z wyżej głosowanych rozwiązań. Może nie być najbardziej matematycznie eleganckim rozwiązaniem, ale powinno wystarczyć. Jak stwierdza Brian B. (najbardziej pozytywna odpowiedź w tym momencie): „Staram się unikać tworzenia nowych algorytmów mieszających” - zgodził się! - Właśnie ! hashNSString
Jonathan Ellis
Pozytywnie oceniany, ponieważ jest to fajny pomysł. Nie zamierzam go jednak używać, ponieważ obawiam się dodatkowych przydziałów NSString.
karwag
1
To nie jest ogólne rozwiązanie, ponieważ dla większości klas descriptionzawiera adres wskaźnika. Czyni to zatem dwa różne wystąpienia tej samej klasy, które są równe różnemu hashowi, co narusza podstawowe założenie, że dwa równe obiekty mają taki sam skrót!
Diogo T
5

Kontrakty typu equals i hash są dobrze określone i dokładnie zbadane w świecie Java (patrz odpowiedź @ mipardi), ale wszystkie te same uwagi powinny mieć zastosowanie do Celu-C.

Eclipse wykonuje niezawodne zadanie generowania tych metod w Javie, więc oto przykład Eclipse przeniesiony ręcznie do 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;
}

A dla podklasy, YourWidgetktóra dodaje właściwość 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;
}

Ta implementacja pozwala uniknąć niektórych pułapek podklas w przykładzie isEqual:od Apple:

  • Test klasy Apple other isKindOfClass:[self class]jest asymetryczny dla dwóch różnych podklas MyWidget. Równość musi być symetryczna: a = b wtedy i tylko wtedy, gdy b = a. Można to łatwo naprawić, zmieniając test na other isKindOfClass:[MyWidget class], wówczas wszystkie MyWidgetpodklasy byłyby wzajemnie porównywalne.
  • Użycie isKindOfClass:testu podklasy zapobiega zastąpieniu podklas isEqual:za pomocą udoskonalonego testu równości. Wynika to z faktu, że równość musi być przechodnia: jeśli a = b i a = c, to b = c. Jeśli MyWidgetinstancja jest równa dwóm YourWidgetinstancjom, YourWidgetmuszą one być sobie równe, nawet jeśli serialNoróżnią się między sobą.

Drugi problem można rozwiązać, biorąc pod uwagę, że obiekty są równe, jeśli należą do dokładnie tej samej klasy, stąd [self class] != [object class]test tutaj. W przypadku typowych klas aplikacji wydaje się to najlepsze podejście.

Jednak z pewnością istnieją przypadki, w których isKindOfClass:test jest lepszy. Jest to bardziej typowe dla klas frameworku niż klas aplikacji. Na przykład każdy NSStringpowinien się równać z innymi NSStringz tą samą leżącą u podstaw sekwencją znaków, niezależnie od NSString/ NSMutableStringrozróżnienia, a także niezależnie od tego, jakie klasy prywatne w NSStringklastrze klas są zaangażowane.

W takich przypadkach isEqual:powinny mieć dobrze zdefiniowane, dobrze udokumentowane zachowanie i należy wyjaśnić, że podklasy nie mogą tego zastąpić. W Javie ograniczenie „bez wymuszania” można wymusić, oznaczając metody equals i hashcode jako final, ale Cel C nie ma odpowiednika.

jedwidz
źródło
@ adubr To omówione w moich dwóch ostatnich akapitach. Nie jest ogniskowa, ponieważ MyWidgetnie jest gromadą klas.
jedwidz
5

To nie odpowiada bezpośrednio na twoje pytanie (w ogóle), ale wcześniej użyłem MurmurHash do generowania skrótów : murmurhash

Chyba powinienem wyjaśnić, dlaczego: szmer jest cholernie szybki ...

schwa
źródło
2
Biblioteka C ++, która koncentruje się na unikatowych skrótach dla klucza void * przy użyciu liczb losowych (a także nie dotyczy obiektów Objective-C), tak naprawdę nie jest tutaj pomocną sugestią. Metoda -hash powinna za każdym razem zwracać stałą wartość, inaczej będzie zupełnie bezużyteczna. Jeśli obiekt zostanie dodany do kolekcji, która wywołuje -hash i zwraca za każdym razem nową wartość, duplikaty nigdy nie zostaną wykryte i nigdy nie będzie można pobrać obiektu z kolekcji. W tym przypadku termin „skrót” różni się od znaczenia w zabezpieczeniach / kryptografii.
Quinn Taylor
3
murmurhash nie jest kryptograficzną funkcją skrótu. Sprawdź swoje fakty, zanim opublikujesz nieprawidłowe informacje. Murmurhash może być użyteczny do mieszania niestandardowych klas C-cel (szczególnie jeśli masz dużo NSDatas), ponieważ jest on niezwykle szybki. Przyznaję jednak, że być może sugerowanie, że nie jest to najlepsza rada dla kogoś „po prostu wybierającego cel-c”, ale zwróć uwagę na mój prefiks mojej oryginalnej odpowiedzi na pytanie.
schwa
4

Jestem newbie zbyt Objective C, ale znalazłem doskonały artykuł na temat równości wobec tożsamości w Objective C tutaj . Z mojego czytania wynika, że ​​możesz zachować domyślną funkcję skrótu (która powinna zapewnić unikalną tożsamość) i wdrożyć metodę isEqual, aby porównać wartości danych.

Ceperry
źródło
Jestem początkującym Cocoa / Objective C, a ta odpowiedź i link naprawdę pomogły mi przejść przez wszystkie bardziej zaawansowane rzeczy powyżej do dolnej linii - nie muszę się martwić o hasze - po prostu wdrażam metodę isEqual:. Dzięki!
John Gallagher,
Nie przegap linku @ ceperry. Artykuł Equality vs IdentityKarla Krafta jest naprawdę dobry.
JJD,
6
@John: Myślę, że powinieneś ponownie przeczytać artykuł. Mówi bardzo wyraźnie, że „instancje, które są równe, muszą mieć równe wartości skrótu”. Jeśli przesłonisz isEqual:, musisz również przesłonić hash.
Steve Madsen
3

Quinn się myli, że odniesienie do skrótu szmeru jest tutaj bezużyteczne. Quinn ma rację, że chcesz zrozumieć teorię mieszania. Szmer destyluje wiele z tej teorii do implementacji. Warto zastanowić się, jak zastosować tę implementację w tej konkretnej aplikacji.

Niektóre kluczowe punkty tutaj:

Przykładowa funkcja z tcurdt sugeruje, że „31” jest dobrym mnożnikiem, ponieważ jest liczbą pierwszą. Trzeba pokazać, że bycie najlepszym jest warunkiem koniecznym i wystarczającym. W rzeczywistości 31 (i 7) prawdopodobnie nie są szczególnie dobrymi liczbami pierwszymi, ponieważ 31 == -1% 32. Dziwny mnożnik z około połową ustawionych bitów i połową bitów czystych prawdopodobnie będzie lepszy. (Stała mnożenia wartości skrótu ma tę właściwość).

Ten typ funkcji skrótu byłby prawdopodobnie silniejszy, gdyby po pomnożeniu wartość wyniku była regulowana za pomocą shift i xor. Mnożenie prowadzi do uzyskania wyników wielu interakcji bitowych na górnym końcu rejestru i niskich wyników interakcji na dolnym końcu rejestru. Shift i Xor zwiększają interakcje na dolnym końcu rejestru.

Przydatne byłoby również ustawienie początkowego wyniku na wartość, w której około połowa bitów to zero, a około połowa bitów to jeden.

Przydatne może być zachowanie ostrożności w kolejności łączenia elementów. Prawdopodobnie należy najpierw przetworzyć wartości logiczne i inne elementy, w których wartości nie są silnie rozłożone.

Przydatne może być dodanie kilku dodatkowych etapów szyfrowania bitów na końcu obliczeń.

To, czy skrót szmeru jest naprawdę szybki dla tej aplikacji, jest pytaniem otwartym. Hash szmeru miesza bitów każdego słowa wejściowego. Wiele słów wejściowych może być przetwarzanych równolegle, co pomaga w wielu problemach z przetwarzaniem potokowym.


źródło
3

Łącząc odpowiedź @ tcurdt z odpowiedzią @ oscar-gomez dotyczącą uzyskiwania nazw właściwości , możemy stworzyć łatwe rozwiązanie dla isEqual i 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;
}

Teraz w swojej klasie niestandardowej możesz łatwo wdrożyć isEqual:i hash:

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

- (BOOL)isEqual:(id)other
{
    return IsEqualObjects(self, other);
}
johnboiles
źródło
2

Pamiętaj, że jeśli tworzysz obiekt, który można mutować po utworzeniu, wartość skrótu nie może ulec zmianie, jeśli obiekt zostanie wstawiony do kolekcji. W praktyce oznacza to, że wartość skrótu musi zostać ustalona od momentu początkowego utworzenia obiektu. Aby uzyskać więcej informacji, zobacz dokumentację Apple dotyczącą metody -hash protokołu NSObject :

Jeśli zmienny obiekt zostanie dodany do kolekcji, która korzysta z wartości skrótu w celu ustalenia pozycji obiektu w kolekcji, wartość zwrócona przez metodę skrótu obiektu nie może się zmienić, gdy obiekt jest w kolekcji. Dlatego albo metoda mieszania nie może polegać na żadnej z wewnętrznych informacji o stanie obiektu, albo musisz upewnić się, że wewnętrzne informacje o stanie obiektu nie ulegną zmianie, gdy obiekt znajduje się w kolekcji. Tak więc, na przykład, słownik zmiennych można umieścić w tablicy haszującej, ale nie wolno jej zmieniać, gdy jest w niej. (Należy pamiętać, że może być trudno ustalić, czy dany obiekt znajduje się w kolekcji).

Dla mnie to brzmi jak kompletna walka, ponieważ potencjalnie skutecznie sprawia, że ​​wyszukiwanie skrótów jest znacznie mniej wydajne, ale przypuszczam, że lepiej jest zachować ostrożność i postępować zgodnie z tym, co mówi dokumentacja.

użytkownik10345
źródło
1
Źle czytasz dokumenty hashujące - jest to w zasadzie sytuacja „albo-albo”. Jeśli obiekt się zmienia, skrót również ogólnie się zmienia. Jest to naprawdę ostrzeżenie dla programisty, że jeśli skrót zostanie zmieniony w wyniku mutacji obiektu, to zmiana obiektu znajdującego się w kolekcji wykorzystującej skrót spowoduje nieoczekiwane zachowanie. Jeśli w takiej sytuacji obiekt musi być „bezpiecznie zmienny”, nie ma innego wyjścia, jak uczynić hash niezwiązanym ze stanem zmiennym. Ta szczególna sytuacja wydaje mi się dziwna, ale z pewnością zdarzają się sytuacje, w których ma ona zastosowanie.
Quinn Taylor
1

Przepraszam, jeśli zaryzykuję sformułowanie kompletnego buminu tutaj, ale ... ... nikt nie zadał sobie trudu, by wspomnieć, że przestrzegając „najlepszych praktyk”, zdecydowanie nie powinieneś określać metody równości, która NIE uwzględniałaby wszystkich danych posiadanych przez obiekt docelowy, np. dane są agregowane do twojego obiektu, w porównaniu z jego powiązaniem, należy wziąć pod uwagę przy wdrażaniu równości. Jeśli nie chcesz brać pod uwagę, powiedz „wiek” w porównaniu, powinieneś napisać komparator i użyć go do wykonania porównań zamiast isEqual :.

Jeśli zdefiniujesz metodę isEqual: arbitralnie wykonującą porównanie równości, poniesiesz ryzyko, że ta metoda zostanie niewłaściwie wykorzystana przez innego programistę, a nawet przez ciebie samego, gdy zapomnisz o „zakręcie” w interpretacji równości.

Ergo, chociaż jest to świetne pytanie dotyczące haszowania, zwykle nie trzeba na nowo definiować metody haszowania, prawdopodobnie zamiast tego należy zdefiniować komparator ad-hoc.

Thibaud de Souza
źródło