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

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

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

2. 代码实现

2.1 哈希节点构造体

#define HASHSIZE 10typedef 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.cterence@k8s-master:/mydata/c$ ./a.outset         key:zhangsan val:100     hash:1set         key:zhangsan val:200     hash:1update         key:zhangsan 100 => 200 set         key:lisi     val:200    hash:6set         key:wangwu   val:300     hash:0set         key:maliu    val:400     hash:1set         key:qianer   val:500     hash:5set         key:zhaojiu  val:600     hash:7set         key:sunzi    val:700     hash:4set         key:wangwu   val:3000     hash:0update         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!