Hello World
Spiga

你的字典里有多少元素?

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

56 条回复

  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真人

  53. rantrism
    43.132.98.*
    链接

    rantrism 2023-04-10 11:00:22

    您好~我是腾讯云开发者社区运营,关注了您分享的技术文章,觉得内容很棒,我们诚挚邀请您加入腾讯云自媒体分享计划。完整福利和申请地址请见:https://cloud.tencent.com/developer/support-plan 作者申请此计划后将作者的文章进行搬迁同步到社区的专栏下,你只需要简单填写一下表单申请即可,我们会给作者提供包括流量、云服务器等,另外还有些周边礼物。

  54. hanababy
    35.215.175.*
    链接

    hanababy 2023-04-28 17:45:31

    Don’t compare your life with others. There’s no comparison between the sun and the moon. They shine when it’s their time. 别拿你的人生和别人的比较。太阳和月亮没有可比性。它们都在属于自己的时刻发光。 Your text to link here... Your text to link here... Your text to link here... Your text to link here...

  55. amel
    35.215.165.*
    链接

    amel 2023-08-04 14:16:10

    一名吴士兴犹未尽,长剑一挥,将一头山羊从头至臀,福彩3D 幸运飞艇 剖为两半,便如是划定了线仔细切开一般,连鼻子也是一分为二,两片羊身分倒左右,剑术之精,实是骇人听闻。七名吴士大声喝彩。范蠡心中也忍不住叫一声:“好剑法!”

  56. Ocean
    35.215.180.*
    链接

    Ocean 2023-11-17 15:27:32

    龙珠体育新闻天空和大海虽然相爱,但却无法实现他们的爱情。他们之间有着难以逾越的距离,无法牵手在一起。天空悲伤地哭泣,他的泪水168体育官网洒在了海面上。即使受到惩罚,天空也义无反顾地将自己的灵魂寄托给了大海。从此以后,大海的蓝色变得比天空更加深邃和美丽。这是一段感人的叶少赛车新闻爱情故事,即使有障碍,他们的爱也依然坚定不移。

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我