哈希

在前面我们已经学到很多在一个结构中查找一个元素，不同的结构的方法不同且实现时的时间复杂度与空间复杂度都有不同，但是但部分的查找都是经过比较，从而找出自己要查找的主要元素。由此我们就想，有没有一种方法不通过比较，从而快速的找到需要的数据，因此，在这里我们就提出了哈希查找，利用存储位置并按照此位置进行存放元素，从而极大的实现了我们的查找效率。下面我们将对哈希查找展开来讲。
目前我们了解到的查找主要有以下几种：

一、基本概念
1、哈希方法的提出
由于在查找与搜索的过程中，如果数据量十分的庞大，要搜索一个数据，将变得十分困难，在数据结构中搜索一个元素需要进行一系列的关键码比较。搜索的效率取决于搜索过程中比较的次数。因此要解决这个问题，将变得十分重要，因此，找到一个有效的方法变得十分重要，因此哈希查找的提出，极大的情况下是为了解决在搜索中的数据量较大的问题。
2、基本概念
构造一种存储结构，使元素的存储位置与它的关键码之间建立一个确定的对应函数关系：Hash()，那么每个元素关键码与结构中的一个唯一的存储位置相对应：Address = Hash(Key)，此处的Hash函数，将产生在哈希表中的唯一一个位置，利用这个位置从而存储数据，将极大的提高数据的存储与查找的效率。

• 在插入时，根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
• 在搜索时，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。该方式即散列方法(Hash Method)，在散列方 法中使用的转换函数叫着散列函数(Hashfunction)，构造出来的结构叫散列表(Hash Table)。
  3、哈希的基本思想—–>哈希表类似于数组
  以关键字K为自变量，通过一个确定的函数f，计算出对应的函数值f (k)，把这个值解释为关键字等于K的结点的存储地址。查找时，再根据要查找的关键字用同样的函数计算地址，然后到相应的存储单元取出要查找的结点。按这个思想建立的表，称为哈希表，称函数f 为哈希函数，称f (k)的值为哈希地址。
  4、

二、哈希函数的确定
1、hash函数构造的注意事项
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
2、hash函数的构造—–常见的哈希函数
（1）直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）=key或Hash（Key）= A*Key + B。
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
适合查找比较小且连续的情况。
例如：查找身高在165的男生与女生的情况，由于大部分的人的身高都在150-185这个区间，利用直接定址法，容易形成数据冗余的情况（当前数据占用其他元素的位置，从而使得数据一直在向后面找空余位置），从而不能更加准确的确定。
（2）除留余数法
设散列表中允许的地址数（表长）为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key % p p<=m,将关键码转换成哈希地址。
注意：在这里，一般不会给出表长，直接利用素数提供表长，这样极大的提高了效率，防止反复增容从降低效率。
常见的质数有
const int _PrimeSize = 28;
static const unsigned long _PrimeList [_PrimeSize] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
采用素数，可以极大的降低hash冲突。
（3）平方取中法
假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为散列地址；再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671或者710用作散列地址。平方取中法中所取的位数由表长决定。
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
例： K = 456 , K2 = 207936 若哈希表的长度m=102，则可取79（中间两位）作为哈希函数值。
（4）折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(注意：最后一部分位数不够时可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如：关键字是9876543210，散列表表长为三位，我们将它分成四组987|654|321|0|，
然后将它们叠加求和987+654+321+0=1962，再求后3位得到散列地址为962。有时可能这还不能够保证分布均匀，不妨从一段向另一端来回折叠后对齐相加。
比如将987和321反转，再与654和0相加，编程789+654+123+0=1566，此时的散列地址为566。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。
（5）选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数（利用库函数实现），通常应用于关键字长度不等时采用此法。
（6）设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

以上六种方法为基本常见的hash函数，了解并且熟练应用这些函数，对我们理解哈希查找有着重要的意义。

hash的出现解决了我们的第一个问题，但是就算再好的hash函数，也会偶尔产生一些冲突，因此解决hash函数的冲突，仍是我们非常重要的一个点。

三、hash冲突的解决
1、闭散列法
定义：闭散列也叫开地址法。设散列表的编址为0到m-1，当添加关键码key时通过散列函数hash(key)计算key的存放位置，但在存放时发现这个桶已经被另一个keyx占据了，即发生哈希冲突。如果表未被装满，表示在给定的范围内必然还有空位置，则可以把key存放到表中“下一个”空位中。简而言之：一旦发生冲突，就去寻找下一个空的散列表地址，只要散列表足够大，空的散列地址总能找到。找空桶的方法如下：
（1）线性探查
设给出一组元素，它们的关键码为：37,25,14,36,49,68,57,11，散列表为HT[12]，表的大小m =12，假设采用Hash(x) = x % p; // (p = 11) 11是最接近m的质数，就有：
Hash(37) = 4 Hash(25) = 3 Hash(14) = 3 Hash(36) = 3
Hash(49) = 5 Hash(68) = 2 Hash(57) = 2 Hash(11) = 0
存在hash表中如下所示：

由上图就可以看出，出现了大量的数据冗余问题，使得一个元素占用了不在其位置上的元素。
线性探查法容易产生数据“堆积”，即不同探查序列的关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索时间增加。怎么解决？接下来，利用下面的方法，将极大的解决这个问题
（2）二次探查
使用二次探查法，在表中寻找“下一个”空位置的公式为：
Hi = (H0 + i^2)%m, Hi = (H0 - i^2)%m, i = 1,2,3…，(m-1)/2
H0是通过散列函数Hash(x)对元素的关键码x进行计算得到的位置，m是表的大小。假设数组的关键码为37,25,14,36,49,68,57,11，假设取m=19，这样可设定为HT[19]，
采用散列函数Hash(x) = x % 19
Hash(37)=18 Hash(25)=6 Hash(14)=14 Hash(36)=17
Hash(49)=11 Hash(68)=11 Hash(57)=0 Hash(11)=11
采用二次探查法处理冲突：

3、双散列法
使用双散列方法，需要两个散列函数。第一个散列函数Hash()按关键码key计算其所在的位置H0 =Hash(key)。一旦发生冲突，利用第二个散列函数ReHash()计算该key到达“下一个”桶的位移，它的取值与key的值有关，要求它的取值应该是小于地址空间大小TableSize，且与TableSize互质的正整数。若设表的长度为m = TableSize，则在表中寻找“下一个”桶的公式为：j = H0 = Hash(key)，p = ReHash(key)； j = (j+p)%m; p是小于m且与m互质的整数。

即使有上面的解决方法，但是当哈希表中存储的元素特别多的时候，还是有极大的可能的存在冲突，因此要解决这个问题，我们需要引入一个概念，负载因子
散列表的负载因子a=填入表中的元素个数、散列表的长度
即，表中元素越多，产生冲突的可能性就越大。
研究表明当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空的，就不会有表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5；如果超出必须考虑增容。

四、hash表的增删元素
1、增加元素：hash表的存在，当然是为了往其中放元素，因此需要标识每一个位置的状态，如果他非空的话，则将元素不插入在这个位置，即使是将元素已经删除，也不能将元素插入在这个位置，这样做的目的是为了防止插入相同的元素。
2、删除元素，找到对应的下标，如果是要删除的元素，只要将其状态修改为删除即可，如果不相同，则一直向后查找，利用线性探测与二次探测即可。

有关hash算法的闭散列法的实现，在下一篇博客在提，现在，对于闭散列就这么的内容，希望可以帮助到大家。

只要不停的奔跑，才能不停留在原地！！！