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"]]
python中的hash函数
习题
- 计算查找失败的平均查找长度以及关键字的平均查找长度8个数字 key%7 如下算好了：
给定一棵二叉树 root，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。如果两棵树具有相同的结构和相同的结点值，则它们是重复的。