哈希表基础（含代码演示）_哈希表代码c语言

一、什么是哈希表        

        哈希表，也称散列表，可以通过关键词的值进行查询和访问的数据结构。通常通过映射函数将关键字直接对应到表中的某个位置，用来加快查找速度，这个映射函数就是哈希函数，存放记录的数组叫做哈希表。

二、哈希表的应用

 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;
}