Hello World
Spiga

你的字典里有多少元素?

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

41 条回复

  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. darklx
    180.157.95.*
    链接

    darklx 2016-12-27 22:39:25

    好久没更了~

  39. terry
    210.51.195.*
    链接

    terry 2016-12-28 11:07:17

    好久没更了~

  40. grades
    222.124.121.*
    链接

    grades 2017-09-18 16:22:14

    GRADES cleaning service bandung didirikan untuk melayani dan memberikan jasa pembersihan rumah Bandung, adapun kami memfokuskan diri pada jasa membersihkan rumah bandung, apartemen dan perkantoran. Grades sangat unik, bukan hanya sebagai cleaning service bandung namun juga housekeeping, jasa kebersihan di bandung dengan standard setara hotel yang disesuaikan dengan standard Grades Home Cleaning yang sudah di akui terbaik di bandung Tenaga kerja kami adalah tenaga yang terlatih dan Bersertifikat Cleaning Service, demikian pula dengan peralatan dan chemical yang kami gunakan sangat berkualitas dan ramah lingkungan.

  41. anchen
    27.195.175.*
    链接

    anchen 2017-09-23 18:01:31

    如果您需要为您的网站增加打赏功能,欢迎使用7支付 https://7-pay.cn

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我