数据结构与算法五：哈希表-哈希函数设计原则-哈希冲突解决方案

数据结构与算法五：哈希表-哈希函数设计原则-哈希冲突解决方案

一、哈希表的定义：

二、哈希表举例：
哈希函数就是映射关系

三、哈希表应用举例：
Leetcode上第387题：

思路：通过s.charAt(i)-'a’将字符串中的字符映射成hash表，出现一次，在相应位置加一，左后找到第一个值为1的下标
其他思路：当然此题解决方案很多，如一位一位的遍历亦可以

四、哈希函数：

将业务场景中的键转化为索引的过程称为哈希表的核心即使再优秀的哈希表也保证不了一个键对应一个不同的索引，这就是哈希冲突哈希函数设计原则：一致性（equals相等这hash值相等）、高效性（简单高效）、均匀性（尽可能使得hash值分布均匀）哈希表体现了空间换时间的原理

为了降低哈希冲突，需要采用大于实际存储数据数量的哈希表，这就是空间换时间的原理。

五、常见哈希函数：
1.整型：
小整数:

小正整数：直接使用；如0-9小负整数：偏移成正整数再使用；如-10-0可以先加10再使用

大整数：

大整数取部分：如复杂的学号20210917141122，如果直接使用需要20210917141122长的哈希表，取部分，如17141122则可以节省很大的空间。

大整数对m取模：m的值很重要，一般是质数取模，哈希冲突的概率小

质数是除了1与自身之外没有其他约数的自然数；0与1既不是质数也不是合数

业内总结数值区间与最优取模值，如下：

2.浮点型：
转化为整数即可

3.字符串：
通过直接转换或者B进制数，转化为整数即可

如果B很大可以每一项都先取模：

3.引用数据类型：
可以让其中的成员变量各自哈希得出；
Java中的hashCode(),为我们计算string类型的hash值;

六、哈希冲突处理方法：

再完美的hash算法也不可能避免hash冲突，因此需要有处理hash冲突的方法；

1.链地址法(常用）：
hashMap、hashSet底层均是散列表；其解决hash冲突的方式就是链地址法；

2.开发地址法：
如果遇到hash冲突，开放地址法有四种处理方案：
线性探测法：冲突时，就去存相邻位置，以此类推
平方探测法：冲突时，进行平方找位置，以此类推
再哈希法： 再次用其他的hash算法，进行一次或多次hash
合理扩容： 为了较少hash冲突可进行适当扩容

数据结构与算法更多相关内容【持续更新中】：

【数据结构与算法一：时间频度和时间复杂度】: 传送门.【数据结构与算法二：数组】: 传送门.【数据结构与算法三：栈和队列】: 传送门.【数据结构与算法四：链表】: 传送门.【数据结构与算法五：哈希表-哈希函数设计原则-哈希冲突解决方案】: 传送门.