Hello World
Spiga

你的字典里有多少元素?

2014-07-12 23:42 by 老赵, 22237 visits

“字典”或者说“哈希表”大家都会用,这真是一个好东西,只要创建了之后就可以不断的丢东西进去,添加删除都是O(1)操作,那叫一个快字了得。不过这里我要再次引用Alan Perlis的名言:“Lisp programmers know the value of everything but the cost of nothing.”,目的是想提醒做事“不要忘记背后的代价”。

上图引自Wikipedia中“Hash table”条目,描述了最常用的“哈希表”实现方式之一,也是.NET中Dictionary<TKey, TValue>所采用的做法。那么就以.NET中的Dictionary实现来举例,它的代价是什么呢?这里的代价主要是其内存开销。

创建Dictionary对象时我们可以传入一个“容量”值,但这并不是它会使用的实际容量。Dictionary内部会找到“不小于该值的最小质数”来作为它使用的实际容量,最小是3。这么做的目的是减少碰撞几率,因为从哈希值定位buckets时会用到取模操作。得到实际容量之后,就会它用来创建int[] bucketsEntry[] entries两个数组,用来实现间接索引(即buckets中保存的其实是entries数组的下标,具体可以参考Reference Source中的实现代码)。

请注意,这个实际容量也是下次rehash之前可以保存的最大元素个数。因此,假如你预计会要保存N个元素,那么就把N传入构造函数吧,这可以避免一次又一次无谓的rehash操作。

因此,即便你只创建了一个空字典,它至少也创建了两个长度为3的数组,再加上其他杂七杂八的字段,一个字典至少也占用了48个字节——还记得“赵人希”公众账号上的第一篇文章《.NET程序性能的基本要领》吗?

事实上,假如是一次初始化之后需要进行多次查找(很常见的模式),也完全可以尝试排序后使用二分查找。甚至在元素数量很少的时候,使用List<KeyValuePair<TKey, TValue>>保存对象,而在需要读写的时候进行线性查找,效率也不会差。尽管这里的时间复杂度会是O(log(N))甚至O(N),但对于实际开发来说,算法除了“时间复杂度”还有“常数”的因素在里面。使用节省内存的实现方式,更可能会影响到GC的效率,这也是托管程序性能重要方面。

尽管如此,但这样的“问题”还是会到处出现。例如《基本要领》里面提到,他们在对Visual Studio和新编译器进行Profiling时,发现有大量的字典只保存了一个元素——甚至是空的。

上周我们在做Profiling时,也发现程序里一个被密集调用的算法使用了字典保持临时状态,但是在绝大部分情况里,这个字典里面只有5到6个元素,此时使用字典就有些得不偿失了。事实上,那个算法在绝大部分情况下,字典里的元素数量都是可以预知的,只有极少数情况下会超出。因此,算法可以修改为:预先获得元素数量,假如小于一个阈值,则使用普通的数组来保存元素,需要时进行线性查找。虽然这个算法还有更激进的优化手段(性能热点怎么优化都不过分),但现在这种则是最容易,也最安全的做法。

而在.NET框架里也用到了类似的实践。例如为了解决之前也在“赵人希”上提到过的死锁问题,我看了PropertyChangedEventManager类的实现,其中便用到了HybridDictionary,内部会根据元素数量来切换使用ListDictionary或哈希表来保存数据。

最后再推荐一篇文章吧:《常用数据结构及复杂度》,里面以.NET里的实现为基础,介绍了常用容器各操作的特征。这东西对于一个合格的程序员来说必须是烂熟于心的。其实这东西也完全不用去背,因为这些基础数据结构和算法实在是太容易理解了,几乎只要知道它是怎样一种结构,各特征都可以很快推断出来。

之前我在微博上抱怨过遇到如何如何不靠谱的面试者,连基本的List<T>是怎么存放元素的都搞不清是怎么一回事,居然还有人说这是在考“背诵”,这些细节不重要云云。对此我只想说:既然你就这点追求,那就一辈子老老实实写那些土鳖程序吧,呵呵呵。

Creative Commons License

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

Add your comment

52 条回复

  1. Bairrfhoinn
    58.247.240.*
    链接

    Bairrfhoinn 2014-07-13 16:27:06

    你好久没有写文章了啊,关注了足足有半年了。

  2. 老赵
    admin
    链接

    老赵 2014-07-13 18:30:18

    @Bairrfhoinn

    懒呗,还有最近微信搞的比较多。

  3. Babylon5
    218.20.43.*
    链接

    Babylon5 2014-07-13 19:27:02

    难得发现RSS订阅中的老赵blog又更新了,今年频率还不错啊,足足更新了3篇!点个赞

  4. allen
    124.200.254.*
    链接

    allen 2014-07-13 20:32:43

    List只用于对象较少?多少?如果是对内存苛刻的程序,需要做时间,空间的权衡;不过现在有多少人还很在乎内存呢,呵呵

  5. seek
    117.79.232.*
    链接

    seek 2014-07-13 22:51:05

    文章对hash这块的解释很不错,但是我没明白在做Profiling的时候,为什么这5,6个value的hash dict成为了热点并且需要优化呢?

  6. 老赵
    admin
    链接

    老赵 2014-07-14 06:08:53

    @seek

    每调用一次就创建一个字典,密集调用呗。

  7. 老赵
    admin
    链接

    老赵 2014-07-14 06:10:05

    @allen

    多“少”需要自己把握,比如HybridDictionary里定义了几个常数,加了注释让人不要轻易修改:

    // These numbers have been carefully tested to be optimal. Please don't change them
    // without doing thorough performance testing.
    private const int CutoverPoint = 9;
    private const int InitialHashtableSize = 13;
    private const int FixedSizeCutoverPoint = 6;
    

    这里又不光是为了省内存,也省时间啊。还有这种情况下省内存就是提升GC效率。

    所以你最多可以说“现在还有多少人在乎性能”,呵呵呵……

  8. 老赵
    admin
    链接

    老赵 2014-07-14 06:13:41

    @Babylon5

    知道我最多一年几篇吗?答案是365篇,刚好平均一天一篇。

  9. Dennis Gao
    12.24.60.*
    链接

    Dennis Gao 2014-07-14 08:59:38

    感谢老赵的推荐,在 RSS 能看到你的更新不容易啊~~

  10. mihooke
    223.64.62.*
    链接

    mihooke 2014-08-19 22:10:54

    赵哥啊,您老的网站搜索框不能用啊,赶紧着修补下吧~ 还有,问下,你的那篇写的关于数组位置颠倒元素的博客在哪呢?我突然有问题了,想回头看看,却找不到了,麻烦赵哥帮我翻出来吧。 谢谢啦。在线等~急~

  11. 链接

    satan.student 2014-08-20 11:00:07

    用你之前给的测对象内存使用的小代码试了一下,泛型版本的Dictionary问题不大。我用List分别存储Key和Value,创建了一个ListDictionary。测试发现两者内存占用差不多。不过也可能是因为List和Dictionary两者用同样的参数进行伸缩……回头有空时候看看原码,试试自己实现的单链表……

  12. 思享家
    123.124.130.*
    链接

    思享家 2014-08-22 09:21:51

    回来打脸!!!回来打脸!!!回来打脸!!!回来打脸!!!还记得你说的赌吗? 回来打脸!!!回来打脸!!!回来打脸!!!回来打脸!!!还记得你说的赌吗? 回来打脸!!!回来打脸!!!回来打脸!!!回来打脸!!!还记得你说的赌吗? http://www.cnblogs.com/helenR/archive/2011/11/19/2255147.html#!comments

  13. 链接

    朱磊 2014-08-22 13:38:06

    @思享家

    是不是该吃药了?

  14. 老赵
    admin
    链接

    老赵 2014-08-24 20:33:36

    @思享家

    看了下,赌什么了?当时不敢赌只敢打嘴炮,现在倒来嚷嚷,只能显得你是缩头啥啥啊。

  15. 嘴炮
    59.104.118.*
    链接

    嘴炮 2014-10-19 17:38:42

    坚定的贴微软标签

  16. 陈晓红
    131.111.184.*
    链接

    陈晓红 2014-11-12 20:51:21

    赵老师您好, 这不是广告留言,我们目前正在联合国外开展开源项目调研,希望了解中国的开源生态环境建设,并提出有效建议。

    调查问卷是我们长期调研中的其中一个部分,可否请您百忙之中填写,并在自己的开源圈子帮助推广扩散?如果您希望了解我们项目的阶段进展,也请您在问卷末尾不吝留下联系方式,便于我们和您保持联系或反馈。

    问卷链接:http://www.sojump.com/jq/3950014.aspx 真诚向您的参与和贡献表示感谢! 清华博士生 剑桥访问学者 Michelle 陈晓红 敬

  17. 夏夜月
    112.224.21.*
    链接

    夏夜月 2014-11-18 21:16:34

    .net开源了! 不知道老赵有没有深入到runtime动刀的需求或者想法呢

  18. test
    1.181.189.*
    链接

    test 2014-12-08 18:00:26

    新博客不错啊,终于找到了,哈哈哈 哈。

  19. 链接

    刘丰 2014-12-31 10:49:06

    老赵用的profiling工具是啥? 或者方法? 求教

  20. 链接

    刘丰 2014-12-31 11:19:21

    关于老赵提到的<常用数据结构的时间复杂度>, 刚才看了下, 有个问题。 文中提到Dictionary的插入操作是O(1), 因为内部实现是链表, 这个我理解。 但是对于插入操作中会涉及到对key的检查(可以看出是链表的循环查找操作),

    for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                    if (add) { 
                        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                    }
                    entries[i].value = value;
                    version++;
                    return;
                } 
            }
    

    从源码看来这个应该是个O(n)的操作吧。

  21. sail
    113.67.73.*
    链接

    sail 2014-12-31 18:02:58

    你的windjs我查了一天,发现了一个bug, 当Wind.compile("async",function(){...})方法里面的行数超过9千行后,就会报堆栈溢出的错误

  22. pongsan
    116.231.144.*
    链接

    pongsan 2015-01-28 09:01:59

    我是初学者。很喜欢你的博客。可是好久没看到你更新博客了。我好期待。期待。

  23. zhao
    222.222.44.*
    链接

    zhao 2015-03-03 15:07:25

    您好赵哥,请教个问题,比如:我要判断一个对象是否为空,aa==null 和null==aa 对性能有区别吗?

  24. 大刀王五
    60.171.110.*
    链接

    大刀王五 2015-05-11 17:13:30

    金融行业怎么样,你以前是不是被北大青鸟坑害过

  25. 渣渣玩意
    106.92.244.*
    链接

    渣渣玩意 2015-05-13 13:39:44

    S.B玩意 就这水平还评价培训机构?渣如狗

  26. coc
    118.193.158.*
    链接

    coc 2015-07-05 07:51:48

    坚定的贴微软标签

  27. ACEr
    106.39.112.*
    链接

    ACEr 2015-07-21 15:38:26

    初学者报道,受益颇多,希望能学到更多知识

  28. 摇八音琴的老乞丐
    113.66.40.*
    链接

    摇八音琴的老乞丐 2015-09-18 01:07:04

    哈欠 还在写这种给beginner看的文章

  29. 175114
    60.207.51.*
    链接

    175114 2015-11-04 02:43:18

    听说你很牛,但是看不出来啊。http://www.175114.com/

  30. bloggerent
    122.175.137.*
    链接

    bloggerent 2018-12-20 21:16:24

    Thank for such Nice Information, Please register and post your worth full article here Website: Article Submission site

  31. 1
    117.68.154.*
    链接

    1 2019-01-31 10:14:09

    11111111111111111111111111111111111111111

  32. 丘八
    182.84.16.*
    链接

    丘八 2019-02-26 12:22:39

    活捉大佬一只

  33. 麻辣
    182.84.17.*
    链接

    麻辣 2019-04-13 23:14:40

    如此好文章一定要留下名啊

  34. dhkd
    222.217.144.*
    链接

    dhkd 2019-07-31 16:57:12

    中通 圆通 顺丰 百世单号购买上单号网www.danhw.com

  35. 斑马会员邀请码
    122.245.225.*
    链接

    斑马会员邀请码 2019-09-16 16:30:48

    学习了 支持一下

  36. bk
    171.110.239.*
    链接

    bk 2019-10-04 11:14:36

    电商专用快递网站www.dh5u.com单号无忧

  37. Youzelin
    101.85.15.*
    链接

    Youzelin 2020-04-05 08:03:38

    请问老赵你现在还更新博客吗?看你博客最新的都只有 2014 年的了。

  38. NH4
    127.0.0.1, 159.65.150.*
    链接

    NH4 2020-05-24 22:18:04

    一个个博客慢慢都不再更新了, 真是遗憾... 可以说话的大环境也是今不如昔了 ZG93bi50ZW5jZW50LnBwLnVh

  39. nijani
    106.198.40.*
    链接

    nijani 2020-07-25 10:26:22

    more useful information especially those who are searching for knowledge

    police exam coaching centre in trichy |

    TNPSC Coaching Centres in madurai |

  40. XiaoFans
    117.157.102.*
    链接

    XiaoFans 2020-10-07 11:31:21

    想知道大佬还活着吗?好几年没更新了

  41. CrackISB
    106.208.21.*
    链接

    CrackISB 2020-11-01 19:39:29

  42. lililala6868
    35.215.136.*
    链接

    lililala6868 2021-02-19 19:59:09

    我是初学者。福彩3D很喜欢你的博客。可是好久没看到你更新博客了北京快3

  43. ppt课件
    36.157.145.*
    链接

    ppt课件 2021-02-22 10:11:26

    非常不错!不过好几年没更新了

  44. 容添下
    116.211.131.*
    链接

    容添下 2021-06-05 14:19:30

    麻雀虽小五脏俱全

  45. 今日头条
    112.2.80.*
    链接

    今日头条 2021-06-18 16:32:23

    文章不错交个朋友

  46. zoroseo2020
    35.215.141.*
    链接

    zoroseo2020 2022-04-28 17:23:22

  47. 自学文库
    182.101.103.*
    链接

    自学文库 2022-05-05 17:27:45

    牛逼克拉斯,这都是啥,没看懂

  48. 会长
    222.128.6.*
    链接

    会长 2022-05-31 13:57:08

    大佬今何在?

  49. rencao
    34.92.139.*
    链接

    rencao 2022-07-23 13:35:40

    中英在2017年庆168SG时时彩开奖结果祝两国建立大使级外交关系45周年时,约翰逊也特地录制视频作为庆祝。在该视频中,约翰逊Your text to link here...表达了对继续加强中英双边关系的期待 [51Your text to link here...

  50. Lucille
    120.29.69.*
    链接

    Lucille 2022-08-26 00:41:55

    In heroes guide for Lords Mobile, there are numerous heroes, and each one has a unique set of skills. Making the ideal squad of heroes from them may be challenging, especially for new players. We'll discuss hero archetypes, present a list of every hero in the game, and offer basic advice on how to use them more effectively in this guide. Lords Mobile has a total of 44 heroes. There are 22 of them that are free to play, which means you can acquire them by finishing in-game tasks or earning in-game money. Two of them are exclusive to in-game events and are known as event heroes. The remaining heroes are "paid"; you can only acquire them by investing actual money.

    Also watch Turbo Driving Racing 3D on PC with Games.lol!

  51. 邱鲜
    221.224.46.*
    链接

    邱鲜 2022-09-28 15:35:36

    大栳,是否有意向为加速工业4.0贡献自己的知识技能?

  52. kericnnoe
    111.242.194.*
    链接

    kericnnoe 2022-12-21 04:05:02

    要玩就要玩第一的DG真人

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我