哈希表基础（含代码演示）
一、什么是哈希表
哈希表，也称散列表，可以通过关键词的值进行查询和访问的数据结构。通常通过映射函数将关键字直接对应到表中的某个位置，用来加快查找速度，这个映射函数就是哈希函数，存放记录的数组叫做哈希表。
二、哈希表的应用
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;
}腾讯云开发者
