算法之 散列表
2022/4/22 14:12:59
本文主要是介绍算法之 散列表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、散列表
1.散列表概念
基本思想:记录存储位置与关键字之间存在对于关系
通过一个函数,将关键字的值计算成地址用于存放
对应函数:Loc(i) = H(keyi)
1.例子:
H(key) = 取key的最后两位
将学号通过最后两位直接对应到相应的位置
优缺点:查找效率高,但是空间效率低。查找仅一次计算
2.术语:
2.1. 散列方法(杂凑法):
选取某个函数,依该函数按关键字计算元素的存储位置,并按此存放。
查找时,由同一个函数对给定值k计算地址,将k与地址单元在元素关键码进行对比,确定查找是否成功。
2.2散列函数(杂凑函数):
散列方法中使用的转换函数
2.3.散列表(杂凑表):
按上述思想构造的表
2.4.冲突:
不同关键码映射到同一个散列地址 ,key1 != key2 ,但是H(key1) = H(key2)
在散列表查找方法中,冲突是不可避免的,只能尽可能减少。
解决方法:1.构造好的散列函数:函数要简单并且计算出的地址应该集中致均匀分布
2.制定一个好的解决冲突的方案
3.函数的构造方法:
3.1 函数的构造的考虑因素
1.执行速度
2.关键字的长度
2.散列表的大小
4.关键字的分布情况
5.操作频率
3.2集合的构造方法
1.具有的性质
n个数据原理仅占用n个地址,虽然散列表是以空间换时间,但是还需要散列空间尽量小。
2.构造方法
1.直接定址法:
以关键码key的某个线性函数值为散列地址,不会产生冲突。
缺点:空间使用率低,要占用连续地址空间
2.除留余数法
Hash(key) = key mod p( p是一个整数 ) p一般小于等于表长且为质数
4.解决冲突的方法:
![](/upload/202204/22/202204221412576473.png)
4.1开放定址法:
思想:有冲突就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将数据元素存入
例子:
伪随机方法:是能找到哪一个就存在哪一个
4.2 :链地址法(拉链法)
思路:相同散列地址的记录链成一单链表
m个散列地址就设m个单链表,然后用一个数组将m个单链表的表头指针存起来,形成一个动态的结构。
理解:将冲突的的数据在这个地址上用单链表的形式表示。
链表上系欸但空间动态申请,适合于表长不确定的情况,
2.散列表的查找
3.哈希表的查找效率分析
1.散列函数
2.处理冲突的方法
3.散列表的装填因子(表中填入的记录数/哈希表的长度)
装填因子对打,表中记录数越多,表明表装的越满,发生冲突的可能性就越大
这篇关于算法之 散列表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?