关于数据结构与算法:数据结构与算法-哈希表-C语言描述

1. 指标：实现一个繁难哈希表

冀望构建一个这样的繁难哈希表：

• √ 长度为 10
• √ 应用 time33 散列函数
• √ key 应用 16 位字符串
• √ data 应用 int
• √ 用单向链表解决哈希碰撞
• X 暂不反对扩容重哈希

2. 代码实现

2.1 哈希节点构造体

#define HASHSIZE 10

typedef struct HashNode {char   key[16];
    int    data;// 数据域
    struct HashNode *next;// 指针域, 哈希碰撞时候的后继结点
} HashNode;

static HashNode *HashTable[HASHSIZE];

2.2 time33散列函数

这里因为要放在长度为 HASHSIZE 的HashTable里，故而对 HASHSIZE 取余

typedef struct HashNode {char   key[16];
    int    data;// 数据域
    struct HashNode *next;// 指针域, 哈希碰撞时候的后继结点
} HashNode;

static HashNode *HashTable[HASHSIZE];

2.3 set函数

• 思考该槽为 NULL 时直接插入
• 思考该槽不为空时，则遍历链表寻找指标key, 找失去就更新, 找不到就尾插新节点

void *set(char *key, int data)
{
    struct HashNode *node;
    unsigned int hash_key = time33(key);
    printf("set key:%s val:%d hash:%d\n", key, data, hash_key);
    
    struct HashNode *new_node;
    new_node = (struct HashNode *)malloc(sizeof(struct HashNode));
    strcpy(new_node->key, key);
    new_node->data = data;
    new_node->next = NULL;
    
    node = HashTable[hash_key];
    // 先看在不在
    if (NULL == node)
    {HashTable[hash_key] = new_node; 
        return NULL;
    }else if(strcmp(node->key, key) == 0){printf("update key:%s %d => %d \n",key,node->data, data);
        //update
        node->data = data;
        free(new_node);
    }else{
        // 碰撞
        while(node->next != NULL){
            node = node->next;
            if(strcmp(node->key, key) == 0){
                //update
                node->data = data;
                printf("update key:%s %d => %d \n",key,node->data, data);
                free(new_node);
            }
        }
        node->next = new_node;
    }
}

2.4 get函数

• 思考该槽为 NULL 时返回NULL
• 思考该槽不为空时，则遍历链表寻找指标key, 找失去就返回该节点, 找不到返回NULL

HashNode *get(char *key)
{unsigned int hash_key = time33(key);
    struct HashNode *node;
    node = HashTable[hash_key];
    while(NULL != node){if (strcmp(key, node->key) == 0)
        {printf("get %s :%d \n", key, node->data);
            return node;
        }
        node = node->next;
    }
    return NULL;
}

2.5 遍历哈希 getAll 函数 用于验证代码

void getAll(){
    struct HashNode *node;
    for (int i = 0; i < HASHSIZE; ++i)
    {if (HashTable[i] != NULL)
        {node = HashTable[i];
            while(node != NULL){printf("%d %s %d \n", i,node->key,node->data);
                node = node->next;
            }
        }        
    }
}

3 测试代码

int main(int argc, char const *argv[])
{set("zhangsan", 100);
    set("zhangsan", 200);//update
    set("lisi", 200);
    set("wangwu", 300);
    set("maliu", 400);
    set("qianer", 500);
    set("zhaojiu", 600);
    set("sunzi",700);
    set("wangwu", 3000);//update
    getAll();
    return 0;
}

Res:

terence@k8s-master:/mydata/c$ gcc hashTable.c
terence@k8s-master:/mydata/c$ ./a.out
set         key:zhangsan val:100     hash:1
set         key:zhangsan val:200     hash:1
update         key:zhangsan 100 => 200 
set         key:lisi     val:200    hash:6
set         key:wangwu   val:300     hash:0
set         key:maliu    val:400     hash:1
set         key:qianer   val:500     hash:5
set         key:zhaojiu  val:600     hash:7
set         key:sunzi    val:700     hash:4
set         key:wangwu   val:3000     hash:0
update         key:wangwu   300 => 3000 
0 wangwu 3000 
1 zhangsan 200 
1 maliu 400 
4 sunzi 700 
5 qianer 500 
6 lisi 200 
7 zhaojiu 600

Done!