type
status
password
date
slug
summary
category
URL
tags
icon
在记录的存储位置和它的关键字之间建立一个确定的对应关系 ,使得每个关键字 对应一个存储位置 , 通过查找关键字, 不需要比较就可获得记录的存储位置; 存储位置 =(关键字)。这样就可以快速定位和删除元素
- 装填因子:数组中可以填充有5个元素,但是现在只填充了2个。所以现在的装填因子是0.4
映射函数
方法 | 关键字 | 适用场景 |
直接定址法 | 知道关键字的分布 | 简单,均匀,不会冲突,适合查找表小且连续的关键字 |
数字分析法 | 关键字位数多,知道关键字分布 | 抽取关键字的一部分计算散列存储位置 |
平方取中法 | 不知道关键字分布,且位数不多 | 1234,平方1522756,抽取中间227作为散列地址。 |
折叠法 | 不知道关键字分布,位数多 | 从左到右分割成位数相等的几部分,这几部分
叠加求和,并按散列表表长,取后几位作为散列地址。 |
直接定址法
- 特点:简单,均匀,不会冲突,但是事先知道关键字的分布情况,适合查找表小且连续的关键字。
- 举例:比如统计1980年以后出生的人数:
地址 | 出生年份 | 人数 |
0 | 1980 | 1500万 |
1 | 1981 | 1600万 |
2 | 1982 | 1300万 |
… | … | … |
20 | 2000 | 800万 |
平方取中法
- 背景: 不知道关键字分布,且位数不是很大。
- 比如: 1234,平方1522756,抽取中间227作为散列地址。
折叠法
- 背景: 不知道关键字分布,位数多。 从左到右分割成位数相等的几部分,这几部分叠加求和,并按散列表表长,取后几位作为散列地址。 比如: 关键字是 , 散列表长为 ; 将关键字分为 组, , 然后 , 求后三位得到散列地址为 ;
除留余数法
- 选取不好,产生冲突。
- 通常 为 (最好接近m)的最小质数或者不包含小于20质因子的合数。
随机数法
- 背景: 关键字长度不等。
- 当关键字为字符串,转化为某种数字来对待,比如ASCLL码或者Unicode码等。
hash冲突解决方法
- 冲突:关键字 不等于 ,但 。
- 把 和 称为散列函数的同义词。
开放定址法
所谓开放地址法,就是一旦产生了冲突,即改地址已经存放了其他数据元素,就去寻找另一个空的散列地址。开放地址法利用试探性散列函数,首先试试附近的散列地址是否是空的。如果还发生冲突的话就再试试其他散列地址。试探性散列函数的基本公式是:
- ,相应解决冲突的方法称为线性探测在散列
- 或 ,相应的解决冲突的方法称为二次探测再散列
- 为伪随机数,相应的解决冲突的方法称为随机探测再散列
代码
自建哈希表 链地址法
705. 设计哈希集合(只有键)
706. 设计哈希映射(键值对)
哈希集合
217. 存在重复元素
136. 只出现一次的数字
349. 两个数组的交集
202. 快乐数
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1,也可能是
无限循环
但始终变不到 1。如果这个过程 结果为 1,那么这个数就是快乐数。输入:n = 19 输出:true 解释:
哈希映射
1. 两数之和
给定一个整数数组
nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那两个整数,并返回它们的数组下标。205. 同构字符串
给定两个字符串 s 和 t ,判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
示例
599. 两个列表的最小索引总和
假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
387. 字符串中的第一个唯一字符
给定一个字符串
s
,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1
219. 存在重复元素 II
给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false 。
设计键
49. 字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
652. 寻找重复的子树
给定一棵二叉树 root,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。如果两棵树具有相同的结构和相同的结点值,则它们是重复的。
python中的hash函数
习题
- 计算查找失败的平均查找长度以及关键字的平均查找长度8个数字 key%7 如下算好了:
给定一棵二叉树 root,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。如果两棵树具有相同的结构和相同的结点值,则它们是重复的。