北海做网站哪家好,王也踏青图是动漫哪一集,网址大全2345 下载这?,html5制作手机网站教程哈希表
1. 概念
哈希函数也叫散列函数#xff0c;它对不同的输出值得到一个固定长度的消息摘要。
1散列结果应当具有同一性#xff08;输出值尽量均匀#xff09;
2雪崩效应#xff08;微小的输入值变化使得输出值发生巨大的变化#xff09;
通常有以下几种构…哈希表
1. 概念
哈希函数也叫散列函数它对不同的输出值得到一个固定长度的消息摘要。
1散列结果应当具有同一性输出值尽量均匀
2雪崩效应微小的输入值变化使得输出值发生巨大的变化
通常有以下几种构造 Hash 函数的方法 直接定址法取关键字或关键字的某个线性函数值为散列地址。例如以年龄为关键字的散列表 随机数法选择一个随机函数把关键字的随机函数值作为它的哈希值。通常用于关键字长度不等时采用此法构造哈希函数。 折叠法将关键字分为位数相同的几部分然后取这几部分的叠加和舍去进位作为散列地址。 平方取中法先计算出关键字值的平方然后取平方值中间几位作为散列地址。 除留余数法最常用的取关键字被某个不大于散列表长度 m 的数 p 求余得到的作为散列地址。 数字分析法当关键字的位数大于地址的位数对关键字的各位分布进行分析选出分布均匀的任意几位作为散列地址。仅适用于所有关键字都已知的情况下根据实际应用确定要选取的部分尽量避免发生冲突。
Hash表大小的确定
Hash 表的空间如果远远大于实际存储的记录数据的个数则造成空间浪费如果过小则容易造成冲突。Hash 表大小确定通常有这两种思路 如果最初知道存储的数据量则需要根据存储个数 和 关键字的分布特点来确定 Hash 表的大小。 事先不知道最终需要存储的记录个数需要动态维护Hash表的容量此时可能需要重新计算 Hash 地址。
Hash冲突解决
(1)拉链法
在重复下表的下面又开了一个数组在这个数组将重复的全部装进去这样在查找的时候只需要遍历这个数组就ok了
(2)开放地址法
这种方法简单来说就是当元素下标值发生冲突时寻找空白的位置插入数据三种方法分别是 线性探测 、二次探测 、再哈希法其中再哈希法就是再将我们传入的值进行一次 哈希化获得一个新的探测步数 step然后按照这个步数进行探测找到第一个空着的位置插入数据。这在很大的程度上解决了 聚集 的问题。Hash 实现方案
这几个都是集合类都是基于散列表分析它们可以从如下几个点出发
线程安全HashTable是线程安全HashMap和HashSet不是
实现方式HashMap基于拉链法的散列表链过长会自动转为红黑树HashSet底层采用HashMap实现的
初始大小HashTable初始大小是11HashMap初始大小是16
空值HashMap可以将空值作为key一条键不能重复或者value多条HashTable不允许null值键与值都不行,HashSet多个null只会有一个null存在。
扩容方式HashTable采用(oldCapacity 1) 1HashMap采用oldCap 1
哈希值HashTable直接使用对象的hashCode而HashTable采用在对象的hashCode上还进行的处理变化Hash 表的及优劣
1优点
对于一些大数据多数据hash表处理起来比较轻松
能够快速的 查改插删元素 等操作
代码简单自己想好hash函数就完成啦2缺点
在hash函数处理某些元素的时候不免出现下标重复相同的情况这种情况可以称作为冲突
哈希表中的数据都是没有顺序的2. 解题技巧我的总结 1 原地哈希题目限制空间复杂度时使用 题目说明实现41. 缺失的第一个正数数值n存到数组中的n-1位置我的提交LCR 120. 寻找文件副本数值n存到数组中的n位置我的提交442. 数组中重复的数据数值n存到数组中的n-1位置我的提交 2 大量无规则数据问题的简化 题目说明实现554. 砖墙前缀和的方式记录每块砖的右端点hash找出最大出现次数的我的提交1711. 大餐计数记录所有数的出现次数对每个数枚举其对面数的可能性我的提交 3 集合交并/子集 题目说明实现1452. 收藏清单记录每个字符串出现的idx列表i位置的字符串jj出现的位置cnt都1看最后是否有个位置cnt和i字符串数相同我的提交
3. 更多练习
4. 参考
❤数据结构入门❤——哈希表总库tryHard
