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 内核源码的人可能都会发现，其中并没有太多复杂的数据结构，作为基础数据结构的双向链表 (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 时)。当 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 函数 – 完美(perfect)hash 函数等一系列其他 hash 函数。
bucket 的英文解释：
Hash table lookup operations are often O(n/m) (where n is the number of objects in the table and m is the number of buckets), which is close to O(1), especially when the hash function has spread the hashed objects evenly through the hash table, and there are more hash buckets than objects to be stored.

可以这样理解：

· 一个 HASH 的结果所对应的地址可存放两个 BUCKET。可解决 HASH 冲突。

· 要存数据时，第一次 HASH 到这里，在第一个 BUCKET 存放一个数据。

· 要存数据时，当第二次因某些原因 HASH 到这里时，在第二个 BUCKET 存放另一个数据。

一个由 5 个 buckets 组成的哈希表，里面有 7 个元素：

linux 的 hash 函数 hash_long 等，用了 golden ratio 来计算。因为桶 (bits) 的数量需要由 hash 函数和对冲突的期望来决定，那么对于 hash_long 这样的 hash 函数，我们怎么确定桶的数量呢？
一般情况下都是自己根据数据特性来考虑使用的 hash 算法，不是千篇一律咬死一个不放，比如存放 IP 地址的 hash table，用一个 65536 的桶就很好，把 IP 的后 16bit 作为 key。这种方法绝对比 hash_long、jhash 等函数的碰撞率低。
其实就是这个界和性能的折中。我可以取我问题空间的最大值。这样肯定能保证键值分散。但是这样会浪费很多空间。然而取得太小，又影响查找效率。感觉还是要在试验中进行测试。而且 hash 比其他搜索的数据结构灵活的地方就是它的可定制性。可以根据具体情况调整，以达到最优的效果。

阿里云 2 核 2G 服务器 3M 带宽 61 元 1 年，有高配

腾讯云新客低至 82 元 / 年，老客户 99 元 / 年

代金券：在阿里云专用满减优惠券