Jeśli kod skrótu null zawsze wynosi zero, w .NET


87

Biorąc pod uwagę, że kolekcje takie jak System.Collections.Generic.HashSet<>accept nulljako członek zestawu, można zapytać, jaki nullpowinien być kod skrótu . Wygląda na to, że framework używa 0:

// nullable struct type
int? i = null;
i.GetHashCode();  // gives 0
EqualityComparer<int?>.Default.GetHashCode(i);  // gives 0

// class type
CultureInfo c = null;
EqualityComparer<CultureInfo>.Default.GetHashCode(c);  // gives 0

Może to być (trochę) problematyczne w przypadku wyliczeń dopuszczających wartość null. Jeśli zdefiniujemy

enum Season
{
  Spring,
  Summer,
  Autumn,
  Winter,
}

wtedy Nullable<Season>(również nazywany Season?) może przyjąć tylko pięć wartości, ale dwie z nich, mianowicie nulli Season.Spring, mają ten sam kod skrótu.

Kuszące byłoby napisanie „lepszego” narzędzia do porównywania równości w następujący sposób:

class NewNullEnumEqComp<T> : EqualityComparer<T?> where T : struct
{
  public override bool Equals(T? x, T? y)
  {
    return Default.Equals(x, y);
  }
  public override int GetHashCode(T? x)
  {
    return x.HasValue ? Default.GetHashCode(x) : -1;
  }
}

Ale czy jest jakiś powód, dla którego nullpowinien być kod skrótu 0?

EDYCJA / DODANIE:

Niektórym wydaje się, że chodzi o nadpisywanie Object.GetHashCode(). Tak naprawdę nie jest. (Jednak autorzy .NET dokonali nadpisania GetHashCode()w Nullable<>strukturze, co jest istotne). Napisana przez użytkownika implementacja parametru GetHashCode()bezparametrowego nigdy nie poradzi sobie z sytuacją, w której znajduje się obiekt, którego szukamy kodu skrótu null.

Chodzi o implementację metody abstrakcyjnej EqualityComparer<T>.GetHashCode(T)lub inną implementację metody interfejsu IEqualityComparer<T>.GetHashCode(T). Teraz, podczas tworzenia tych linków do MSDN, widzę, że jest tam napisane, że te metody rzucają, ArgumentNullExceptionjeśli ich jedynym argumentem jest null. To z pewnością błąd w MSDN? Żadna z własnych implementacji platformy .NET nie zgłasza wyjątków. Rzucenie w takim przypadku skutecznie przerwałoby każdą próbę dodania nulldo HashSet<>. Chyba że HashSet<>robi coś niezwykłego, gdy ma do czynienia z nullprzedmiotem (będę musiał to przetestować).

NOWA EDYCJA / DODATEK:

Teraz próbowałem debugować. Dzięki HashSet<>, mogę potwierdzić, że z comparer domyślny równości, wartości Season.Springi null będzie kończyć się w tym samym segmencie. Można to ustalić, bardzo dokładnie sprawdzając prywatne elementy tablicy m_bucketsi m_slots. Zauważ, że indeksy są zawsze, zgodnie z projektem, przesunięte o jeden.

Kod, który podałem powyżej, jednak tego nie naprawia. Jak się okazuje, HashSet<>nigdy nawet nie zapyta modułu porównującego równość, kiedy wartość wynosi null. To pochodzi z kodu źródłowego HashSet<>:

    // Workaround Comparers that throw ArgumentNullException for GetHashCode(null).
    private int InternalGetHashCode(T item) {
        if (item == null) { 
            return 0;
        } 
        return m_comparer.GetHashCode(item) & Lower31BitMask; 
    }

Oznacza to, że przynajmniej w przypadku HashSet<>nie można nawet zmienić skrótu pliku null. Zamiast tego rozwiązaniem jest zmiana skrótu wszystkich innych wartości, na przykład:

class NewerNullEnumEqComp<T> : EqualityComparer<T?> where T : struct
{
  public override bool Equals(T? x, T? y)
  {
    return Default.Equals(x, y);
  }
  public override int GetHashCode(T? x)
  {
    return x.HasValue ? 1 + Default.GetHashCode(x) : /* not seen by HashSet: */ 0;
  }
}

1
Po drugie - bardzo dobre pytanie.
Sachin Kainth

26
Dlaczego kod skrótu dla null nie powinien wynosić zero? Wiesz, kolizja hash to nie koniec świata.
Hot Licks

3
Tyle że jest to dobrze znana, dość powszechna kolizja. Nie żeby to było złe, a nawet tak poważny problem, po prostu łatwo go uniknąć
Chris Pfohl

8
lol, dlaczego myślę „jeśli .NET framework wyskoczy z mostu, czy podążymy za nim?” ...
Adam Houldsworth

3
Tak z ciekawości, jaki byłby zerowy sezon?
SwDevMan81

Odpowiedzi:


25

Tak długo, jak kod skrótu zwracany dla wartości null jest spójny dla typu, wszystko powinno być w porządku. Jedynym wymaganiem dla kodu skrótu jest to, że dwa obiekty, które są uważane za równe, mają ten sam kod skrótu.

Zwracanie 0 lub -1 dla null, o ile wybierzesz jeden i będziesz go zwracać przez cały czas, zadziała. Oczywiście kody skrótu inne niż null nie powinny zwracać żadnej wartości, której używasz dla null.

Podobne pytania:

GetHashCode na pustych polach?

Co powinien zwrócić GetHashCode, gdy identyfikator obiektu ma wartość null?

W sekcji „Uwagi” tego wpisu MSDN opisano bardziej szczegółowo kod skrótu. Przejmująco, dokumentacja nie zawiera żadnego pokrycia lub omówienie wartości null w ogóle - nawet w zawartość.

Aby rozwiązać problem z wyliczeniem, zaimplementuj ponownie kod skrótu, aby zwracał wartość różną od zera, dodaj domyślny wpis wyliczenia „nieznany” równoważny null lub po prostu nie używaj wyliczeń dopuszczających wartość null.

Nawiasem mówiąc, ciekawe znalezisko.

Innym problemem, który widzę z tym ogólnie, jest to, że kod skrótu nie może reprezentować 4-bajtowego lub większego typu, który jest dopuszczalny bez co najmniej jednej kolizji (więcej, gdy zwiększa się rozmiar typu). Na przykład kod skrótu int to po prostu int, więc używa pełnego zakresu int. Jaką wartość w tym zakresie wybierasz dla null? Cokolwiek wybierzesz, zderzy się z samym kodem skrótu wartości.

Zderzenia same w sobie niekoniecznie są problemem, ale musisz wiedzieć, że one istnieją. Kody skrótu są używane tylko w niektórych okolicznościach. Jak stwierdzono w dokumentacji na MSDN, kody skrótów nie gwarantują zwrócenia różnych wartości dla różnych obiektów, więc nie należy się tego spodziewać.


Nie sądzę, aby pytania, które łączysz, były całkowicie podobne. Kiedy nadpisujesz Object.GetHashCode()w swojej własnej klasie (lub strukturze), wiesz, że ten kod zostanie trafiony tylko wtedy, gdy ludzie faktycznie mają instancję Twojej klasy. Taka instancja nie może być null. To dlaczego nie zacząć od override Object.GetHashCode()z if (this == null) return -1;Istnieje różnica między „być null” i „bycia obiektem posiadającym kilka pól, które są null”.
Jeppe Stig Nielsen

Mówisz: Oczywiście kody haszujące inne niż null nie powinny zwracać żadnej wartości, której używasz dla null. Zgadzam się, to byłoby idealne. I to jest powód, dla którego zadałem swoje pytanie w pierwszej kolejności, ponieważ ilekroć piszemy wyliczenie T, wtedy (T?)nulli (T?)default(T)będziemy mieć ten sam kod skrótu (w obecnej implementacji .NET). Można to zmienić, jeśli implementatorzy platformy .NET zmienili kod skrótu null lub algorytm kodu skrótu System.Enum.
Jeppe Stig Nielsen

Zgadzam się, że linki dotyczyły pustych pól wewnętrznych. Wspomniałeś, że jest to dla IEqualityComparer <T>, w Twojej implementacji kod skrótu jest nadal specyficzny dla typu, więc nadal jesteś w tej samej sytuacji, spójność dla typu. Zwracanie tego samego kodu skrótu dla wartości null dowolnego typu nie ma znaczenia, ponieważ wartości null nie mają typu.
Adam Houldsworth

1
Uwaga: dwukrotnie zaktualizowałem swoje pytanie. Okazuje się, że (przynajmniej z HashSet<>) nie działa zmiana kodu skrótu programu null.
Jeppe Stig Nielsen

6

Należy pamiętać, że kod skrótu jest używany jako pierwszy krok tylko do określania równości i [jest / nie powinien] nigdy (być) używany jako faktyczne określenie, czy dwa obiekty są równe.

Jeśli kody skrótu dwóch obiektów nie są równe, to są traktowane jako nierówne (ponieważ zakładamy, że podstawowa implementacja jest poprawna - tj. Nie odgadujemy tego ponownie). Jeśli mają ten sam kod skrótu, należy je następnie sprawdzić pod kątem rzeczywistej równości, co w twoim przypadku nullnie powiedzie się wartość i wartość wyliczenia.

W rezultacie - użycie zera jest tak samo dobre jak każdej innej wartości w ogólnym przypadku.

Jasne, będą sytuacje, takie jak wyliczenie, w których to zero jest współdzielone z kodem skrótu rzeczywistej wartości. Pytanie brzmi, czy malutki koszt dodatkowego porównania powoduje problemy.

Jeśli tak, zdefiniuj własną funkcję porównującą dla przypadku wartości null dla określonego typu i upewnij się, że wartość null zawsze daje kod skrótu, który jest zawsze taki sam (oczywiście!) I wartość, której nie może uzyskać podstawowa własny algorytm kodu skrótu. Dla twoich własnych typów jest to możliwe. Dla innych - powodzenia :)


5

Nie musi to być zero - jeśli chcesz, możesz zrobić to 42.

Liczy się tylko konsekwencja w realizacji programu.

To najbardziej oczywista reprezentacja, ponieważ nullczęsto jest reprezentowana jako zero wewnętrznie. Co oznacza, że ​​podczas debugowania, jeśli zobaczysz kod skrótu o wartości zero, możesz pomyśleć: „Hmm… czy to był problem z zerową referencją?”

Zwróć uwagę, że jeśli użyjesz liczby takiej jak 0xDEADBEEF, to ktoś może powiedzieć, że używasz magicznej liczby ... i tak jakbyś był. (Można powiedzieć, że zero jest również magiczną liczbą i miałbyś rację ... z wyjątkiem tego, że jest tak szeroko stosowany, że jest czymś w rodzaju wyjątku od reguły.)


4

Dobre pytanie.

Właśnie próbowałem to zakodować:

enum Season
{
  Spring,
  Summer,
  Autumn,
  Winter,
}

i wykonaj to w ten sposób:

Season? v = null;
Console.WriteLine(v);

wraca null

jeśli tak, zamiast normalne

Season? v = Season.Spring;
Console.WriteLine((int)v);

powróci 0, zgodnie z oczekiwaniami, lub po prostu Spring, jeśli unikniemy rzucania int.

Więc .. jeśli wykonasz następujące czynności:

Season? v = Season.Spring;  
Season? vnull = null;   
if(vnull == v) // never TRUE

EDYTOWAĆ

Z MSDN

Jeśli dwa obiekty są porównywane jako równe, metoda GetHashCode dla każdego obiektu musi zwracać tę samą wartość. Jeśli jednak dwa obiekty nie są porównywane jako równe, metody GetHashCode dla tych dwóch obiektów nie muszą zwracać różnych wartości

Innymi słowy: jeśli dwa obiekty mają ten sam kod skrótu, co nie oznacza, że ​​są równe, to rzeczywista równość jest określana przez Equals .

Z MSDN ponownie:

Metoda GetHashCode dla obiektu musi konsekwentnie zwracać ten sam kod skrótu, o ile nie ma modyfikacji stanu obiektu, który określa wartość zwracaną przez metodę Equals obiektu. Należy zauważyć, że dotyczy to tylko bieżącego wykonywania aplikacji i że można zwrócić inny kod skrótu, jeśli aplikacja zostanie ponownie uruchomiona.


6
kolizja z definicji oznacza, że ​​dwa nierówne obiekty mają ten sam kod skrótu. Pokazałeś, że przedmioty nie są równe. Czy mają teraz ten sam kod skrótu? Według PO tak, co oznacza, że ​​jest to kolizja. To nie koniec świata, w którym dochodzi do kolizji, jest to po prostu bardziej prawdopodobna kolizja, niż gdyby null hashował do czegoś innego niż 0, co obniża wydajność.
Servy

1
Co właściwie mówi twoja odpowiedź? Mówisz, że Season.Spring nie jest równe zero. Cóż, to nie jest złe, ale tak naprawdę nie odpowiada na to pytanie w żaden sposób, teraz tak.
Servy

2
@Servy: pytanie brzmi: dlaczego mam ten sam hascode dla 2 różnych obiektów ( null i Spring ). Więc odpowiedź jest taka, że ​​nie ma przyczyny kolizji nawet mając ten sam hashcode, nawiasem mówiąc, nie są równe.
Tigran

3
„Odpowiedź: dlaczego nie?” Cóż, PO uprzednio odpowiedział na twoje pytanie „dlaczego nie”. Jest bardziej prawdopodobne, że spowoduje kolizje niż inna liczba. Zastanawiał się, czy był powód, dla którego wybrano 0, i jak dotąd nikt na to nie odpowiedział.
Servy

1
Ta odpowiedź nie zawiera niczego, czego PO by nie wiedział, co wynika ze sposobu, w jaki zadano pytanie.
Konrad Rudolph

4

Ale czy jest jakiś powód, dla którego kod skrótu null powinien wynosić 0?

To mogło być cokolwiek. Zwykle się zgadzam, że 0 niekoniecznie było najlepszym wyborem, ale prawdopodobnie prowadzi do najmniejszej liczby błędów.

Funkcja skrótu bezwzględnie musi zwracać ten sam skrót dla tej samej wartości. Raz istnieje na składnik, który to robi, to jest naprawdę ważne tylko wartość dla skrótu null. Gdyby istniała dla tego stała, taka jak hm object.HashOfNull, to ktoś wdrażający a IEqualityComparermusiałby wiedzieć, jak użyć tej wartości. Jeśli o tym nie pomyślą, szansa, że ​​użyją 0, jest nieco wyższa niż każda inna wartość, jak sądzę.

przynajmniej w przypadku HashSet <> nie jest nawet możliwa zmiana wartości skrótu null

Jak wspomniano powyżej, myślę, że jest to całkowicie niemożliwe, ponieważ istnieją typy, które już są zgodne z konwencją, w której hash z null wynosi 0.


Kiedy implementuje się metodę EqualityComparer<T>.GetHashCode(T)dla jakiegoś określonego typu, Tktóry na to pozwala null, trzeba coś zrobić, gdy argument jest null. Możesz (1) rzucić ArgumentNullException, (2) zwrócić 0lub (3) zwrócić coś innego. Przyjmuję twoją odpowiedź za zalecenie, aby zawsze wracać 0w takiej sytuacji?
Jeppe Stig Nielsen

@JeppeStigNielsen Nie jestem pewien co do rzutu i powrotu, ale jeśli zdecydujesz się wrócić, to zdecydowanie zero.
Roman Starkov

2

Ze względu na prostotę jest to 0. Nie ma takiego surowego wymogu. Musisz tylko zapewnić ogólne wymagania dotyczące kodowania hash.

Na przykład musisz się upewnić, że jeśli dwa obiekty są równe, ich hashcodes również muszą być równe. Dlatego różne hashcody muszą zawsze reprezentować różne obiekty (ale niekoniecznie jest to prawdą odwrotnie: dwa różne obiekty mogą mieć ten sam hashcode, nawet jeśli zdarza się to często, nie jest to dobrej jakości funkcja hashująca - nie ma dobra odporność na kolizje).

Oczywiście ograniczyłem swoją odpowiedź do wymagań natury matematycznej. Istnieją również warunki techniczne specyficzne dla platformy .NET, o których można przeczytać tutaj . 0 dla wartości zerowej nie ma wśród nich.


1

Można więc tego uniknąć, używając Unknownwartości wyliczenia (chociaż wydaje się nieco dziwne, że a Seasonjest nieznane). Więc coś takiego mogłoby zanegować ten problem:

public enum Season
{
   Unknown = 0,
   Spring,
   Summer,
   Autumn,
   Winter
}

Season some_season = Season.Unknown;
int code = some_season.GetHashCode(); // 0
some_season = Season.Autumn;
code = some_season.GetHashCode(); // 3

Wtedy miałbyś unikalne wartości kodu skrótu dla każdego sezonu.


1
tak, ale to nie odpowiada w rzeczywistości na pytanie. W ten sposób zgodnie z pytaniem null zderzy się z Uknown. Co to jest różnica?
Tigran

@Tigran - Ta wersja nie używa typu dopuszczającego wartość null
SwDevMan81

Rozumiem, ale pytanie dotyczy typu dopuszczającego wartość null.
Tigran

Mam w SO milion razy scenę, którą ludzie proponują jako odpowiedzi.
SwDevMan81

1

Osobiście uważam, że używanie wartości zerowych jest trochę niezręczne i staram się ich unikać, kiedy tylko mogę. Twój problem to tylko kolejny powód. Czasami są jednak bardzo przydatne, ale moją zasadą jest, aby nie mieszać typów wartości z null, jeśli to możliwe, tylko dlatego, że pochodzą z dwóch różnych światów. W środowisku .NET wydają się robić to samo - wiele typów wartości udostępnia TryParsemetodę, która jest sposobem na oddzielenie wartości od żadnych wartości ( null).

W twoim konkretnym przypadku łatwo jest pozbyć się problemu, ponieważ radzisz sobie z własnym Seasontypem.

(Season?)nulldla mnie oznacza „sezon nie jest określony”, tak jak w przypadku formularza internetowego, w którym niektóre pola nie są wymagane. Moim zdaniem lepiej jest określić tę specjalną „wartość” w enumsobie, zamiast używać jej trochę niezgrabnie Nullable<T>. Będzie szybszy (bez boksu), łatwiejszy do odczytania (w Season.NotSpecifiedporównaniu z null) i rozwiąże Twój problem z kodami skrótu.

Oczywiście w przypadku innych typów, na przykład intnie można rozszerzyć dziedziny wartości, a określenie jednej z wartości jako specjalnej nie zawsze jest możliwe. Ale int?kolizja kodu skrótu jest znacznie mniejszym problemem, jeśli w ogóle.


Kiedy mówisz „boks”, myślę, że masz na myśli „zawijanie”, tj. Umieszczanie wartości struktury wewnątrz Nullable<>struktury (gdzie element HasValueczłonkowski zostanie ustawiony na true). Czy na pewno problem jest naprawdę mniejszy int?? W wielu przypadkach używa się tylko kilku wartości int, a następnie jest to równoważne wyliczeniu (które teoretycznie może mieć wielu członków).
Jeppe Stig Nielsen

Generalnie powiedziałbym, że wyliczenie jest wybierane, gdy wymagana jest ograniczona liczba znanych wartości (2-10). Jeśli limit jest większy lub nie intma go wcale, ma to większy sens. Oczywiście preferencje są różne.
Maciej

0
Tuple.Create( (object) null! ).GetHashCode() // 0
Tuple.Create( 0 ).GetHashCode() // 0
Tuple.Create( 1 ).GetHashCode() // 1
Tuple.Create( 2 ).GetHashCode() // 2

1
To ciekawe podejście. Przydałaby się zmiana odpowiedzi, tak aby zawierała dodatkowe wyjaśnienia, zwłaszcza biorąc pod uwagę charakter pytania.
Jeremy Caney
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.