周立功来讲解哈希表的实现

ze, unsigned int key_len,

2                     unsigned int value_len, hash_func_t pfn_hash)

3    {

4        int i;

5        if ((p_hash == NULL) || (pfn_hash == NULL)){ 

6            return NULL;

7        }

8        p_hash -> p_head = (slist_head_t *)malloc(size * sizeof(slist_head_t));

9        if (p_hash -> p_head == NULL) {

10          return -1;

11      }

12      for (i = 0; i < size; i++){

13          slist_init(&p_hash -> p_head[i]);

14      }

15      p_hash -> size           = size;

16      p_hash -> key_len         = key_len;

17      p_hash -> value_len  = value_len;

18      p_hash -> pfn_hash       = pfn_hash;

19      return 0;

20  } 

2. 添加记录

hash_db_add()接口用于向已经初始化的哈希表中添加一条记录，添加一条记录时，需要指定关键字信息和记录值信息，其函数原型定义（hash_db.h）：

int hash_db_add (hash_db_t *p_hash, void *key, const void *value); 

其中，p_hash为指向哈希表实例的指针，key为指向关键字的指针，value为指向记录值的指针。特别地，由于在添加记录时，程序不会修改key和value指针所指向的值，因此，指针都加了const修饰符。以添加一条学生记录为例，使用范例如下：

    student_t stu = {

               "zhangsan",

            'M',

            173.3,

            60

    };

    unsigned char id[6] = {0x20, 0x14, 0x44, 0x70, 0x02, 0x39};

    hash_db_add(&hash_students, id, &stu);

在添加记录函数的实现中，首先需要使用哈希函数找到关键字对应的记录在哈希表中的索引，以确定该条记录所在链表的表头，然后分配一个存储记录的结点空间，将关键字、记录等信息存储在该空间中，然后将结点添加到对应链表的头部（由于记录在链表中的具体位置不重要，因此直接添加在链表头部，效率更高）。函数实现的范例详见程序清单3.64。

程序清单3.64  添加记录函数范例程序

1    int hash_db_add (hash_db_t *p_hash, const void *key, const void *value)

2    {

3        int idx = p_hash -> pfn_hash(key);                  // 使用哈希函数通过关键字得到哈希值

4        // 分配内存，存储链表结点+关键字+记录

5        char *p_mem = (char *)malloc(sizeof(slist_node_t) + p_hash -> key_len + p_hash -> value_len);

6        if (p_mem == NULL) {

7            return -1;

8        }

9        memcpy(p_mem + sizeof(slist_node_t), key, p_hash -> 9        memcpy(p_mem + sizeof(slist_node_t), key, p_hash -> key_len);                  // 存储关键字