做了几年开发，这个技术点一直是面试高频考点，今天系统梳理一下核心知识点和实战经验。
1.哈希概念
哈希（hash）又称散列，是一种组织数据的方式。从译名来看有散乱排列的意思，其本质是通过哈希函数将关键字key值与存储位置建立映射关系，查找时通过哈希函数计算出key值的位置，实现快速查找。
1.1直接定址法
当关键字key值比较集中时，直接定址法是最简单也是最有效的方法。比如一组数据集中在[ 0 - 99 ]，我们开一组大小为100的数组即可，数据直接作为下标来定位存储位置。再比如一组数据集中在[ a - z]，我们开一个大小为26的数组即可，让数据减去字符‘a'的结果来定位存储位置。
例题：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
class Solution
{
public:int firstUniqChar(string s){int arr[26]={0};//范围for 遍历for(auto e: s){arr[e-'a']++;}for (int i = 0; i < s.size(); i++){if (arr[s[i] - 'a'] == 1){return i;}}return -1;}
};1.2哈希冲突
直接定址法适用于数据比较集中的情况，当数据过于分散时这意味这我们将会开一个过大的数组来存储，而这会极大的浪费内存空间，不可取。
所以当面对这种情况的时候，我们会使用哈希函数:h(key)，通过哈希函数对关键字key值在存储空间的映射，来定位key值的存储位置。而这里存在一个问题：不同的值通过哈希函数的映射后的位置可能相同，这就会导致哈希冲突（哈希碰撞）。我们可以通过设计一个好的哈希函数来减少哈希冲突，但是在实际情况下，哈希冲突是不可避免的。
1.3负载因子
假设存储空间的大小为M，已经放入存储空间的数据个数是N，那么负载因子就是：N/M。负载因子也称载荷因子。负载因子越大，哈希冲突概率越大，空间利用率越高。负载因子越小，哈希冲突概率越小，空间利用率越低。
1.4哈希函数
1.4.1除法散列法/除留余数法
顾名思义就是通过取余，其余值就是映射的存储位置。假设存储空间的大小为M，关键字为key，哈希函数h(key)=key%M。
使用除法散列法时，对M有一个要求：要求M不能为2的幂、10的幂。假设M为 2^3，这相当于直接保留了2进制中的后3位，那么只要key值的后3位相同那么就一定冲突，例如：3，11，19，27......，它们二进制的后三位都是011，所以它们同时取余M都等于3。所以当M为2的幂时会导致很高的冲突概率，不可取。同理当M为10的幂时，假设为10^3，这相当于保留了10进制中的后3位，那么只要key值的后3位相同就一定冲突，例如：1001，2001，3001.....，所以也不可取。
综上所述，建议M的取值为不接近2的幂的值（素数）
优化建议：
如果你的项目访问量较大，建议增加缓存机制。我们团队在优化后，接口响应时间从800ms降到了50ms， 效果非常明显。具体的缓存策略可以根据业务场景调整。
但在实际操作中也有存在直接去2的幂，10的幂的情况。比如java中实现的哈希表就是直接取的2的幂。当然他不仅仅的取余这么简单，还有其他操作保证了较低的冲突概率。比如M为2^16，先取余得到2进制的后16位，再将key>>16，将取余的结果和右移的结果做异或运算。这样的操作将每个数都参与的运算，使其分布的更加的均匀。（了解，在后续的代码实现中我们还是以取素数为例）
1.4.2乘法散列法（了解）
使用乘法散列法对M没用要求，其大体思路为：关键值key乘上一个常量A(0<A<1)，然后在对其结果取余，得到小数部分。再将M乘上小数部分，再向下取整，得到最终结果。哈希函数为：h(key)= floor( M*( ( key*A ) %1.0) ) ,floor表示向下取整
A的取值范围为0~1，结论表明A的取值为：(根号5 - 1)/2 = 0.6180339887....（黄金分割点）比较好
1.5将关键字转化为整型
在哈希函数里面我们说到了，要通过哈希函数将key值映射到存储位置。不管是那种方法，我们可以看到key值都要参与具体的运算的。但是如果key不为整型时，这么办？
这里我们就需要将key值转化为整型，如果为负数、浮点数等等就强制类型转化为整型。如果为string类型，可以通过将每个字符的ascll码相加，来得到整型。其他的都类似，通过映射的值来转化为整型。
1.6解决哈希冲突
哈希表中使用的哈希函数主要还是除法散列法，但对于哈希冲突，不论选择什么哈希函数都不可避免。所以我们需要知道可以解决哈希冲突的方法，主要分为两种：开放地址法、链地址法。
1.6.1开放地址法
在开放地址法中，所有元素都存于哈希表中，当通过哈希函数映射key的存储位置发生冲突时，按照一定规则去找下一个空白位置进行存储。开放地址法的负载因子一定是小于1的。这里的规则一