当前位置: 首页 > news >正文

C语言手撕一个Hash表(HashTable)

什么是Hash Table

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

散列函数

散列函数是将我们想插入的节点散列成一个数值的函数。它是一个函数。我们可以把它定义成 hash(key),要想找到一个不同的 key 对应的散列值都不一样的散列函数,几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法,也无法完全避免这种散列冲突。而且,因为数组的存储空间有限,也会加大散列冲突的概率。

所以我们几乎无法找到一个完美的无冲突的散列函数,即便能找到,付出的时间成本、计算成本也是很大的,所以针对散列冲突问题,我们需要通过其他途径来解决。

散列冲突

开放寻址法

开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。那如何重新探测新的位置呢?我先讲一个比较简单的探测方法,线性探测(Linear Probing)。当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。

链表法

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个“桶(bucket)”或者“槽(slot)”会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。

HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响 HashMap 的性能。

于是,在 JDK1.8 版本中,为了对 HashMap 做进一步优化,我们引入了红黑树。而当链表长度太长(默认超过 8)时,链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点,提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候,又会将红黑树转化为链表。因为在数据量较小的情况下,红黑树要维护平衡,比起链表来,性能上的优势并不明显。

装载因子

装载因子越大,说明散列表中的元素越多,空闲位置越少,散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链,查找的过程也会因此变得很慢。

最大装载因子默认是 0.75,当 HashMap 中元素个数超过 0.75*capacity(capacity 表示散列表的容量)的时候,就会启动扩容,每次扩容都会扩容为原来的两倍大小。

代码

这里我们给出C语言的HashTable代码,我们使用的是链表法,而且也没有在链表过长的时候将其转化为红黑树,只是单纯的链表。

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>typedef struct Node {int key;int val;struct Node *next;
} Node;typedef struct HashMap {int size;int count;struct Node **hashmap;
} HashMap;// 定义哈希函数
unsigned int hash(int n) {return (unsigned int) n;
}// 创建一个节点
Node *creatNode(int key, int val) {Node *node = (Node *) malloc(sizeof(Node));node->key = key;node->val = val;node->next = NULL;return node;
}// 创建一个hash表
HashMap *createHashMap() {HashMap *H = (HashMap *) malloc(sizeof(HashMap));H->size = 8;H->count = 0;H->hashmap = (Node **) calloc(H->size, sizeof(Node *));return H;
}// 扩容,以2倍的形式扩容
static void extend(HashMap *map) {int newsize = map->size * 2;Node **newhashmap = (Node **) calloc(newsize, sizeof(Node *));for (int i = 0; i < map->size; i++) {Node *node = map->hashmap[i];Node *head1 = (Node *) malloc(sizeof(Node));Node *head2 = (Node *) malloc(sizeof(Node));Node *temp1 = head1;Node *temp2 = head2;while (node) {if (hash(node->key) % newsize != i) {temp2->next = node;temp2 = temp2->next;} else {temp1->next = node;temp1 = temp1->next;}node = node->next;}temp1->next = NULL;temp2->next = NULL;newhashmap[i] = head1->next;newhashmap[i + map->size] = head2->next;free(head1);free(head2);}map->size = newsize;free(map->hashmap);map->hashmap = newhashmap;
}// 插入某个结点
bool insert(HashMap *map, int key, int val) {int hash_key = hash(key) % map->size;// 要插入的哈希值未产生碰撞if (map->hashmap[hash_key] == NULL) {map->count++;map->hashmap[hash_key] = creatNode(key, val);} else {Node *head = map->hashmap[hash_key];if (head->key == key) return false;while (head->next && head->next->key != key) head = head->next;if (head->next == NULL) {map->count++;head->next = creatNode(key, val);} else if (head->next->key == key) return false;}// 装载因子过高就开始扩容if (map->count / map->size > 0.75) extend(map);return true;
}// 寻找某个结点
bool find(HashMap *map, int key, int *v) {int hash_key = hash(key) % map->size;if (map->hashmap[hash_key] == NULL) {return false;} else {Node *head = map->hashmap[hash_key];if (head->key == key) {*v = head->val;return true;}while (head->next && head->next->key != key) head = head->next;if (head->next == NULL) return false;if (head->next->key == key) {*v = head->next->val;return true;}}return false;
}// 删除某个结点
void delete(HashMap *map, int key) {int hash_key = hash(key) % map->size;if (map->hashmap[hash_key] == NULL) return;Node *head = map->hashmap[hash_key];if (head->key == key) {map->hashmap[hash_key] = head->next;map->count--;free(head);return;}while (head->next && head->next->key != key) head = head->next;if (head->next == NULL) return;if (head->next->key == key) {Node *temp = head->next;head->next = head->next->next;map->count--;free(temp);}return;
}int main() {HashMap *H = createHashMap();for (int i = 0; i < 1024; i++) {insert(H, i, i);}printf("H size is %d\n",H->size);printf("H count is %d\n",H->count);delete(H, 0);int v = 0;if (find(H, 0, &v)) printf("%d\n", v);else printf("not find \n");if (find(H, 4, &v)) printf("%d\n", v);else printf("not find \n");return 0;
}

相关文章:

C语言手撕一个Hash表(HashTable)

什么是Hash Table 散列表用的是数组支持按照下标随机访问数据的特性&#xff0c;所以散列表其实就是数组的一种扩展&#xff0c;由数组演化而来。可以说&#xff0c;如果没有数组&#xff0c;就没有散列表。 散列函数 散列函数是将我们想插入的节点散列成一个数值的函数。它…...

代码随想录第二十七天(669、108、538、回溯算法介绍)

669. 修剪二叉搜索树 不能简单地通过递归实现代码&#xff0c;比如&#xff1a; class Solution { public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root nullptr || root->val < low || root->val > high) return nullptr;root->left t…...

【Leetcode】设计循环队列

目录 【Leetcode622】设计循环队列 A.链接 B.题目再现 C.解法 【Leetcode622】设计循环队列 A.链接 设计循环队列 B.题目再现 C.解法 其实这题用数组或是链表都能解决&#xff0c;但是如果是用链表的话&#xff0c;那么队列为空的条件和队列满了的条件是一样的&#xff0…...

【Linux】浅谈shell命令以及运行原理

前言&#xff1a;上篇博文把linux下的基本指令讲解完了。本期我们聊聊Linux下【shell】命令及其运行原理。 目录 Shell的基本概念与作用 原理图展示 shell命令执行原理 Shell的基本概念与作用 Linux严格意义上说的是一个操作系统&#xff0c;我们称之为“核心&#xff08;ker…...

【shell脚本】nginx服务管理及存活检测脚本实战

前言 今天终于敢说自己是csdn万粉博主了&#xff0c;感谢大家的厚爱&#xff0c;我会继续输出更多优质的好文章&#xff0c;一起学习。 座右铭&#xff1a; 先努力让自己发光&#xff0c;再帮助更多的人。 &#x1f3e0; 个人主页&#xff1a;我是沐风晓月 &#x1f9d1; 个人…...

web服务器—nginx

一、nginx介绍Nginx(“engine x”)是一款是由俄罗斯的程序设计师Igor Sysoev所开发高性能的 Web和 反向代理服务器&#xff0c;也是一个 IMAP/POP3/SMTP 代理服务器。和apache一样&#xff0c;都是web服务器软件&#xff0c;因为其性能优异&#xff0c;所以被广大运维喜欢。又因…...

网络安全工具大合集

还是一句话&#xff0c;功夫再高&#xff0c;也怕菜刀首先&#xff0c;恭喜你发现了宝藏。本文章集成了全网优秀的开源攻防武器项目&#xff0c;包含&#xff1a;信息收集工具&#xff08;自动化利用工具、资产发现工具、目录扫描工具、子域名收集工具、指纹识别工具、端口扫描…...

什么是SHA256?比特币是如何应用SHA256算法的?

SHA 256算法是一种具有确定性的单向哈希函数 算法是执行操作的一系列步骤或过程 哈希函数是种数学函数&#xff0c;输入的长度任意&#xff0c;但是输出长度固定&#xff0c;可以理解为文件的数字指纹&#xff0c;同一个输入值&#xff0c;总是得相同的输出 SHA256&#xff0…...

JDK20正式发布了GA版本,短期维护支持,以及JDK21预览

最近&#xff0c;Oracle发布了JDK20&#xff0c;相比对于Java开发者来说&#xff0c;JDK的发版是比较收关注的事情了&#xff0c;小简也来和大家一起了解了解JDK20发生了什么变化呢&#xff1f; 首先&#xff0c;JDK20是一个短周期版本&#xff0c;有6个月的维护时间&#xff0…...

.NET/C#/GC与内存管理(含深度解析)

详情请看参考文章&#xff1a;.NET面试题解析(06)-GC与内存管理 - 不灬赖 - 博客园 (cnblogs.com)一、对象创建及生命周期一个对象的生命周期简单概括就是&#xff1a;创建>使用>释放&#xff0c;在.NET中一个对象的生命周期&#xff1a;new创建对象并分配内存对象初始化…...

Java开发 | 内部类 | 静态内部类 | 非静态内部类 | 匿名内部类

目录 1.内部类 1.1内部类的简单创建 1.2内部类的分类 1.2.1普通内部类 1.2.2静态内部类 1.3匿名内部类 1.4局部内部类 1.内部类 内部类就是一是一个类里面装着另外一个类&#xff0c;就像俄罗斯套娃一样。最外层的类我们叫外部类&#xff0c;内层的类我们叫内部类。 1…...

Portal认证

Portal认证Portal认证简介Portal认证协议Portal认证方式Portal认证流程Portal认证用户下线Portal认证简介 定义&#xff1a; Portal认证通常也称作Web认证&#xff0c;一般将Portal认证网站成为门户网站。用户上网时&#xff0c;必须在门户网站进行认证&#xff0c;如果没有认…...

论文解读:ChangeFormer | A TRANSFORMER-BASED SIAMESE NETWORK FOR CHANGE DETECTION

论文地址&#xff1a;https://arxiv.org/pdf/2201.01293.pdf 项目代码&#xff1a;https://github.com/wgcban/ChangeFormer 发表时间&#xff1a;2022 本文提出了一种基于transformer的siamese网络架构&#xff08;ChangeFormer&#xff09;&#xff0c;用于一对共配准遥感图…...

Redis 内存优化技巧

这次跟大家分享一些优化神技如何用更少的内存保存更多的数据&#xff1f;我们应该从 Redis 是如何保存数据的原理展开&#xff0c;分析键值对的存储结构和原理。从而继续延展出每种数据类型底层的数据结构&#xff0c;针对不同场景使用更恰当的数据结构和编码实现更少的内存占用…...

【java】笔试强训Day2【​倒置字符串​与排序子序列】

目录 ⛳选择题 1.A 派生出子类 B &#xff0c; B 派生出子类 C &#xff0c;并且在 java 源代码有如下声明&#xff1a; 2.下面代码将输出什么内容&#xff1a;&#xff08; &#xff09; 3.阅读如下代码。 请问&#xff0c;对语句行 test.hello(). 描述正确的有&…...

【Linux】基础IO(一) :文件描述符,文件流指针,重定向

&#x1f34e;作者&#xff1a;阿润菜菜 &#x1f4d6;专栏&#xff1a;Linux系统编程 码字不易&#xff0c;请多多支持&#x1f618;&#x1f618; 这是目录重新认识文件系统内部的文件操作我们C语言的文件操作系统内部的文件操作OS一般会如何让用户给自己传递标志位的&#x…...

【C语言】通讯录的实现(静态版)

【C语言】通讯录的实现(静态版一.前言1.前期准备a.菜单实现b.联系人结构体的构建c.菜单选项的功能d.#define 的定义2.功能的实现a.初始化通讯录b.增加联系人c.显示通讯录d.查找联系人e.修改联系人d.删除联系人3. 总代码test.ccontact.ccontact.h一.前言 本文将会用c语言实现一…...

IDEA一键构建Docker镜像

效果 Idea右击Dockerfile文件&#xff0c;直接在服务器构建docker镜像 开整 1、下载docker插件 2、编写Dockerfile文件 # 基础镜像 FROM openjdk:8-jdk-alpine # 工作目录 WORKDIR /opt/apps/gateway/logs/ # 文件拷贝,把target目录下的jar报拷贝到镜像的/APP/目录下 ADD…...

QT的使用3:鼠标事件

鼠标事件0 事件1 需求2 查看控件的事件处理函数3 UI设计4 新建一个类&#xff0c;继承QLabel5 对已有对象进行类型提升6 重写事件处理函数7 项目进一步拓展&#xff08;1&#xff09;获取鼠标按键&#xff08;2&#xff09;鼠标移动&#xff08;3&#xff09;显示多个按键&…...

线程安全之单例模式

文章目录前言一.什么是单例模式二.在java中的单例模式2.1 饿汉式的介绍2.2 懒汉式的介绍三 懒汉式的单例模式,线程不安全的解决方式3.1 造成线程不安全的原因3.2 解决方案3.3 总结前言 这篇文章,我们会介绍一下单例模式,但这里的单例模式,不是我们所说的设计模式,当然听到设计…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...