Hello World
Spiga

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

2012-12-29 02:26 by 老赵, 6634 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

26 条回复

  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

  20. Rohit
    103.134.101.*
    链接

    Rohit 2021-02-06 17:18:48

    good one keep it up Your text to link here...

  21. karthik
    157.51.128.*
    链接

    karthik 2021-08-04 16:10:39

    Attendance Management keeps track of your employee hours. It is the system you use to document the time your employees work and the time they take off. Attendance Management can be done by recording employee hours on paper, using spreadsheets, punching time cards, or using online attendance software for your company. https://www.infobrez.com/attendance-management-software

  22. chiyo
    157.49.163.*
    链接

    chiyo 2021-09-14 22:19:22

    AWS Certification Training in Chennai helps you to become expert in 100+ AWS Services Such as Compute, Containers, Storage, Database, Migration & Transfer, Networking, Content Delivery and more with Classroom and Online Learning Options. https://www.besanttechnologies.com/training-courses/cloud-computing-training/amazon-web-services-training-institute-in-chennai

  23. chiyo
    157.49.163.*
    链接

    chiyo 2021-09-14 22:20:46

    Learn Python Training in Chennai from Python Experts. Build your Career in Python Programming. It’s a Right time to learn Python Course from Basic to Advanced level with Placements. Python Programmers are some of the highest Paid in the industry, with average Salaries over $100000. This Python Certification Training will help you to get a valid lifetime industry-recognized Credential and become a best Python Developer! https://www.besanttechnologies.com/training-courses/python-training-institute-in-chennai

  24. dev padikal
    157.49.137.*
    链接

    dev padikal 2021-09-21 00:50:41

    Brands N Behind is Chennai's most trusted ad Agency & Digital Marketing Company. We are based in Chennai & We provide a complete range of marketing & branding services.

    https://www.brandsnbehind.com/

  25. dev padikal
    157.49.137.*
    链接

    dev padikal 2021-09-21 00:52:41

    Brands N Behind is Chennai's most trusted ad Agency & Digital Marketing Company. We are based in Chennai & We provide a complete range of marketing & branding services.

    At Brands N Behind providing the expected work in the given deadline has helped us in enhancing our credibility in the market. We are a team of creative yet smart people who understand the importance of implementing innovation in work. We have always helped our client’s business to foster and reach up to unmatchable heights.

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

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我