技术宅的结界

 找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 790|回复: 3
收起左侧

c语言实现的哈希表

[复制链接]

9

主题

19

帖子

439

积分

用户组: 中·技术宅

UID
5181
精华
3
威望
39 点
宅币
248 个
贡献
79 次
宅之契约
0 份
在线时间
41 小时
注册时间
2019-7-25
发表于 2021-6-26 01:09:44 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有帐号?立即注册→加入我们

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

[C] 纯文本查看 复制代码
#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[HASHSIZE];

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[indexOf(key)],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[i],key);
	if (p == NULL) {
		//插入表头
		struct list *p = newNode(key,value);
		if (p == NULL)
		            return;
		p->next = hashList[i];
		hashList[i] = 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[i];
	if (p == NULL) return;
	if (strcmp(p->key, key)==0) {
		del = p;
		hashList[i] = 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[i] != NULL) {
			struct list *p = hashList[i];
			hashList[i] = p->next;
			freeNode(p);
		}
	
}
void traversal() {
	//遍历哈希表
	for (int i = 0; i < HASHSIZE; i++) 
		for (struct list *p = hashList[i]; 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();
}
回复

使用道具 举报

1088

主题

2606

帖子

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
236
威望
474 点
宅币
21362 个
贡献
45937 次
宅之契约
0 份
在线时间
2059 小时
注册时间
2014-1-26
发表于 2021-6-28 14:04:26 | 显示全部楼层
你这哈希表只能有一个实例啊……

39

主题

219

帖子

7845

积分

用户组: 管理员

UID
77
精华
14
威望
144 点
宅币
7110 个
贡献
158 次
宅之契约
0 份
在线时间
160 小时
注册时间
2014-2-22
发表于 2021-6-30 08:03:34 | 显示全部楼层
每次看到链表操作之类的代码,就会想起大学时代的C语言课程。

1088

主题

2606

帖子

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
236
威望
474 点
宅币
21362 个
贡献
45937 次
宅之契约
0 份
在线时间
2059 小时
注册时间
2014-1-26
发表于 2021-6-30 08:51:31 | 显示全部楼层
美俪女神 发表于 2021-6-30 08:03
每次看到链表操作之类的代码,就会想起大学时代的C语言课程。

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

本版积分规则

QQ|申请友链||Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2021-10-24 03:37 , Processed in 0.034308 second(s), 29 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表