Chinaunix首页 | 论坛 | 博客
  • 博客访问: 98786
  • 博文数量: 23
  • 博客积分: 1546
  • 博客等级: 上尉
  • 技术积分: 170
  • 用 户 组: 普通用户
  • 注册时间: 2007-11-18 19:47
文章分类

全部博文(23)

文章存档

2012年(1)

2011年(6)

2010年(3)

2009年(13)

我的朋友

分类:

2011-08-29 23:51:28

读过Linux内核源码的人可能都会发现,其中并没有太多复杂的数据结构,作为基础数据结构的双向链表(list)和基于list实现的hash表占据了绝大部分数据结构。内核为什么会大量使用这两种数据结构呢?围绕这个问题(主要是hash表),我将以自己的理解揣摩一下其意图。

首先,这两种数据结构都十分简单,简单包括理解起来简单使用起来简单两方面内容。这也意味着代码的可读性和可维护性都比其他复杂的数据结构要好,出现bug的风险也较低。从哲学上来讲,这也符合K.I.S.S.条款。

其次,内核是一个比较讲究性能的软件,为了程序设计和维护的简单性而失掉性能,这究竟是不是算得不偿失呢?我们是不是应该将天平更加偏向于性能?已经记不起是在哪里听说过,很多商业的路由软件都是基于二叉树的数据结构来存储路由项,以求得其路由查找的时间复杂度为log(n),并且他批评Linux的路由项组织为hash表,致使性能不佳,不适合商业。确实有一定道理,可仔细分析,hash表的性能真的比二叉树差么?二叉树的插入和删除某一项的时间复杂度都为log(n);hash表插入和删除的时间复杂度最好为O(1),最差为O(n),如果选取的表项(m)足够多,且hash函数足够好的话,其时间复杂度为O(n/m)(当m<=n时)。当m > n / log(n)的时候,hash表的平均表现就比二叉树要好;且当m>=n时,其时间复杂度趋近于O(1)。m的值可以做成可调整的,这也正显示了内核的可定制性。不过,不要盲目乐观,这一切都是以一个足够好的hash函数为前期的。

如何判定一个hash函数的好坏呢?

hash的中文意思是“散列”,可解释为:分散排列。一个好的hash函数应该做到对所有元素平均分散排列,尽量避免或者降低他们之间的冲突(Collision)。有必要再次提醒大家的是,hash函数的选择必须慎重,如果不幸所有的元素之间都产生了冲突,那么hash表将退化为链表,其性能会大打折扣,时间复杂度迅速降为O(n),绝对不要存在任何侥幸心理,因为那是相当危险的。历史上就出现过利用Linux内核hash函数的漏洞,成功构造出大量使hash表发生碰撞的元素,导致系统被DoS,所以目前内核的大部分hash函数都有一个随机数作为参数进行掺杂,以使其最后的值不能或者是不易被预测。这又对hash函数提出了第二点安全方面的要求:hash函数最好是单向的,并且要用随机数进行掺杂。提到单向,你也许会想到单向散列函数md4和md5,很不幸地告诉你,他们是不适合的,因为hash函数需要有相当好的性能

一筹莫展了吧?谁叫你又想闭门造车了!还是看看前辈们是如何做的,充分发扬拿来主义的精神,我又称这种做法为“不战而驱人之兵”,这难道不是兵家之上上策么?Linux内核里面用的jhash是一个久经考验,并被实践证明经得起考验的hash函数,可以CPMS(Copy Paste Modify Save)之。Jhash的作者Bob Jenkins在其上还公布了诸如针对能预知的数据进行hash的hash函数--等一系列其他hash函数,看客们可以选择之,如果有兴趣继续钻研,也可以踏在他们的肩膀上。

Linux内核发展到今天,已经不单单是Linus一个人的功劳,而是全世界人们的集体劳动成果,是人类智慧的结晶。其精妙之处很值得我们细细地品味、慢慢地把玩!

参考资料:
  1. .
  2. .
阅读(831) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~