目录
哈希表
概述
-
哈希表（散列表），可以理解为Hash函数（散列函数）与链表结合共同实现的一种数据结构。与离散化思想类似，离散化可以理解为一种特殊的哈希。
issue
希望读者读完本文可以独立解决一下问题：
-
为什么用哈希表？
-
哈希表的优缺点
-
关于冲突以及结果方法
-
处理冲突的两种方式分别是什么？它们个在自己的领域有着怎样的优势
一、什么是哈希表
文章开头就已经提到，哈希表是一种在链表上做一些特殊操作的数据结构。那么它与链表有什么样的联系呢，我下面举个简单的例子：
图书馆有十万万图书，把它们随意放在书架上，此时书架上的书是没有顺序的，小王想找一本《C primer puls》，他只能从第一本图书开始找，一本一本遍历，这样复杂度会很高；
哈希表就是给这些图书编号放置，便于查找。如何给图书编号那就得靠哈希函数了，通过哈希函数对其进行特殊处理下标，并将其储存在数组中。
二、哈希表的优缺点
大家在刚才的描述中一定能看出哈希表的优缺点了，这里我总结一下 ，还是希望大家能独立思考
（1）优点
-
对于一些大数据多数据，hash表处理起来比较轻松
-
能够快速的 查，改，插，删元素 等操作
-
代码简单（自己想好hash函数就完成啦）
（2）缺点
-
在hash函数处理某些元素的时候，不免出现下标重复相同的情况，这种情况可以称作为冲突
-
哈希表中的数据都是没有顺序的
冲突的解决方法
前面提到的冲突，当两个或两个以上的下标相同时发生冲突，那么该如何处理这种情况呢，下面提到两种方法，拉链法和开放寻址法，
这里比较懒用y总的图来形象的概括下
（1）拉链法
可以看出在重复下表的下面又开了一个数组，有点像邻接表。在这个数组将重复的全部装进去，这样在查找的时候只需要遍历这个数组就ok了；
这是第一种解决 冲突 的方法，但使用是还是需要考虑数组长度是否合适的
（2）开放地址法
这种方法简单来说就是当元素下标值发生冲突时，寻找空白的位置插入数据。
其实当发生冲突时，寻找空白的位置也有三种方法，分别是 线性探测 、二次探测 、再哈希法
1.线性探测
线性的意思是 ：当发生冲突时，索引+1，查看此时位置是否为空，是的话插入，否则重复以上操作；
但这个方法的有一个致命的缺点，当很长一段长度都不为空时候上述步骤要重复很多次，这种现象称为聚集
那么我们将如何处理这种问题呢，接下来讲的二次探测来缓解这种情况
2.二次探测
二次探测 在线性探测的基础上，将每次探测的步长改为了当前下标值 index + 12 、index + 22 、 index + 32 …… 直到找到空白位置插入元素为止
我们可以看到，二次探测 在一定程度上解决了 线性探测 造成的 聚集 问题，但是它却在另一种程度造成了一种聚集，就比如 12 、22 、32 …… n2 上的聚集。所以这种方式还是有点不太好。
3.再哈希法
再哈希法 就是再将我们传入的值进行一次 哈希化，获得一个新的探测步数 step，然后按照这个步数进行探测，找到第一个空着的位置插入数据。这在很大的程度上解决了 聚集 的问题。
HASH表的基本操作
-
计算hash函数的值
-
定位到对应链表
O（1）的复杂度
今天时间有点赶，可能写的不够全也不够好，还有代码实现以及一些配图没有完成例子也没有多么生动，以后有时间会做修改，最后，希望大家指出我的不足，大家共同学习进步，早日进大厂！！
