一、什么是哈希表
哈希表，也称散列表，可以通过关键词的值进行查询和访问的数据结构。通常通过映射函数将关键字直接对应到表中的某个位置，用来加快查找速度，这个映射函数就是哈希函数，存放记录的数组叫做哈希表。
二、哈希表的应用
1、普通方法查找key
要实现从包含n个整数的数组中擦护照整数key，以下为普通的方法。
通过循环进行逐一查询，效率低。
//从包含n个整数的数组中擦护照整数key //存在则返回1，不存在返回0 int find_key(int a[], int key) { int i =0; for(i = 0; i < n; i++) { if(key == a[i]) { return 1; } } return 0; }
2、哈希表查找目标数组中各元素出现次数
1） 先设置目标函数a[ ] ，初始化哈希表table[ ]，将哈希表所有函数初始化为0，方便在之后统计元素出现次数。
int main(void) { int a[] = { 2, 43, 2, 7, 8, 12, 9, 21 };//目标key int i = 0; int table[MAX_TABLE_LEN] = { 0 };//哈希表初始化 create_hash(a, 10, table); for (i = 0; i < MAX_TABLE_LEN; i++) { if (table[i] > 0) //当table[i]大于0的时候说明i这个元素在a中出现，出现次数为table[i] { printf(" % d apper % d times.\n", i, table[i]); } } }
2）在函数create_hash中用 i 遍历数组a中的n个函数，通过table[a[i]]++来记录a[i]出现的次数。在完成遍历table的下标即对应a中的元素大小，而下标对应的table[a[i]的大小即为a[i]]这个值的出现次数，该次数在table对应下表的大小上体现。
void create_hash(int a[], int n, int table[]) { int i = 0; for (i = 0; i < n; i++) { table[a[i]]++; } }
通过以上代码即可实现利用哈希表进行数组元素个数的统计。
3）用哈希表实现排序
void sort(int a[], int n) { int table[MAX_TABLE_LEN] = { 0 }; int i = 0; for (i = 0; i < n; i++) { table[a[i]]++;//哈希函数 记录每个元素出现的次数 } int j = 0; int k = 0; for (i = 0; i < MAX_TABLE_LEN; i++) { for (j = 0; j < table[i]; j++) { a[k++] = i;//用新数组a来从i = 0开始记录i的大小，实现从小到大排序 } } }
第一个for循环用来实现 2）中 数据 i 出现的次数，第二个外循环用来遍历table数组，内循环用来将每一个 i 在对应数量内进行遍历，将 i 的值记录在新数组a中，实现排序。
3、 当处理指数，浮点数，字符串，数组，对象等元素时哈希表的应用
在遇到以上问题时需要使用哈希函数，我们可以将待存储的数据转换为表长范围内的整数，然后再使用数组下表进行访问。
整数类型的哈希函数
可以直接取余表长得到对应哈希值
int int_func(int key)
{
return key % MAX_TABLE_LEN;
}
字符串的哈希函数
最简单的表示为遍历字符串当中的字符，将他们的ASC||码相加得到整数，再用整数取余表长得到哈希值
int string_func(const char* key)
{
int sum = 0;
while (*key)
{
sum += *key;//遍历相加字符串中的字符ASC||
key++;
}
return sum % MAX_TABLE_LEN;//取余表长
}
三、哈希表使用中的问题
由于取余的原因，哈希函数可能将不同的数据映射在同一组下标上，这样会使产生冲突，无法正确计算。所以可以使用一些方法来进行避免冲突，如线性探测 ，拉链法。该类方法将会在下一篇中进行讲解，谢谢阅读。
四、具体题例
leetcode第349题、两个数组的交集
题目描述：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) { int hash1[1000] = { 0 }; int hash2[1000] = { 0 }; for(int i = 0; i < nums1Size; i++) { hash1[nums1[i]]++; } for(int i = 0; i < nums2Size; i++) { hash2[nums2[i]]++; } int a[1000] = { 0 }; int k = 0; for(int i = 0; i < 1000; ++i) { if((hash1[i] > 0) && (hash2[i] > 0)) { a[k++] = i; } } *returnSize = k; int* result = (int*)malloc(k * sizeof(int)); for(int i = 0; i < k; i++) { result[i] = a[i]; } return result; }
