Why can't you use null as a key for a Dictionary<bool?, string>?

Question

Apparently, you cannot use a null for a key, even if your key is a nullable type.

This code:

var nullableBoolLabels = new System.Collections.Generic.Dictionary<bool?, string>
{
    { true, "Yes" },
    { false, "No" },
    { null, "(n/a)" }
};

...results in this exception:

Value cannot be null. Parameter name: key

Description: An unhandled exception occurred during the execution of the current web request. Please review the stack trace for more information about the error and where it originated in the code.

[ArgumentNullException: Value cannot be null. Parameter name: key] System.ThrowHelper.ThrowArgumentNullException(ExceptionArgument argument) +44 System.Collections.Generic.Dictionary'2.Insert(TKey key, TValue value, Boolean add) +40
System.Collections.Generic.Dictionary'2.Add(TKey key, TValue value) +13

Why would the .NET framework allow a nullable type for a key, but not allow a null value?

Solution 1

It would tell you the same thing if you had a Dictionary<SomeType, string>, SomeType being a reference type, and you tried to pass null as the key, it is not something affecting only nullable type like bool?. You can use any type as the key, nullable or not.

It all comes down to the fact that you can't really compare nulls. I assume the logic behind not being able to put null in the key, a property that is designed to be compared with other objects is that it makes it incoherent to compare null references.

If you want a reason from the specs, it boils down to a "A key cannot be a null reference " on MSDN.

If you want an exemple of a possible workaround, you can try something similar to Need an IDictionary implementation that will allow a null key

Solution 2

Oftentimes you have to go back to C++ methodologies and techniques to fully understand how and why the .NET Framework works in a particular manner.

In C++, you oftentimes have to pick a key that will not be used - the dictionary uses this key to point to deleted and/or empty entries. For instance, you have a dictionary of <int, int>, and after inserting an entry, you delete it. Rather than running the Garbage Cleanup right then and there, restructuring the dictionary, and leading to bad performance; the dictionary will just replace the KEY value with the key you previously selected, basically meaning "when you're traversing the dictionary memoryspace, pretend this <key,value> pair does not exist, feel free to overwrite it."

Such a key is also used in dictionaries that pre-allocate space in buckets in a particular manner - you need a key to "initialize" the buckets with instead of having a flag for each entry that indicates whether or not its contents are valid. So instead of having a triple <key, value, initialized> you would have a tuple <key, value> with the rule being that if key == empty_key then it hasn't been initialized - and therefore you may not use empty_key as a valid KEY value.

You can see this sort of behavior in the Google hashtable (dictionary for you .NET people :) in the documentation here: http://google-sparsehash.googlecode.com/svn/trunk/doc/dense_hash_map.html

Look at the set_deleted_key and set_empty_key functions to get what I'm talking about.

I'd wager .NET uses NULL as either the unique deleted_key or empty_key in order to do these sort of nifty tricks that improve performance.

Solution 3

You can't use a null bool? because nullable types are meant to act like reference types. You can't use a null reference as a dictionary key, either.

The reason you can't use a null reference as a dictionary key probably comes down to a design decision at Microsoft. Allowing null keys requires checking for them, which makes the implementation slower and more complicated. For example, the implementation would have to avoid using .Equals or .GetHashCode on a null reference.

I agree that allowing null keys would be preferable, but it's too late to change the behavior now. If you need a workaround you can write your own dictionary with allowed null keys, or you could write a wrapper struct which implicitly converts to/from T and make that the key-type for your dictionary (ie. the struct would wrap the null and handle comparing and hashing, so the dictionary never 'sees' the null).

Solution 4

There is no fundamental reason. HashSet allows null and a HashSet is simply a Dictionary where the key is the same type as the value. So, really, null keys should have been allowed but would be breaking to change it now so we're stuck with it.

Solution 5

Dictionairies (basic description)
A dictionary is the generic (typed) implementation of the Hashtable class, introduced in .NET framework 2.0.

A hashtable stores a value based on a key (more specificly a hash of the key).
Every object in .NET has the method GetHashCode.
When you insert an key value pair into an hashtable, GetHashCode is called on the key.
Think of it: you can't call the GetHashCode method on null.

So what about Nullable types?
The Nullable class is simply a wrapper, to allow null values to be assigned to value types. Basically the wrapper consists of an HasValue boolean that tells if it is null or not, and a Value to contain the value of the value type.

Put it together and what do you get
.NET doesn't really care what you use as a key in a hashtable/dictionary.
But when you add a key value combination, it has to be able to generate a hash of the key.
It doesn't matter if your value is wrapped inside a Nullable, null.GetHashCode is impossible.

The Indexer property and Add methods of the Dictionary will check for null, and throw an exception when it finds null.

View more solutions

Comments

[Jonathan Allen]

Wrong. You can call GetHashcode on a Nullable<bool> set to null. The result is 0.

[Jonathan Allen]

Yes, we already know that. The question is why they choose to implement it that way.

[Fitzchak Yitzchaki]

But in my opinion in this context it does not make sense to ask a dictionary, give me the item that his key is null.

[jeffora]

The question was specific to nullable types and I was highlighting that they behave the same as reference types

[Jonathan Allen]

They don't behave the same. For example, you can get the hascode of a structure null but not a reference null.

[jeffora]

typeof(T).IsValueType will return true for bool? (or any Nullable type) so it is possible to determine if it's a value nullable vs a reference null. Which brings it back to it being an implementation decision

[Alastair Pitts]

This doesn't really answer the question. He wants to know why Nullable is acceptable when one of it's possible values will always throw an exception.

[devuxer]

Look at my example. What doesn't make sense about it?

[andriy]

There's no prohibition against using a type with a stupid implementation of GetHashCode. For instance, you could create your own type that, for GetHashCode, always returns 1, or returns a random value. You could still use this type as a Dictionary key. You shouldn't do that, of course, but that's different from saying you can't.

[Dynami Le Savard]

I never said you can't call GetHashCode()on a Nullable<bool>, I said you can't call GetHashCode() on null.

[devuxer]

@Jonathan, what do you think of Dynami's comment that "you can't call GethasCode() on null"?

[Dynami Le Savard]

@DanM Well, nevermind that. Though not being able to call GetHashCode() on null seemed like an elegant way to put it, I then thought about the fact that you can also provide your own comparer in the ctor of a dictionary, which could not be using the Equals and GetHashCode methods.

[erikkallen]

No, this is wrong. Strings are not interned if they are the result of a computation. Your issue was that byte[] does not override GetHashCode and Equals, so you get reference comparisons, but string does, to provide value comparison.

[Jon Hanna]

You can pass null to an IEQualityComparer's GetHashCode() though, so you can certain get a hash-code for a null.

[ANeves]

@Dynami Le-Savard But you can compare nulls. null == null, null != (bool?)true, null != (bool?)false, etc. In my case I have a bidimensional Dictionary, and one of the indexers is something that can be null. I will need to work around this limitation by design, which is fine. But I would like to understand the limitation, and in this light your answer does not answer OP's question - it just re-states it. We know it cannot be null, but why?

[ANeves]

Insightful. But what about Dictionary<int, object>? It cannot use null as key, and it accepts default(int) as a key; maybe it uses Nullable<int> internally as key instead of int?

[ANeves]

But the hashcode is not, by definition, assuredly unique. public override int GetHashCode() { return 0; } is a valid implementation, even if quite useless. So it would not matter if the Dictionary just internally used an arbitrary hashcode for null values. I'm not convinced this is a good explanation.

[Yvo]

However null does not equal null. Using an arbitrary code for null would result in some unpredictable code.

[ANeves]

I disagree, I believe null equals null. If a==a must return true, then null==null must also return true; no? Also, the example implementation provided in MSDN returns true if both are null. Am I thinking wrongly about this?

[harry]

Well, int is not a nullable type, so you naturally would not be able to use int(null) as a key.

[ANeves]

... yes; let me try to rephrase. So what would then be the "key that will not be used" that would be used to mark the deleted entries? Unless the internal key type is the selected value type boxed into a Nullable<T>, there is no available key as all keys are valid. No?

[harry]

Very good question - you're right. But having a key set aside as empty (and possibly another key as deleted) is an optimization. I obviously know nothing of the internal .NET code and how it's implemented, but a) it's not hard to envision that such an optimization was only used for reference types, and b) possibly completely different implementations of a hashtable are used for value and pointer types internally due to their different requirements and performance characteristics? Just a guess.

[JonnyRaa]

surely that's what you'd expect! Just because two objects have the same values doesn't make them the same object. In c# strings are immutable so all operations actually give you a new string

[Jeff B]

Looking at the source it does set the key to default<TKey> when you remove an entry.... but I'm not sure it uses that to decide whether a spot is free or not (I see a lot of -1 values that I think might do that).

[brandon]

Dictionary uses a hashcode from key.GetHashcode() as the key, not the key value itself (for numbers up to 32 bit hashcode and value are the same). And it uses 31 bits of the hashcode for comparison with 1 sign bit to indicate unset entry locations, hence the -1.

[Triynko]

Null should be allowed as a key. It's hashcode should obviously be zero, and you can compare null to null in C# just fine; they are equal. This is not TSQL with some weird null != null concept. This implementation is terrible. For example, I want to build a tree from a flat list of item->parent relationships, so I want to call items.GroupBy(x => x.ParentId).ToDictionary(x => x.Key, x.ToList()), but I cannot, because the root nodes have null for their ParentId, and although it can GroupBy the value null just fine, it refuses to allow it as a key in a dictionary. Ridiculous. j/k

[Christopher King]

Actually, there is no fundamental reason. HashSet allows null and a HashSet is simply a Dictionary where the key is the same type as the value. So, really, null keys should have been allowed but would be breaking to change it now so we're stuck with it.

[user1496062]

Hashcode are meant to be evenly distributed 0 for null is not hence it stuffs up your bucketing. Not to mention as others have that dictionary is a reference structures and used the memory address .. &null == fault

[Tom Lint]

In my opinion, this should be allowed to be circumvented by a custom IEqualityComparer. The default implementation indeed calls GetHashCode on the passed object, but a custom IEqualityComparer is free to do whatever it wants, as long as it generates hash codes consistent with the rules for GetHashCode(). The only reason for not allowing null-keys is backward compatibility, which to me sometimes feels like a bad thing.