Why can't you use null as a key for a Dictionary?

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?

Answer 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 example of a possible workaround, you can try something similar to Need an IDictionary implementation that will allow a null key

Answer 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.

Answer 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).

Answer 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.

Answer 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.

Answer 6

Not using null is part of the contract according to the MSDN page: http://msdn.microsoft.com/en-us/library/k7z0zy8k.aspx

I guess the reason is that having null as valid value will just complicate the code for no reason.

Answer 7

Key value must to be unique, so null cannot be a valid key because null indicate no key.

That why .Net framework doesn't allow null value and throw an exception.

As far as why Nullable allowed, and not catches at compile time, I think the reason is because that where clause that allow everyt T except Nullable one is not possible (at least I don't know how to achieve that).

Answer 8

Ah, the problems of generic code. Consider this block via Reflector:

private void Insert(TKey key, TValue value, bool add)
{
    int freeList;
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

There is no way to rewrite this code to say "Nullable nulls are allowed, but don't allow reference types to be null".

Ok, so how ab out not allowing TKey to be a "bool?". Well again, there is nothing in the C# language that would allow you to say that.

Answer 9

Dictionaries can't accept null reference types for a variety of reasons, not least because they don't have a GetHashCode method.

A null value for nullable value type is meant to represent a null value – the semantics are meant to be as synonymous with a reference null as possible. It would be slightly odd if you could use null nullable value where you couldn't use null references just because of an implementation detail of nullable value types.

Either that or Dictionary has:

if (key == null)

and they never really thought about it.

Answer 10

Dictionary keys can't be null in .NET, regardless of the type of the key (nullable or otherwise).

From MSDN: As long as an object is used as a key in the Dictionary<(Of <(TKey, TValue>)>), it must not change in any way that affects its hash value. Every key in a Dictionary<(Of <(TKey, TValue>)>) must be unique according to the dictionary's equality comparer. A key cannot be null reference (Nothing in Visual Basic), but a value can be, if the value type TValue is a reference type. (http://msdn.microsoft.com/en-us/library/xfhwa508.aspx)

Answer 11

I've just been reading up on this; and as Eric replied, I now believe this is incorrect, not all strings are automatically Interned, and I needed to override the equality operation.

---

This bit me when I converted a dictionary from using a string as a key to an array of bytes.

I was in the vanilla C mindset of a string simply being an array of characters, so it took me a while to figure out why a string built by concatenation worked as a key for lookups while a byte array built in a loop did not.

It's because internally .net assigns all strings that contain the same value to the same reference. (it's called 'Interning')

so, after running:

{
string str1 = "AB";
string str2 = "A";
str1 += "C";
str2 += "BC";
}

str1 and str2 actually point to the exact same place in memory! which makes them the same onject; which allows a dictionary to find an item added with str1 as a key by using str2.

while if you:

{
char[3] char1;
char[3] char2;
char1[0] = 'A';
char1[1] = 'B';
char1[2] = 'C';
char2[0] = 'A';
char2[1] = 'B';
char2[2] = 'C';
}

char1 and char2 are distinct references; if you use char1 to add an item to a dictionary, you cannot use char2 to look it up.