C++数据结构之哈希表
2024-10-06 23:09:22
哈希表的定义:哈希表是一种根据关键码去寻找值的数据映射结构,该结构通过把关键码映射的位置去寻找存放值的地方。键可以对应多个值(即哈希冲突),值根据相应的hash公式存入对应的键中。
哈希函数的构造要求:
- 运算过程要尽量简单高效,以提高哈希表的插入和检索效率;
- 哈希函数应该具有较好的散列型,以降低哈希冲突的概率,即尽量使关键字对应的记录均匀分配在哈希表里面
- 哈希函数应具有较大的压缩性,以节省内存
- 关键字极小的变化可以引起哈希值极大的变化。
哈希冲突解决方法:1.链地址法
链地址法的原理时如果遇到冲突,他就会在原地址新建一个空间,然后以链表结点的形式插入到该空间。
下面从百度上截取来一张图片,可以很清晰明了反应下面的结构。比如说我有一堆数据{1,12,26,337,353...},而我的哈希算法是H(key)=key mod 16,第一个数据1的哈希值f(1)=1,插入到1结点的后面,第二个数据12的哈希值f(12)=12,插入到12结点,第三个数据26的哈希值f(26)=10,插入到10结点后面,第4个数据337,计算得到哈希值是1,遇到冲突,但是依然只需要找到该1结点的最后链结点插入即可,同理353。
2. 开放地址法
参考文章:
https://www.cnblogs.com/s-b-b/p/6208565.html
https://www.cnblogs.com/jijiji/p/4856805.html
最新文章
- Mac 词典工具推荐:Youdao Alfred Workflow(可同步单词本)
- Nginx与Apache的比较
- TortoiseGit上传项目到GitHub////////////////////////////z
- 关于使用TP-Link桥接小米路由器
- Career path of Bioinformatics
- 删除ubuntu后无法进入windows
- Leetcode Word Break
- 【转】Hadoop web页面的授权设定
- Android 调用浏览器和嵌入网页
- Python和Django在Windows上的环境搭建
- myplan
- 《python基础教程》笔记之 元组
- for 循环 以及基本的数据类型
- nowcoder 211E - 位运算?位运算! - [二进制线段树][与或线段树]
- Eloquent JavaScript #04# Objects and Arrays
- Redis热点Key发现及常见解决方案!
- python apsheduler cron 参数解析
- Angular4 自制打地鼠游戏
- delphi TComponent类 2
- 异常类Exception(String message, Throwable cause)中的cause理解
热门文章
- ssh connection refused 问题
- 基于partition的递归
- Spring mvc 初始化过程
- git fetch和pull的区别
- IIFE 立即执行函数表达式-模块化
- PHP swoole TCP服务端和客户端
- 51nod 1850 抽卡大赛 (十二省联考模测) DP
- BZOJ 1420: Discrete Root (原根+BSGS)
- koa2+redis+jwt token验证,简单注册登录
- 【Winfrom-Panel】Panel隐藏与显示,自动隐藏菜单, Auto-Hide Menu