搜索结构之【哈希】
查找分类
在很多的时候，我们需要从元素的集合中查找出给定的关键字是否存在的过程，这个过程通常有两种结果：查找成功，查找失败。
用于搜索数据的集合，称之为搜索结构，一般是由统一类型的元素的集合。
而查找的环境分为静态环境和动态环境。
静态环境：在插入或者删除等操作前后搜索结构不会发生改变，向顺序表，链表。
动态环境：为了保证较高的搜索效率，在插入或者删除的前后搜索结构会自动进行调整，结构可能会发生改变，向搜索二叉树，AVL树，B_树，B+树这样的一些结构。
静态查找：只是查找给定关键字是否存在元素集合中。
动态查找：不光包含静态查找要求，还会插入一些元素集合中没有的元素或者删除一些没有的元素。
哈希
在顺序表，二叉搜索树，B树等搜索结构中进行查找的时候，元素的关键码和元素的存储位置并没有什么直接关系，查找的效率取决于元素的比较次数。
而理想的搜索结构是不经过任何的比较，直接从搜索结构中找到想要的元素。因此，我们构造出了这样的一种搜索结构，使元素的关键码和它的存储地址建立起来一个一一对应的关系address=Hash（key)。这就是哈希查找，这个函数就称之为哈希函数，这种结构我们称之为哈希表。
在插入元素的时候，我们对元素的key进行函数元素，计算出它的存储位置。
同样的，在查找元素的时候，我们对给定元素的key进行同样的运算，计算出它的hash地址，直接到对应的位置查找即可。
因为这种搜索结构不需要经过多次的关键码比较，直接定位，所以查找的效率比较快。
哈希冲突
对于两个不同的元素，它们的关键码不一样，但是通过哈希函数计算出来了相同的哈希地址，这种情况，就叫做哈希冲突，很明显，我们应该尽量避免这样的情况出现。
如果key1不等于key2，但是通过哈希函数计算出了相同的哈希地址，就发生了哈希冲突。
常见的哈希函数
1.直接定址法：我们通过一个线性的函数，比如Hash（key）=A*key+B，其中A，B为常数，计算出哈希地址。
这种方法优点简单快捷，缺点是事先得知道关键码的分布情况，适合查找关键码小，而且连续的情况。
2.除留余数法：假设散列表中的运行存储的长度为M，取一个不大于M的数，但最接近M的质数p作为除数，取模运算。Hash(key)=key%p。
3.平方取中法：假设元素的关键码是123，那么关键码的平方就是1522756，那么就取中间三个数字227作为散列地址，适合不知道关键字的分布，关键字位数又不是很大的情况。
4.随机数法：选一个随机数函数，取元素关键码的随机数函数值作为散列地址。Hash（key）=random（key）。适合关键字长度不等的时候用。
5.折叠法：折叠法就是把关键码从左到右分割成几个位数相等的几部分，然后讲这几部分折叠相加，然后再根据表长，取后几位作为散列地址。比如说关键码是9876543210，散列表长为三位，讲其分为四组987|654|321|0，折叠相加987+654+321+0=1962，取后三位962作为散列地址。这种方法适合关键码位数比较多，事先不知道元素分配情况。
哈希冲突的避免方法
即便是我们有各种各样的哈希函数，但是仍然不能完全避免哈希冲突的问题，因此我们需要把哈希表再进行改造，降低哈希冲突。
【闭散列】
闭散列又叫做开放地址法，即当我们计算出一个元素的哈希地址，准备向这个地址中插入元素的时候，发现哈希表中对应位置以及有元素了，即发生管哈希冲突，那么我们重新计算下一个地址，只要表没有存满，那么元素总有地方能够存放。
1.线性探测
线性探测的基本思想就是：如果发生哈希冲突，即这个位置以及有元素存在，那么依次向后探测，一旦找到空位置就进行插入。
但是在线性探测中，不能随便的删除元素，一旦删除过后，就会影响其他元素的查找，因此我们对每一个位置，设置了一个标志位，有三个标志，空，存在，和删除。当状态为删除的时候，不能进行插入操作。
另外，负载因子也是一个很重要的指标，在开放地址法中，负载因子定义为：α=填入表中的元素个数/散列表的长度。α越大，说明了表中的元素个数越多，那么发生哈希冲突的概率就越大。就会大大降低查表的效率。因此我们应该严格负载因子在0.7左右才适合。
缺点：虽然线性探测简单，但是很容易出现数据的堆积问题，使得查询关键码需要经过很多次的比较，导致搜索时间边长。
2.二次探测
二次探测的思想是，当发生哈希冲突的时候，在表中寻找下一个位置的公式为：H(i)=(H0+i^2)%m,H(i)=(H0-i^2)%m,i=1,2,3,4…(m-1)/2.
经过大量数据研究，当表长为质数并且负载因子不超过0.5的时候，新的表项一定能够插入的，并且任何一个位置都不会探测超过两次，因此在插入的时候，必须确保负载因子不超过0.5，否则就要考虑增容的问题。
【开散列】
开散列首先对关键码集合进行散列地址的计算，然后讲具有相同的散列地址的元素归于同一个子集合，每一个子集合称之为一个桶，各个桶中的元素通过一个个链表连接起来，各链表的头节点组成一个向量，因此，向量的元素个数与可能的桶数一致。
开散列的方法，貌似需要新增指针来管理链表，但是比起闭散列要求负载因子小于0.7的要求，开散列节省了不少的存储空间。