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 散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。 散列函数 散列函数是将我们想插入的节点散列成一个数值的函数。它…...

代码随想录第二十七天(669、108、538、回溯算法介绍)
669. 修剪二叉搜索树 不能简单地通过递归实现代码,比如: 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.解法 其实这题用数组或是链表都能解决,但是如果是用链表的话,那么队列为空的条件和队列满了的条件是一样的࿰…...

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

【shell脚本】nginx服务管理及存活检测脚本实战
前言 今天终于敢说自己是csdn万粉博主了,感谢大家的厚爱,我会继续输出更多优质的好文章,一起学习。 座右铭: 先努力让自己发光,再帮助更多的人。 🏠 个人主页:我是沐风晓月 🧑 个人…...

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

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

什么是SHA256?比特币是如何应用SHA256算法的?
SHA 256算法是一种具有确定性的单向哈希函数 算法是执行操作的一系列步骤或过程 哈希函数是种数学函数,输入的长度任意,但是输出长度固定,可以理解为文件的数字指纹,同一个输入值,总是得相同的输出 SHA256࿰…...

JDK20正式发布了GA版本,短期维护支持,以及JDK21预览
最近,Oracle发布了JDK20,相比对于Java开发者来说,JDK的发版是比较收关注的事情了,小简也来和大家一起了解了解JDK20发生了什么变化呢? 首先,JDK20是一个短周期版本,有6个月的维护时间࿰…...

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

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

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

论文解读:ChangeFormer | A TRANSFORMER-BASED SIAMESE NETWORK FOR CHANGE DETECTION
论文地址:https://arxiv.org/pdf/2201.01293.pdf 项目代码:https://github.com/wgcban/ChangeFormer 发表时间:2022 本文提出了一种基于transformer的siamese网络架构(ChangeFormer),用于一对共配准遥感图…...

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

【java】笔试强训Day2【倒置字符串与排序子序列】
目录 ⛳选择题 1.A 派生出子类 B , B 派生出子类 C ,并且在 java 源代码有如下声明: 2.下面代码将输出什么内容:( ) 3.阅读如下代码。 请问,对语句行 test.hello(). 描述正确的有&…...

【Linux】基础IO(一) :文件描述符,文件流指针,重定向
🍎作者:阿润菜菜 📖专栏:Linux系统编程 码字不易,请多多支持😘😘 这是目录重新认识文件系统内部的文件操作我们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文件,直接在服务器构建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 新建一个类,继承QLabel5 对已有对象进行类型提升6 重写事件处理函数7 项目进一步拓展(1)获取鼠标按键(2)鼠标移动(3)显示多个按键&…...

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

铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...

Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...