论坛 › 源码分享 › c语言实现的哈希表

天马座 发表于 2021-6-26 01:09:44

c语言实现的哈希表

本帖最后由 天马座 于 2021-7-11 02:05 编辑

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//哈希桶数量

#define HASHSIZE (1 << 16)

typedef int Value;

struct list {
        //单链表
        char *key;
        Value value;
        struct list *next;
}
;
//哈希表
struct list *hashList;

Value valuedup(Value value){
        //兼容字符串代码
        return value;

}

struct list *newNode(char* key,Value value) {
        //创建一个新节点
        struct list *p = (struct list *)malloc(sizeof(struct list));
        if (p == NULL)
                return NULL;
        p->key = strdup(key);
        if (p->key == NULL){
                free(p);
                return NULL;
      }
        p->value = valuedup(value);
        //if (p->value == NULL){
      //      free(p->key);
      //      free(p);
        //      return NULL;
      //}
        return p;

}

void freeNode(struct list *p){
      //释放节点
      free(p->key);
      //free(p->value);
       free(p);
}

unsigned int hashCode(char* s) {
        //计算哈希值
        unsigned int h = 0;
        while(*s != '\0')
                h = *s++ + 31 * h;
        return h;
}
int indexOf(char *key) {
        //计算key所在的下标
        return hashCode(key) & (HASHSIZE - 1) ;
}
struct list *listFind(struct list *head, char *key) {
        //链表查找键
        for (struct list *p = head; p != NULL; p = p->next)
                if (strcmp(p->key, key)==0)
                    return p;
        return NULL;
}
struct list *find(char *key) {
        //哈希表查找键
        return listFind(hashList,key);
}
int contains(char *key) {
        //key是否存在
        return find(key) == NULL ? 0 : 1;
}
void add(char *key, Value value) {
        //添加键值对
        int i = indexOf(key);
        struct list *p = listFind(hashList,key);
        if (p == NULL) {
                //插入表头
                struct list *p = newNode(key,value);
                if (p == NULL)
                            return;
                p->next = hashList;
                hashList = p;
        } else{
                Value v = valuedup(value);
                //if (v == NULL)
        //      return ;
      //      free(p->value);
                p->value = v;
      }
}
void removeKey(char *key) {
        //删除一个key
        struct list *del = NULL;
        int i = indexOf(key);
        struct list *p = hashList;
        if (p == NULL) return;
        if (strcmp(p->key, key)==0) {
                del = p;
                hashList = p->next;
        } else {
                for (; p->next != NULL; p = p->next)
                            if (strcmp(p->next->key, key)==0) {
                        del = p->next;
                        p->next = p->next->next;
                        break;
                }
        }
        if (del == NULL) return;;
        freeNode(del);
}
void release() {
        //销毁哈希表
        for (int i = 0; i < HASHSIZE; i++)
                while(hashList != NULL) {
                        struct list *p = hashList;
                        hashList = p->next;
                        freeNode(p);
                }
       
}
void traversal() {
        //遍历哈希表
        for (int i = 0; i < HASHSIZE; i++)
                for (struct list *p = hashList; p != NULL;p = p->next)
                        printf("key = %s   value = %d \n",p->key ,p->value);
               
       
}
void main() {
        add("a",1);
        add("b",2);
        add("c",3);
        traversal();
        removeKey("c");
        traversal();
        release();
}

0xAA55 发表于 2021-6-28 14:04:26

你这哈希表只能有一个实例啊……

Golden Blonde 发表于 2021-6-30 08:03:34

每次看到链表操作之类的代码，就会想起大学时代的C语言课程。

0xAA55 发表于 2021-6-30 08:51:31

美俪女神 发表于 2021-6-30 08:03
每次看到链表操作之类的代码，就会想起大学时代的C语言课程。

哈希表是很有价值的东西，复杂度O(1)的查询速度，缺点是往里面增加数据的时候数组的扩容有个时间成本。

查看完整版本: c语言实现的哈希表