一、啥是哈希表

哈希表又称散列表，其实就是和数组、链表一样的是一种数据结构，在你从来没有接触过这个概念的时候，觉得神秘而不可探测，其实就是一纸老虎，人狠话不多，先上一个相对官方的概念定义：

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。建立了关键字与存储位置的映射关系，公式如下：

存储位置 = f（关键字）

这里把这种对应关系f称为散列函数，又称为哈希（Hash）函数。

采用散列技术将记录存在在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。那么，关键字对应的记录存储位置称为散列地址。

散列技术既是一种存储方法也是一种查找方法。散列技术的记录之间不存在什么逻辑关系，它只与关键字有关，因此，散列主要是面向查找的存储结构。

人狠话不多，直接例子：

例1：现在我要你存储4个元素 13 7 14 11，你将如何存储？？？

答：显然，我们可以用数组来存。也就是：a[1] = 13; a[2] = 7; a[3] = 14; a[4] = 11; 当然，我们也可以用Hash来存。下面给出一个简单的Hash存储：

先来确定那个函数。我们就用h(key) = key%5;(这个函数不用纠结，我们现在的目的是了解为什么要有这么一个函数)。那么 对于第一个元素 h(13) = 13%5 = 3; 也就是说13的下标为3；即Hash[3] = 13; 对于第二个元素 h(7) = 7 % 5 = 2; 也就是说7的下标为2; 即Hash[2] = 7; 同理，Hash[4] = 14; Hash[1] = 11; 好了，存现在是存好了。但是，这并没有体现出Hash的妙处，现在我要你查找11这个元素是否存在。你会怎么做呢？ 当然，对于数组来说，那是相当的简单，一个for循环就可以了。也就是说我们要找4次。这是很笨的办法，因为为了找一个数需要把整个序列循环一遍才行，太慢！

下面我们来用Hash找一下：

首先，我们将要找的元素11代入刚才的函数中来映射出它所在的地址单元。也就是h(11) = 11%5 = 1 了。下面我们来比较一下Hash[1]?=11, 这个问题就很简单了。

也就是说我们就找了1次。我咧个去， 这个就是Hash的妙处了。

那么，怎么设计哈希函数呢，上边的mod 5，我还mod 8 呢，是不是很气？接下来咱们就看看哈希函数的设计

二、哈希函数的设计

1 直接定址法 　　取关键字或者关键字的某个线性函数为Hash地址，即address(key)=a*key+b;如知道学生的学号从2000开始，最大为4000，则可以将address(key)=key-2000作为Hash地址。

2 平方取中法 　　对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取中间的两位数{72，89，00}作为Hash地址。

3 折叠法 　　将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。

4 除留取余法 　　如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p。

在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。

三、Hash表大小的确定

Hash表大小的确定也非常关键，如果Hash表的空间远远大于最后实际存储的记录个数，则造成了很大的空间浪费，如果选取小了的话，则容易造成冲突。在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数，则需要动态维护Hash表的容量，此时可能需要重新计算Hash地址。

四、冲突的解决

冲突的发生：比如有一组关键字{12，13，25，23，38，34，6，84，91}，Hash表长为14，Hash函数为address(key)=key，当插入12，13，25时可以直接插入，而当插入23时，地址1被占用了，发生了冲突现象，因此需要办法来解决，否则记录无法进行正确的存储。通常情况下有2种解决办法：

1 开放定址法 　　即当一个关键字和另一个关键字发生冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。比较常用的探测方法有线性探测法，比如有一组关键字{12，13，25，23，38，34，6，84，91}，Hash表长为14，Hash函数为address(key)=key，当插入12，13，25时可以直接插入，而当插入23时，地址1被占用了，因此沿着地址1依次往下探测(探测步长可以根据情况而定)，直到探测到地址4，发现为空，则将23插入其中。

2 链地址法 　　采用数组和链表相结合的办法，将Hash地址相同的记录存储在一张线性表中，而每张表的表头的序号即为计算得到的Hash地址。如上述例子中，采用链地址法形成的Hash表存储表示为：

hash.jpg

虽然能够采用一些办法去减少冲突，但是冲突是无法完全避免的。因此需要根据实际情况选取解决冲突的办法。

五、Hash表的平均查找长

Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。 查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数； 查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。

下面的例子有助于理解。

例1

将关键字序列{7, 8, 30, 11, 18, 9, 14}散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，长度为10，即{0, 1,2, 3, 4, 5, 6, 7, 8, 9}。散列函数为： H(key) = (key * 3) % 7，处理冲突采用线性探测再散列法。

求等概率情况下查找成功和查找不成功的平均查找长度。

解：

1 求散列表

H(7) = (7 * 3) % 7 = 0 H(8) = (8 * 3) % 7 = 3 H(30) = 6 H(11) = 5 H(18) = 5 H(9) = 6 H(14) = 0

按关键字序列顺序依次向哈希表中填入，发生冲突后按照“线性探测”探测到第一个空位置填入。 H(7) = 0，key = 7应插在第0个位置，因为第0个位置为空，可以直接插入。 H(8) = 3，key = 8应插在第3个位置，因为第3个位置为空，可以直接插入。 H(30) = 6，key = 30应插在第6个位置，因为第6个位置为空，可以直接插入。 H(11) = 5，key = 11应插在第5个位置，因为第5个位置为空，可以直接插入。 H(18) = 5，key = 18应插在第5个位置，但是第5个位置已经被key=11占据了，所以往后挪一位到第6个位置，但是第6个位置被key=30占据了，再往后挪一位到第7个位置，这个位置是空的，所以key=18就插到这个位置 H(9) = 6，key = 9应插在第6个位置，但是第6个位置已经被key = 30占据，所以需要往后挪一位到第7个位置，但是第7个位置已经被key = 18占据，所以再往后挪移到第8个位置，这个位置是空的，所以key = 9就插到这个位置。 H(14) = 0，key = 14应插在第0个位置，但第0个位置已被key=7占据，所以往后挪移一位到第1个位置，这个位置是空的，所以key=14就插到这个位置。

最终的插入结果如下表所示：

address0123456789key714 8 1130189 

2 求查找成功的平均查找长度

查找7，H(7) = 0，在0的位置，一下子就找到了7，查找长度为1。 查找8，H(8) = 3，在3的位置，一下子就找到了8，查找长度为1。 查找30，H(30) = 6，在6的位置，一下子就找到了30，查找长度为1。 查找11，H(11) = 5，在5的位置，一下子就找到了11，查找长度为1。 查找18，H(18) = 5，第一次在5的位置没有找到18，第二次往后挪移一位到6的位置，仍没有找到，第三次再往后挪移一位到7的位置，找到了，查找长度为3。 查找9，H(9) = 6，第一次在6的位置没找到9，第二次往后挪移一位到7的位置，仍没有找到，第三次再往后挪移一位到8的位置，找到了，查找长度为3. 查找14，H(14) = 0，第一次在0的位置没找到14，第二次往后挪移一位到1的位置，找到了，查找长度为2。

所以，查找成功的平均查找长度为(1 + 1 + 1 + 1 + 3 + 3 + 2) / 7 = 12 / 7。

3 求查找不成功的平均查找长度

查找不成功，说明要查找的数字肯定不在上述的散列表中。 因为这里哈希函数的模为7，所以要查找的数的初始地址只可能位于0~6的位置上。 地址0，到第一个关键字为空的地址2需要比较3次，因此查找不成功的次数为3。比如要查找的数为28，H(28) = (28 * 3) % 7 = 0。即28对应的地址是0，由于存放在0位置的数是7，所以往后挪移一位，发现在1位置存放的数是14，继续往后挪一位，发现位置2上没有数。至此就知道28不在这个哈希表里，即查找28失败。 地址1，到第一个关键字为空的地址2需要比较2次，因此查找不成功的次数为2。 地址2，到第一个关键字为空的地址2需要比较1次，因此查找不成功的次数为1。 地址3，到第一个关键字为空的地址4需要比较2次，因此查找不成功的次数为2。 地址4，到第一个关键字为空的地址4需要比较1次，因此查找不成功的次数为1。 地址5，到第一个关键字为空的地址9需要比较5次，因此查找不成功的次数为5。 比如要查找的数为4，H(4) = (4 * 3) % 7 = 5，所以从地址5开始查找，最终发现地址5、地址6、地址7、地址8上存放的数都不是5，并且地址9的位置上没放数据，至此可知5不在这个哈希表里。 地址6，到第一个关键字为空的地址9需要比较4次，因此查找不成功的次数为4。 所以，查找不成功的平均查找长度为（3 + 2 + 1 + 2 + 1 + 5 + 4）/ 7 = 18 / 7。

六、C语言的实现

/*采用数组实现哈希表*/ #include<stdio.h> #define DataType int #define Len 10 typedef struct HashNode { DataType data; //存储值 int isNull; //标志该位置是否已被填充 }HashTable; HashTable hashTable[Len]; void initHashTable() //对hash表进行初始化 { int i; for(i = 0; i<Len; i++) { hashTable[i].isNull = 1; //初始状态为空 } } int getHashAddress(DataType key) //Hash函数 { return key * 3 % 7; } int insert(DataType key) { int address = getHashAddress(key); if(hashTable[address].isNull == 1) //没有发生冲突 { hashTable[address].data = key; hashTable[address].isNull = 0; } else //当发生冲突的时候 { while(hashTable[address].isNull == 0 && address<Len) { address++; //采用线性探测法，步长为1 } if(address == Len) //Hash表发生溢出 return -1; hashTable[address].data = key; hashTable[address].isNull = 0; } return 0; } int find(DataType key) { int address = getHashAddress(key); while( !(hashTable[address].isNull == 0 && hashTable[address].data == key && address<Len)) { address++; } if( address == Len) { address = -1; } return address; } int main(int argc, char *argv[]) { int key[]={7,8,30,11,18,9,14}; int i; initHashTable(); for(i = 0; i<7; i++) { insert(key[i]); } for(i = 0; i<7; i++) { int address; address = find(key[i]); printf("key:%d\t address:%d\n", key[i],address); } return 0; } //运行结果 key:7 address:0 key:8 address:3 key:30 address:6 key:11 address:5 key:18 address:7 key:9 address:8 key:14 address:1

最后在加上一个用哈希表的LeetCode的例子：

 

例：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true

用C语言加哈希表实现如下：

bool canConstruct(char * ransomNote, char * magazine) { int hash[26] = {0}; for (int i = 0; i < strlen(magazine); i++) { hash[magazine[i] - 'a'] += 1; } for (int i = 0; i < strlen(ransomNote); i++) { hash[ransomNote[i] - 'a'] -= 1; if (hash[ransomNote[i] - 'a'] < 0) { return false; } } return true; }

用C++没用哈希表实现如下：

#include <string> class Solution { public: bool canConstruct(string ransomNote, string magazine); }; bool Solution::canConstruct(string ransomNote, string magazine) { if (ransomNote.empty() ) { return true; } if ( magazine.empty() || (ransomNote.size() > magazine.size()) ) { return false; } for (int i = 0; i < ransomNote.size(); i++) { std::string::size_type pos = magazine.find(ransomNote[i]); if (pos != -1) { magazine.erase(pos, 1); continue; } else { return false; } } return true; }