哈希表原理
1.哈希表是什么
哈希表（hash table，又叫散列表），其原理的核心就是哈希函数（即散列函数），即如何构建一个确定的映射，它能把关键字映射到一个唯一的存储位置，如下公式所示
记录的存储位置=f(关键字)
f为散列函数，又称哈希函数。通过此函数将值映射到表中的一个位置来访问记录，以加快查找的速度，存放记录的数组叫做散列表。
2.Hash表的基本思路
假设ki为某个对象的关键字，则用哈希函数h(ki)来映射ki的内存地址，也就是ki的下标，将ki对象的元素内容存入这个地址中就行了。
用下面一个通俗易懂的例子来解释
现在需要存储4个元素 13 7 14 11
显然，我们可以用数组来存。也就是：a[0]=13;a[1]=7;a[2]=14,a[3] = 11
我们也可以用hash表来存储
先确定哈希函数为h(ki)=ki%5;，因此
对于第一个元素h(13)=13%5 = 3；也就是说13的下标为3；即Hash[3]=13;
对于第二个元素h(7)=7%5=2;也就是说7的下标为2；即Hash[7]=2
以此类推 Hash[4]=14;Hash[1]=11.
咋一看这样并没有什么优势，其实不然，实际上其在查找方面效率很高
比如现在我要查找11这个元素是否存在，如果用数组，遍历一遍，即需要查找4次，时间复杂度为O（n）
而用哈希函数来实现，代入上面的公式有
h(11) = 11%5=1，即查找了1次，就找到了此值，时间复杂度为O(1)
3.哈希表优缺点
优点：一对一的查找效率很高；
缺点：一个关键字可能对应多个散列地址；需要查找一个范围时，效果不好。
4.哈希冲突问题
所谓哈希冲突即一个关键字映射到多个值得情况，如
10%5=0；20%5=0，即Hash[0]=10 还是 Hash[0]=20呢
解决哈希冲突常见的方法有拉链法，开放地址法，再散列法
4.1 拉链法
拉链法即数组和链表的结合，如下图所示：
左边为一个数组，数组中成员为一个指针，指向一个链表的头
比如要寻找353，首先找到数组下标为1的位置，再找到值为1的链表，此时由于(1不等于363),，继续往下查找下一个链表(337不等于353)，再查找下一个链表，即找到该值。
对于要插入存储新的值，在冲突的时候，则将值存在该行链表的最右边.。
位桶：上述图中每一个数组对应的所有链表即在一个位桶之中
哈希桶：哈希桶就是盛放不同key链表的容器(即是哈希表)
装载因子：即存储的关键字/哈希表中可以散列的位置的大小，值越大表示hash表越拥挤，越容易引起冲突
优缺点
拉链法的优点在于处理冲突简单，且由于用到了链表，删除方便。
缺点是表长不固定，需要额外的的空间。
3.2 开放地址法
开放地址法的特征就是，每个位桶中没有链表，只会存储一个值，即每个位桶的装载因子等于1。
它的实现是在插入一个元素的时候，通过哈希函数判断，如果发生冲突，就以当前地址为基准，再寻址去寻找下一个地址，若发生冲突再去寻找下下个地址，直到找到一个空的地址为止。
如
（1）线性探查法
dii=1，2，3，…，m-1；这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
（2）二次探查
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )；这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
（3）伪随机探查
在查找位置index周围随机的查找。称为随机在探测。
di=伪随机数序列；具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），生成一个伪随机序列，并给定一个随机数做起点，每次去加上这个伪随机数就可以了。
3.3 再散列法
再散列法其实很简单，就是在使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置
缺点：每次冲突都要重新散列，计算时间增加。
参考资料
https://blog.****.net/qq_41230365/article/details/81058217