分类： LINUX
2009-04-09 23:55:14
读过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一个人的功劳，而是全世界人们的集体劳动成果，是人类智慧的结晶。其精妙之处很值得我们细细地品味、慢慢地把玩！
参考资料:
