Hello World
Spiga

NullableKey:解决Dictionary中键不能为null的问题

2012-12-29 02:26 by 老赵, 5717 visits

众所周知,.NET中Dictionary的键不能为null,否则会抛出NullReferenceException,这在某些时候会显的很麻烦。与此相对的是Java中的HashMap支持以null为键,则方便许多。尽管null的确不是个好东西,但它既然已经存在,既然给我们造成了麻烦,我们就要想办法去解决它。实现一个自己的字典类自然可行,但要精心实现一个高效的字典并不是件容易的事情,例如BCL中的Dictionary.cs就有超过2000行代码。此外另一个容易想到的方法便是实现IDictionary接口,将大部分实现委托给现成的Dictionary类来完成。不过,这相比我在这里要提出的方法还是显得太复杂了。

在编程语言中引入null其实是件很自然的事情,因为我们都在冯诺依曼机上进行开发,内存的访问方式便是“地址”,于是便有了nullNIL等类似的事物来表示一个指针没有指向任何一块地址,但与之相伴的便是各类错误。毕竟null这玩意儿过于透明,编译器在许多时候没法通过静态分析来检查出问题,所以在一些“非冯模型”的编程语言里都会避免使用null。例如在Haskell中,就使用Maybe这种数据类型来代替null。假如在C#中来模拟Maybe的话,其实就类似于:

public abstract class Maybe<T> { }

public sealed class Nothing<T> : Maybe<T> {
    public static Nothing<T> Instance = new Nothing<T>();

    private Nothing() { }
}

public sealed class Just<T> : Maybe<T> {
    private readonly T _value;

    public Just(T value) {
        _value = value;
    }

    public T Value { get { return _value; } }
}

Maybe类型中没有null,“有值”则是Just,“无值”则是Nothing。而TMaybe<T>并不兼容,再获取一个Maybe<T>类型的数据之后,则必须在逻辑分支里对NothingJust两种情况进行处理,于是就不会出现NullReferenceException。从理论上说,我们也可以使用这种方式来解决Dictionary中键不能为null的问题,只要用Dictionary<Maybe<TKey>, TValue>来代替Dictionary<TKey, TValue>即可,但实际上这种方式还是有两个缺点:

  1. 我们还是可以向字典的键传递null。不过幸运的是,编译器不会把TKeynull当做Maybe<TKey>null来使用,因此更大的问题在于:
  2. 除了Nothing以外,我们每次都要创建一个新对象,每个新对象都占用两个额外的字长(即8个或16个字节),这对GC来说会带来压力。

不过以上两个问题的解决办法也是显而易见的,那就是使用struct来代替class。在C#中有两个常被忽视,但对于性能有莫大关系的能力,一是unsafe代码,二便是可自定义的struct类型。struct不会对GC造成压力,并且不会占用额外的内存,可能唯一的问题便是用作泛型时会生成一份额外的可执行代码,且无法继承了。

无法继承没有关系,其实我们也不需要严格按照Maybe的数据模型来实现,只要能够解决问题即可。例如,我们可以使用这么一个NullableKey类型:

public struct NullableKey<T> {
    private readonly T _value;

    public NullableKey(T value) {
        _value = value;
    }

    public T Value {
        get { return _value; }
    }
}

重载了GetHashCodeEquals方法以后,我们便可以使用NullableKey<T>来代替普通的T作为Dictionary的键。更有意思的是,我们可以为定义Nullable<T>T之间的隐式转换,这样在很多场合下可以方便我们编写代码,例如:

var dict = new Dictionary<NullableKey<string>, int>();
dict[null] = 1;

foreach (string key in dict.Keys) {
    Console.WriteLine(key ?? "<null>");
}

由于Dictionary还支持使用自定义的IEqualityComparer类型,因此我也提供了一个配套的NullableKeyEqualityComparer<T>类,可以用来封装一个自定义的IEqualityComparer<T>,并提供IEqualityComparer<NullableKey<T>>的功能,例如:

var stringComparer = StringComparer.OrdinalIgnoreCase; // IEqualityComparer<string>
var keyComparer = new NullableKeyEqualityComparer<string>(stringComparer);
var dict = new Dictionary<NullableKey<string>, int>(keyComparer);

NullableKeyNullableKeyEqualityComparer的代码我已经提交至GitHub里的Tmc项目里。所谓Tmc,即缩写之The Missing Collections,我会放一些平时较为常用的,但BCL以及Power CollectionsC5等常用第三方类库所没有提供的集合。东西不会多(毕竟已经有BCL和第三方类库了),但总比每次都重写要好。也希望大家也可以帮我审阅代码,尤其要着重检查效率方面的问题。毕竟是通用类库,我希望可以在效率方面也有很好的保证。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

20 条回复

  1. 苏理
    118.195.65.*
    链接

    苏理 2012-12-29 08:49:53

    真是困惑 - - 我从来不搞.net开发,不知道做这个是否有意义。现在互联网这个领域很少用微软的asp/.net/windows server技术吧?

  2. 老赵
    admin
    链接

    老赵 2012-12-29 10:06:42

    @苏理

    奇怪,既然觉得没人用.NET,自己也从来不搞.NET,那么你还困惑个毛?

    还是你说做NullableKey没有意义?那就更奇怪了,你用不着,那还不许我用得着嘛?

  3. gsralex
    182.127.158.*
    链接

    gsralex 2012-12-29 14:58:44

    就算互联网不用(你说的),unity3d也用c#(支持xbox360,wii,ps3,android,ios,wp)游戏开发,sony psv 的sdk主打也是c#。 c#还是很多人愿意用的:)

  4. waynebaby
    116.226.211.*
    链接

    waynebaby 2012-12-29 15:10:32

    我还是真么用过 Nullable与T之间的隐式转换>_< 看代码去

  5. waynebaby
    116.226.211.*
    链接

    waynebaby 2012-12-29 15:12:42

    public static implicit operator T(NullableKey<T> key) {
        return key._value;
    }
    
    public static implicit operator NullableKey<T>(T value) {
        return new NullableKey<T>(value);
    }
    

    重载操作符 n年才用一次 >_<

  6. 老赵
    admin
    链接

    老赵 2012-12-29 15:23:37

    @waynebaby

    是啊,很少用,像这里对于编程体验很有帮助时才用。

  7. cdyhe
    183.17.156.*
    链接

    cdyhe 2012-12-29 15:31:41

    对,没错。有时候真的希望空键,有一个“默认值”,而不是抛出NullReferenceException

  8. 老赵
    admin
    链接

    老赵 2012-12-29 15:36:48

    @cdyhe

    这里不是什么“默认值”,“默认值”其实也不一定是好事。这里只是方便了那些null是“合法值”的情况,而不是“默认值”。

  9. seek
    165.146.67.*
    链接

    seek 2012-12-29 18:02:12

    在什么样的场景下会适用null作为key呢?

  10. 周翀
    218.93.195.*
    链接

    周翀 2012-12-29 21:14:05

    @seek

    为一个单参数函数外面套一个计算结果的cache,Dictionary的Key是函数传入值,Value是曾经的计算结果。如果这个参数是引用类型,就有可能为null,而我们不需要关心里面的函数是否也为null准备了计算结果,我们直接缓存/返回结果就行了。

  11. 老赵
    admin
    链接

    老赵 2012-12-29 23:58:10

    @seek

    很多情况,只要同时满足 1) 需要用值来映射某个东西 2) null是一个合法的值。

  12. Juvy
    123.98.102.*
    链接

    Juvy 2013-01-03 10:52:34

    你只是怕抛出NullReferenceException异常是吗?如果是这样的话,将Dictionary的Add方法进行一次封装,在封装的方法中进行判空处理,不知道这样是否可以解决问题?

  13. 老赵
    admin
    链接

    老赵 2013-01-03 22:43:56

    @Juvy

    能不能先看看文章,然后想想清楚甚至模拟写几行代码,最后再来支招呢?

  14. jerry
    114.212.81.*
    链接

    jerry 2013-01-04 01:33:03

    另外,其实这种策略是一种双刃剑:

    默认的Dictionary不允许放入null,所以在每次存入或者用外部来的Key索引的时候必须要检查,否则exception,但遍历输出我们就不关心了,总是好的数据...

    换成nullable的策略后我们不再关心进入的是什么,但在我们遍历输出所有Key的时候我们就必须要检测了,因为就像你上面代码一样,很多时候我们要输出的特殊值不能放在KeyValuePair里面...这个检测时在循环内,所以...当然,Dic的用法应该多数都是查找而不会遍历所以这个问题也应该不大...

    说实话,个人不喜欢这种有强烈C++风格的扩充,比如 foreach (string key in dict.Keys)这里已经不能再使用var Key了

    不可能有一门语言十全十美吧...

  15. 老赵
    admin
    链接

    老赵 2013-01-04 19:16:51

    @jerry

    没搞懂这个跟检查不检查啥关系,这个只是一个数据结构的策略,null也可以是正常值啊。支不支持null的确是一种选择,但这个跟你说的检查没有关系。

    还有,这个跟语言更没有关系了,不知道为什么好多人都要混起来说……

  16. jerry
    114.212.81.*
    链接

    jerry 2013-01-04 19:25:54

    我说编程语言语言是因为你一上来的“在编程语言中引入null其实是件很自然的事情 blah blah.....”

    我说的检查是这个意思,比如 dict[inputKey] = 1; 这里的inputKey可能是null,我们不需要检查,但如果有输出的需求,我们一般又而不是直接输出里面存的key null 或者 value 1而是需要像你写的那样 Console.WriteLine(key ?? ""); 这里的检查必不可少

  17. 老赵
    admin
    链接

    老赵 2013-01-05 11:40:57

    @jerry

    你还是搞混了,在某些编程语言里引入null的确是很自然的事情,但这个跟Dictionary是不是支持null无关。我明白你的意思,但Console.WriteLine(key ?? "<null>")也跟检查毫无关系,别把两个东西混在一起说。

    检不检查null是具体业务需求,某个业务把null当做不合法的值那就需要检查,但某个业务也可能把-1"Hello World"当做不合法的、待检查的值,而null反而是合法的。再好好想想吧,别自然而然地把null当做一种特别的、不合法的、待检查的东西,它其实也只不过是一个普通值而已。

  18. 链接

    Haart 2013-01-05 17:02:17

    @jerry

    你举的这种例子中,确实需要进行检查。但是并非所有以null作为key的字典中,都需要将key输出

    也就是:在某些业务需求中,null是一个合理的key值,在这种业务需求中,我们不需要将key输出,也不需要对key进行取成员操作,也不需要将key参与运算,总之,一个null的key值不会造成任何问题,并且null也确实具有其合理的业务含义。那么这种情况下,引入null作为key值就是合情合理的了。

  19. dannybaobei7
    132.188.64.149, 132.188.64.*
    链接

    dannybaobei7 2015-10-09 17:52:50

    再看这篇文章已经是两年以后了, 惭愧, 我是看完了swift 和scala的pattern match才明白为啥要这么干的, 老赵的做法其实就是一种pattern match

已自动隐藏某些不合适的评论内容(主题无关,争吵谩骂,装疯卖傻等等),如需阅读,请准备好眼药水并点此登陆后查看(如登陆后仍无法浏览请留言告知)。

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我