Linux内核中的hash与bucket简单介绍
哈希函数(Hash Function)为根据索引键来返回数值哈希程序代码的算法。索引键(Key)是被存储对象的某些属性值(Value)。当对象加入至 Hashtable时，它存储在与对象哈希程序代码相符的哈希程序代码相关的Bucket中。当在Hashtable内搜寻值时，哈希程序代码会为该值产生，并且会搜寻与该哈希程序代码相关的Bucket。例如，student和teacher会放在不同的Bucket中，而dog和god会放在相同的 Bucket中。所以当索引键是唯一从Hashtable获取元素的性能时表现会较好。Hash的四大优点如下所示。 · 事先不需要排序。 · 搜寻速度与数据多少无关。 · 数字签名的密码技术保密性(Security)高。 · 可做数据压缩(Data Compression)，以节省空间。 Linux内核里的哈希表应用非常广泛，PHP内核里大部分语言特性也是基于哈希表实现的。为什么哈希表能这么神通广大?哈希表能够实现高效的数据存储和查找，而存储和查找是编程中应用最广泛的两个操作。 Linux内核里的哈希表 读过Linux内核源码的人可能都会发现，其中并没有太多复杂的数据结构，作为基础数据结构的双向链表(list)和基于list实现的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 / log(n)的时候，hash表的平均表现就比二叉树要好;且当m>=n时，其时间复杂度趋近于O(1)。m的值可以做成可调整的，这也正显示了内核的可定制性。不过，不要盲目乐观，这一切都是以一个足够好的hash函数为前期的。 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…