模拟linux内核哈希表

原创作品，敬请转载，转载时请务必以超链接形式标明出处。欢迎讨论。

一.linux源码中，提供了方便哈希表创建和使用的结构体和API。他们在源码中的位置和定义如下：

   1./include/linux/types.h文件中有两个结构体:

    

struct hlist_head {
        struct hlist_node *first;
 };
 struct hlist_node {
       struct hlist_node *next, **pprev;
 };

   2./include/linux/list.h文件中实现了操作哈希表的API。这里不予以列举。有需要看源码哦。

二.一个哈希表的实例（相信大家在数据结构书中都遇见过)。

   1.问题描述：将关键字 {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}，用H(x)=x % P,散列到

哈希表中，使用链地址法处理冲突。

   2.hash.h文件中描述了这一实例。
     

#include <linux/types.h>
/*H(k) = k%p
 *@ p<=m,m哈希表的长度
*/
#define NR_HASH 13      /*m*/
#define  P 13           /*p*/
#define NR_KEYS 12      /*keys number*/

#define hashfn(x)       ((x)%(P))               /*hashfn*/

int keys[NR_KEYS] = {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79};   /*关键字
*/

struct hash_term        /*哈希表项*/
{
        int key;
        struct hlist_node list;
};
struct hlist_head  hash[NR_HASH];                       /*哈希表*/

   3.hash.c是一个内核模块程序，实现了哈希表的创建，散列和遍历。
     

#include <linux/types.h>

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>

#include "hash.h"
static int __init lkp_init(void)
{
        int i;
        int addr;
        struct hash_term *p;
        struct hash_term *tpos;
        struct hlist_node *pos;

        for(i=0; i<NR_HASH; i++)
        {
                INIT_HLIST_HEAD( &hash[i] );    /*初始化哈希表*/
        }

        for(i=0; i<NR_KEYS; i++)
        {
                addr = hashfn(keys[i]);         /*由哈希函数获得地址*/

                p = (struct hash_term *)kmalloc(sizeof(struct hash_term), GFP_KERNEL);  /*动态申请内核内存*/
                p->key = keys[i];
                hlist_add_head(&p->list, &hash[addr]);          /*头插法存放关键字节点*/
        }

        for(i=0; i<NR_HASH; i++)                /*输出哈希表*/
        {
                printk("print hash table:\n");
                printk("%d\t",i);
                hlist_for_each_entry(tpos, pos, &hash[i], list){
                        printk("%d\t",tpos->key);
                }
                printk("^\n");
}

        return 0;
}

static void __exit lkp_cleanup(void)
{
        struct hlist_node *pos;
        struct hlist_node *n;
        int i;

        printk("destroy hash table....");               /*释放内存*/
        for(i=0; i<NR_HASH; i++)
        {
                hlist_for_each_safe(pos, n,  &hash[i]){
                        kfree(pos);
                }
        }
}
module_init(lkp_init);
module_exit(lkp_cleanup);
MODULE_LICENSE("GPL");

4.接下来就是编写Makefile文件，执行make命令，插入模块并观察运行结果等等。