C实现的hash table动态关联数组

动态关联数组中的元素是一系列键值对，实现关联数组的数据结构有binary search tree和hash table。在大多数高级语言中，都有现成的关联数组， 如c++和golang中的std::map和map。这里在c中实现hash table和char* 到 char* 的关联数组。

1. 添加文件hash_tbl.h和hash_tbl.c

//hash_tbl.h
#ifndef HASH_TBL_H
#define HASH_TBL_H

#define INIT_BUCKET_NUM  40

typedef struct hash_node{
    char              *key;
    char              *val;
    struct hash_node  *next;
}hash_node;

typedef struct hash_tbl{
    int              bucket_num;
    int              node_num;
    hash_node        **buckets;
}hash_tbl;

void init_hash_tbl(hash_tbl *tbl);
#endif

//hash_tbl.c
#include "hash_tbl.h"
#include "comm.h"

void init_hash_tbl(hash_tbl *tbl){
    tbl->bucket_num = INIT_BUCKET_NUM;
    tbl->node_num = 0;
    tbl->buckets = calloc(tbl->bucket_num, sizeof(hash_node*));
    if(!tbl->buckets)
        err_exit(MEM_ERR);
}

• （1）哈希节点定义了哈希表中的元素
• （2）利用链表来解决哈希寻址冲突的问题，即将冲突的哈希节点挂在链表的尾部
• （3）为哈希表分配了40个桶，每一个桶对应一个哈希节点链表

2. 向哈希表中插入节点

//hash_tbl.c
void insert_hash_tbl(hash_tbl *tbl, const char *k,
    const char *v){
    hash_node *item = new_hash_node(k, v);
    int ix = hash_func(k, HT_BASE, tbl->bucket_num);

    if(!tbl->buckets[ix]){
        tbl->buckets[ix] = item;
    }else{
        hash_node dummy = {NULL, NULL, NULL};
        dummy.next = tbl->buckets[ix];
        hash_node *prev = &dummy;

        while(prev && prev->next){
            //update node if key exists
            if(prev->next->key && 
              strcmp(prev->next->key, k) == 0){
                item->next = prev->next->next;
                del_hash_node(&(prev->next));
                prev->next = item;
                return;
            }
            prev = prev->next;
        }
        //link the new node
        prev->next = item;
    }
    tbl->node_num++;
}

• （1）通过哈希函数计算得出桶的索引，新建哈希节点用以描述键值对
• （2）若桶对应的链表为空，用新哈希节点作为链表的头
• （3）若桶不为空，遍历链表，如存在重复键，替换哈希节点，否则节点添加到链表尾部

3. 在哈希表中搜索键，返回值

//vector.c
char *search_hash_tbl(hash_tbl *tbl, const char *k){
    int ix = hash_func(k, HT_BASE, tbl->bucket_num);
    hash_node *prev = tbl->buckets[ix];
    while(prev){
        if(prev->key && strcmp(prev->key, k) == 0){
            return prev->key;
        }
        prev = prev->next;
    }
    return NULL;
}

• （1）搜索的过程与插入过程类型，若存在键，返回对应的值，若不存在，返回空指针

4. 从哈希表中删除键值对

//vector.c
void del_key_hash_tbl(hash_tbl *tbl, const char *k){
    int ix = hash_func(k, HT_BASE, tbl->bucket_num);
    hash_node dummy = {NULL, NULL, NULL};
    dummy.next = tbl->buckets[ix];
    hash_node *prev = &dummy;
    while(prev && prev->next){
        if(prev->next->key && 
           strcmp(prev->next->key, k) == 0){
            hash_node *next = prev->next->next;
            del_hash_node(&(prev->next));
            prev->next = next;
            tbl->node_num--;
            break;
        }
        prev = prev->next;
    }
    tbl->buckets[ix] = dummy.next;
}

• （1）删除键值对的过程类似于从链表中删除一个节点

5. 添加测试用例

//vector.c
void test_hash_tbl(){
    hash_tbl tbl;
    init_hash_tbl(&tbl);
    char key[125], val[125];
    for(char c = 'a'; c <= 'z'; c++){
        sprintf(key, "%c", c);
        sprintf(val, "%c", c + 'A' - 'a');
        //printf("insert %s-%s\n", key, val);
        insert_hash_tbl(&tbl, key, val);
    }

    for(char c = 'a'; c <= 'f'; c++){
        sprintf(key, "%c", c);
        if(search_hash_tbl(&tbl, key)){
            sprintf(val, "%s", search_hash_tbl(&tbl, key));
            printf("%s-%s\n", key, val);
        }
        del_key_hash_tbl(&tbl, key);
    }

    reset_hash_tbl(&tbl);
}

• （1）建立大小写字符串键值表
• （2）在哈希表中检索部分键，同时进行删除

代码清单：https://github.com/KevinACoder/Learning/tree/master/ds