Hello World
Spiga

你的字典里有多少元素?

2014-07-12 23:42 by 老赵, 21166 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

38 条回复

  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. 土鳖程序
    119.248.1.*
    链接

    土鳖程序 2015-11-13 12:03:19

    “土鳖程序”,这是个有意思的说法,有点像小学课本里说的“山药蛋”派作家吧。人在一方面越有知,也说面在另一方面越无知。很多在各自领域做出卓越成就的人,在个人生活为人处世上都是达到了白痴的地步,爱因斯坦,杰克逊,吴清源.... 对于博主深刻钻研的工匠精神我是深感佩服了。但是对于这种奚落面试者的态度,我确十分不能认同。 对于程序设计的细节难以尽数,只要大局观没有问题,对于工作中遇到的细节都可以后天掌握,没必要,用一个具体的知识点,对面试整体水平下定论。 面试本身是种双向选择的阶段,不仅仅是企业挑选员工,对于要求较高像博主这样的人也是在面试企业。如果面试者的态度是如此轻视招到麾下的也只能是平庸之辈,把面试工作交给这样的人企业前景堪忧啊。呵呵。瞎说的别见怪。

  30. Claude
    218.109.251.*
    链接

    Claude 2015-11-20 15:40:51

    从老赵的博客中学习了不少东西,来留个言吧。 老赵怎么不更新博客了,是很忙吗? 我期待着分享一下香港那边的IT工作和生活情况。

  31. root
    114.95.105.*
    链接

    root 2015-12-17 10:59:27

    怎么不更了......

  32. 老赵
    admin
    链接

    老赵 2015-12-17 12:19:22

    @土鳖程序

    是的,我不能让高级人才看到我居然能让土鳖程序员进入公司,这样他们都不敢来了。

  33. 粉丝er
    112.73.26.*
    链接

    粉丝er 2016-02-01 17:13:49

    老赵,太久不写文章不大好啊。写写在美利坚的生活也是好的 :-)

  34. 大笨蛋
    103.16.127.*
    链接

    大笨蛋 2016-06-27 16:41:28

    你怎么不写博客了?

  35. 大笨蛋
    103.16.127.*
    链接

    大笨蛋 2016-06-27 18:10:17

    老赵你要理解不是所有人都有你那么好的脑子的,比如我。有些东西看了很多次理解不了,但是还是要工作,还是要写垃圾代码活下去啊。

  36. JASON
    61.152.150.*
    链接

    JASON 2016-08-17 11:47:20

    老赵怎么不写博客啦? 最近在忙什么呢

  37. 随便说
    119.40.53.*
    链接

    随便说 2016-09-08 17:43:15

    @大笨蛋 同意。我也是个垃圾程序员,在写着垃圾代码。老赵是高级程序员,所以去美国了,所以中国是留不住高级程序员的。哈哈!

  38. PHP程序员雷雪松
    59.173.86.*
    链接

    PHP程序员雷雪松 2016-09-09 17:28:45

    博主的博客很精彩啊,很有内涵。

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我