本文共 2327 字，大约阅读时间需要 7 分钟。
http://blog.csdn.net/fengtaocat/article/details/7025488
Linux内核中实现了一种简单的开散列表。散列表中的每个项都是一个hlist_head结构，hlist_head结构是一个链表的头结点，它的大小是固定的。而在链表中具体保存我们需要的信息。这个链表的实现方式与前文所讲的双向循环链表有所不同。
Linux内核中很多地方都使用了散列的技术，比如为了加快查询特定pid的进程描述符的过程，Linux内核中建立了一个pid_hash的结构，类似的我们还可以发现tcp_hash,inode_hashtable等。
下面我们以pid_hash为例具体说明一下hash的实现细节：
pid_hash的声明：
- static struct hlist_head *pid_hash;
- struct hlist_head {
- struct hlist_node *first;
- };
我们可以看到pid_hash的每个项都是一个链表头，大小为一个指针的size，一般为4字节。我们来看一下链表节点的定义：
- struct hlist_node {
- struct hlist_node *next, **pprev;
- };
注意，这里面向前的指针被定义为了struct hlist_node**类型，实际上pprev指针指向的是前一个结点的next域。为什么这样设计呢？
原因：
首先我们假设一下pprev域修改为struct hlist_node* prev，那么现在这个链表和我们平时所见到的一样了。我们考虑下这个链表的头结点，它一定会是struct hilist_node类型的，否则第二个节点的prev无法指向它；而在看一下我们现在的实现，pprev只需要指向hlist_head类型的域即可（比如hlist_head中的first），这就意味着头结点不需要是hlist_node类型。而hlist_node和hlist_head的区别在哪里，少了一个指针！这就意味着节省了hash表的空间。
pid_hash的初始化是在内核初始化时(即start_kernel函数中)进行的，具体由pidhash_init函数完成。
- void __init pidhash_init(void)
- {
- int i, pidhash_size;
-
- pid_hash = alloc_large_system_hash("PID", sizeof(*pid_hash), 0, 18,
- HASH_EARLY | HASH_SMALL,
- &pidhash_shift, NULL, 4096);
- pidhash_size = 1 << pidhash_shift;
-
- for (i = 0; i < pidhash_size; i++)
- INIT_HLIST_HEAD(&pid_hash[i]);
- }
alloc_large_system_hash是专门用于为hash表分配一块连续的内存的，参数4096意味着最多4K个项，也就是最多占用1页的内存。INIT_HLIST_HEAD是负责链表节点的初始化的宏。
那么下一个重要的问题，hash函数是如何实现的呢？非常简洁。
- #define pid_hashfn(nr, ns) \
- hash_long((unsigned long)nr + (unsigned long)ns, pidhash_shift)
其中，nr是pid的值，而ns表示的是pid的命名空间（这个是为了支持轻量级虚拟化而引入的新概念）。我们具体看一下hash_long的实现：
- #if BITS_PER_LONG == 32
- #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32
- #define hash_long(val, bits) hash_32(val, bits)
- #elif BITS_PER_LONG == 64
- #define hash_long(val, bits) hash_64(val, bits)
- #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64
- #else
- #error Wordsize not 32 or 64
- #endif
- static inline u32 hash_32(u32 val, unsigned int bits)
- {
-
- u32 hash = val * GOLDEN_RATIO_PRIME_32;
-
-
- return hash >> (32 - bits);
- }
hash函数的原理就是乘一个非常大的数GOLDEN_RATIO_PRIME_32（会导致溢出），然后只使用了部分的高位最为结果。这个hash函数非常简洁，计算很快。但是hash结果如何取决于GOLDEN_RATIO_PRIME_32的选取。这个值接近黄金分割数会使得hash的结果最好。实际中Linux内核选取了0x9e370001UL这个值，因为它接近黄金分割数并且容易计算0x9e370001UL = 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1。