真的是很久很久不写文章了。自我检讨一下，以后每周都要好好写文章，如果没有特别想说明的，就学习一下源码或者底层实现~
今天这篇文章主要是记录哈希表的定义、一些问题和我尝试实现哈希表等等。为什么写这个呢，因为我曾经面试的时候被要求手写映射算法。我就是摸石头过河写的，现在系统的整理一下~~
简介
哈希表是通过键（key）—值（value）来存储数据的。它通过一定的算法使fun(key)=value。其中这里的fun方法就是哈希算法。能实现上述表达是的表就是哈希表。那有没有fun(key1)=fun(key2)=value的情况呢，在算法中如何解决呢。首先这种情况叫做哈希碰撞，在算法中有多种解决办法可以往下看。至此所有有关哈希的名词和讲解到此结束，接下来是每一个名词的解决和实现。
哈希算法
1.求余法（这里的除数最好选用素数，减少哈希碰撞）
（1）分配一片空间来存储数据，比如空的数组
空数组
（2）使用我们的哈希算法：对存进来的数字进行%13，余数对应位置。例如数字18%13=5，则数字18在5的位置上。根据这样的方法，我们可以存入数据13、14、15、19
放入数据
（3）现在我们存入26这个数字。我们发现26%10=0，但是0的位置上已经有13了。那么我们查看1的位置，1的位置已经有14，再查看2的位置，2的位置有15，那么再查看3的位置发现3是空的，则把26放入3的位置上。样就解决了哈希碰撞。
放入26
（4）周而复始，这就是取余算法
2.MAD法
上述的方法在数据存储上有一定的规律容易窥探，这种方法算是上一种的改进。下面我们看一下它的表达式：
hash(key) = (a*key+b) % M， 其中M仍为素数,a>0,b>0，且a % M != 0
其实这就是一个计算的方式，我们也可以自己设计哟~
3.其他方法
其实哈希算法还有很多，例如：数字分析法、平方取中法、折叠法、平方散列法、斐波那契散列法等等。甚至只要我们设计的合理还有许多可以设计的方法，在这里就不一一介绍了，有喜欢的小伙伴可以考虑自行科普。
解决哈希冲突
其实在上面取余法的时候我们就已经解决了一个哈希冲突，我们所使用的方法就是线性探查发，也就是说一个一个的寻找。并且我们要知道的是冲突是不可避免的，所以我们有许多解决冲突的办法。
1.解决冲突的两种策略
（1）开放定址法：散列地址空间对所有词条开放（解释：装有数字的数组快允许不对应的key存放，例如取余法）；词条存储地址(散列地址)仅限于散列表所覆盖的范围之内（解释：不申请过多的内存，就是定长的数组，例如取余法）。
代表方法如：线性试探、查找链法等。
（2）封闭定址法：散列地址空间只对对应的词条开放；词条存储地址不局限于散列表范围之内（和上面的刚好相反）。
代表方法如：多槽位法、独立链法、公共溢出区等
2.解决冲突的方法
（1）多槽位法
这个非常好理解，上述取余法是一维数组每一个key对应的空间只有一个。那申请一个二维数组，将一个key对用的空间增多就是多槽法。看图~
多槽法
到这里，我有一个疑问，如果0这一格也装满了怎么办？根据资料说明，如果有新的加入则迅如对应的key并且增加一行。这就会导致许多空间没有得到利用。下面来看下一种方法
（2）独立链法
它和多槽法很相似，只不过不是有申请那么多的内存了。而是以链和数组的形式结合，这样做的好处就是空间会被充分利用，但是空间未必连续分布，会导致系统缓存失效。来看图~
独立链法
（3）公共溢出区
就是如果发现类似26这样的冲突数据，就放在令开辟的空间里（缓冲区）。
公共溢出区
（4）线性探查法
就是上述取余法时解决冲突的办法。
（5）采用平方探查法
类似于线性探查法，探查法出现哈希重读寻找下一位是否存在值。而平方探查发则寻找下1^2 位和上1^ 2位，如果均有，则寻找下2^ 2和上2^2位。以此类推，看图~
image.png
网友评论