Le code de hachage de null doit-il toujours être égal à zéro, en .NET ?

Question

Étant donné que des collections telles que System.Collections.Generic.HashSet<> accepter null en tant que membre d'un ensemble, on peut se demander quel est le code de hachage de null devrait être. Il semble que le cadre utilise 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

Cela peut s'avérer (un peu) problématique avec les enums nullables. Si nous définissons

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

puis le Nullable<Season> (également appelé Season? ) ne peut prendre que cinq valeurs, mais deux d'entre elles, à savoir null et Season.Spring ont le même code de hachage.

Il est tentant d'écrire un "meilleur" comparateur d'égalité comme celui-ci :

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

Mais y a-t-il une raison pour que le code de hachage de null devrait être 0 ?

EDIT/ADDITION :

Certaines personnes semblent penser qu'il s'agit de passer outre à l'obligation d'information. Object.GetHashCode() . En fait, ce n'est pas le cas. (Les auteurs de .NET ont fait une surcharge de GetHashCode() dans le Nullable<> structure qui es (mais cela n'a rien à voir avec le sujet). Une implémentation écrite par l'utilisateur de la méthode sans paramètre GetHashCode() ne peut jamais gérer la situation où l'objet dont nous cherchons le code de hachage est null .

Il s'agit de mettre en œuvre la méthode abstraite EqualityComparer<T>.GetHashCode(T) ou en mettant en œuvre la méthode de l'interface IEqualityComparer<T>.GetHashCode(T) . Maintenant, en créant ces liens vers MSDN, je vois qu'il y est dit que ces méthodes lancent un ArgumentNullException si leur seul argument est null . Il s'agit certainement d'une erreur de MSDN ? Aucune des implémentations de .NET ne lance d'exception. Dans ce cas, le fait de lancer des exceptions briserait effectivement toute tentative d'ajouter la fonction null à un HashSet<> . A moins que HashSet<> fait quelque chose d'extraordinaire lorsqu'il s'agit d'un null (il faudra que je teste cela).

NOUVELLE MODIFICATION/AJOUT :

J'ai ensuite essayé de déboguer. Avec HashSet<> Je peux confirmer qu'avec le comparateur d'égalité par défaut, les valeurs Season.Spring et null volonté se terminent dans le même seau. Cela peut être déterminé en inspectant très attentivement les membres du tableau privé m_buckets et m_slots . Notez que les indices sont toujours, par construction, décalés d'une unité.

Le code que j'ai donné ci-dessus ne résout cependant pas ce problème. Il s'avère que HashSet<> ne demandera même pas au comparateur d'égalité si la valeur est null . Ceci est tiré du code source de 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; 
    }

Cela signifie que, au moins pour HashSet<> il n'est même pas possible de modifier le hash de null . La solution consiste à modifier le hachage de toutes les autres valeurs, comme suit :

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

Answer 1

Tant que le code de hachage renvoyé pour les nullités est cohérent pour le type, tout devrait bien se passer. La seule exigence pour un code de hachage est que deux objets considérés comme égaux partagent le même code de hachage.

Renvoyer 0 ou -1 pour null, à condition d'en choisir un et de le renvoyer tout le temps, fonctionnera. Évidemment, les codes de hachage non nuls ne doivent pas renvoyer la valeur que vous utilisez pour null.

Questions similaires :

~~

GetHashCode sur les champs nuls ?

Que doit renvoyer GetHashCode lorsque l'identifiant de l'objet est nul ?

~~

Les "Remarques" du présent Entrée MSDN donne plus de détails sur le code de hachage. Il est intéressant de noter que la documentation n'aborde pas la question des valeurs nulles. à tous - même pas dans le contenu communautaire.

Pour résoudre votre problème avec l'enum, réimplémentez le code de hachage pour qu'il renvoie une valeur non nulle, ajoutez une entrée d'enum "inconnue" par défaut équivalente à null, ou n'utilisez tout simplement pas d'enum nullable.

Une trouvaille intéressante, d'ailleurs.

Un autre problème que je vois avec cette méthode est que le code de hachage ne peut pas représente un type de 4 octets ou plus qui est nullable sans au moins une collision (d'autant plus que la taille des caractères augmente). Par exemple, le code de hachage d'un int est juste l'int, il utilise donc toute la plage de l'int. Quelle valeur de cette plage choisissez-vous pour null ? Celle que vous choisirez entrera en collision avec le code de hachage de la valeur elle-même.

Les collisions en elles-mêmes ne sont pas nécessairement un problème, mais vous devez savoir qu'elles existent. Les codes de hachage ne sont utilisés que dans certaines circonstances. Comme indiqué dans la documentation de MSDN, les codes de hachage ne sont pas garantis de renvoyer des valeurs différentes pour des objets différents et ne devraient donc pas être utilisés.

Answer 2

Ce n'est pas le cas avoir à zéro -- Vous pourriez en faire 42 si vous le souhaitiez.

Tout ce qui compte, c'est cohérence pendant l'exécution du programme.

C'est juste la représentation la plus évidente, parce que null est souvent représenté par un zéro en interne. En d'autres termes, lors du débogage, si vous voyez un code de hachage de zéro, cela peut vous inciter à penser : "Hmm s'agit-il d'un problème de référence nulle ?"

Notez que si vous utilisez un nombre comme 0xDEADBEEF On pourrait alors dire que vous utilisez un nombre magique... et c'est en quelque sorte le cas. (On pourrait aussi dire que le zéro est un nombre magique, et on aurait en quelque sorte raison... sauf qu'il est si largement utilisé qu'il constitue en quelque sorte une exception à la règle).

Answer 3

N'oubliez pas que le code de hachage n'est utilisé que comme première étape dans la détermination de l'égalité et qu'il [n'est/ne devrait] jamais (être) utilisé pour déterminer de facto si deux objets sont égaux.

Si les codes de hachage de deux objets ne sont pas identiques, ils sont traités comme tels (car nous supposons que l'implémentation unerlying est correcte - c'est-à-dire que nous ne la remettons pas en question). S'ils ont le même code de hachage, ils doivent alors être vérifiés pour les éléments suivants réel l'égalité qui, dans votre cas, le null et la valeur de l'énumération échouera.

Par conséquent, l'utilisation de zéro est aussi bonne que n'importe quelle autre valeur dans le cas général.

Bien sûr, il y aura des situations, comme votre énumération, où ce zéro est partagé avec un réel le code de hachage de la valeur. La question est de savoir si, pour vous, le minuscule surcoût d'une comparaison supplémentaire pose des problèmes.

Si c'est le cas, définissez votre propre comparateur pour le cas du nullable pour votre type particulier, et assurez-vous qu'une valeur nulle produit toujours un code de hachage qui est toujours le même (bien sûr !). y une valeur qui ne peut être produite par l'algorithme de hachage propre au type sous-jacent. Pour vos propres types, c'est faisable. Pour les autres, bonne chance :)

Answer 4

Bonne question.

Je viens d'essayer de coder cela :

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

et l'exécuter comme suit :

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

il renvoie null

si je le fais, au lieu de normal

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

il renvoie 0 comme prévu, ou simple Printemps si nous évitons d'avoir recours à int .

Donc, si vous faites ce qui suit

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

EDITAR

De MSDN

Si deux objets sont comparés comme étant égaux, la méthode GetHashCode de chaque objet doit renvoyer la même valeur. Toutefois, si deux objets ne sont pas comparés comme étant égaux, les méthodes GetHashCode pour les deux objets ne doivent pas nécessairement renvoyer des valeurs différentes.

En d'autres termes : si deux objets ont le même code de hachage, cela ne signifie pas qu'ils sont égaux, car réel L'égalité est déterminée par Équivalents .

Toujours d'après MSDN :

La méthode GetHashCode pour un objet doit consi code de hachage tant qu'il n'y a pas de modification de l'état de l'objet qui détermine la valeur de retour de la méthode Equals de l'objet. détermine la valeur de retour de la méthode Equals de l'objet. Notez que ceci n'est vrai que pour l'exécution en cours d'une application, et que qu'un code de hachage différent peut être renvoyé si l'application est exécutée si l'application est réexécutée.

Answer 5

Mais y a-t-il une raison pour que le code de hachage de null soit 0 ?

Cela aurait pu être n'importe quoi. Je suis d'accord pour dire que 0 n'était pas nécessairement le meilleur choix, mais c'est celui qui entraîne probablement le moins de bogues.

Une fonction de hachage absolument debe renvoient le même hachage pour la même valeur. Une fois qu'il existe a qui fait cela, c'est vraiment la seule valeur valide pour le hachage de null . S'il y avait une constante pour cela, comme, hm, object.HashOfNull , alors quelqu'un qui met en œuvre un IEqualityComparer pour utiliser cette valeur. S'ils n'y pensent pas, la probabilité qu'ils utilisent 0 est légèrement plus élevée que toutes les autres valeurs, je pense.

au moins pour les HashSet<>, il n'est même pas possible de changer le hash de null

Comme mentionné plus haut, je pense que c'est complètement impossible, simplement parce qu'il existe des types qui suivent déjà la convention selon laquelle le hash de null est 0.