两数之和(LeetCode)——哈希表法(C语言)

上一篇文章留了个引子——用“哈希表”法来解决这个问题。

今天，我们来解决一下。为什么用哈希表法？很简单因为它——快！

讲解之前我们先来提出几个问题？

1)什么是“哈希表”？

2)怎么用“哈希表法”来解决这个问题？

什么是“哈希表”？

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

（摘自：百度百科）

其实 哈希表 就是一种 散列表 ，其英文叫做 “Hash table”，本身就是一种 数据结构 。包含 键值对（key-value），通过一个 key 值来直接访问数据，查找速度快。

看完这些仍然一头雾水对吧，下面举个简单的例子，我们应该就会更加理解哈希表。

日常生活中都使用过 字典、电话簿 等等。

字典通过什么来查找文字？其中一种方法是通过找汉字的首字母来进行确定范围，然后再在已经缩小后的范围中找取我们需要的汉字。

我要是想在电话簿中寻找 张三 该怎么找？首先通过张三的姓氏首字母 Z ，然后只用看 Z 中的人名即可。

李四	1233xxxxxx	L
王强	2341xxxxxx	W
张三	3478xxxxxx	Z

哈希表就类似于这样，可以看出其本质是“数组”。对于一个数据，提取它的key（关键值）通过哈希函数中特定的“加工”，将其得到一个值，将这个 值 放置到数组的固定位置。

（PS：哈希表的数据必须一一对应，否则将出现“哈希冲突”，因此一个好的哈希函数将减少冲突的产生）

怎么用哈希函数来解决问题？

这个我们将结合例题来讲解

讲解时我们先分开一个板块一个板块的讲，便于理解，最后我将完整的代码发出，大家自行理解。

struct hashTable //自定义数据结构
{
    int key;  //键
    int val;  //值
    UT_hash_handle hh;
};

 对下面这个代码做个必要的解释：

UT_hash_handle hh;

使定义的结构具有 “哈希性” ，它可以命名为任何名称。（这一步必须有！！！）

struct hashTable* hashtable; //定义哈希指针，指向前面的 hashTable 数据结构


struct hashTable* find(int ikey) //通过 key 值来查找
{
    struct hashTable* tmp; //定义指向 hashTable 的指针变量 tmp
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

同样进行解释：

    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;

第一个参数 hashtable 是哈希表，第二个参数是 ikey 的地址（一定要传递地址）。最后 tmp 是输出变量。当可以在哈希表中找到相应键值时，tmp 返回给定键的结构，当找不到时 tmp 返回NULL。

//重复性检查，当把两个相同key值的结构体添加到哈希表中时会报错

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey); //返回 ikey 值对应的节点it
    if (it == NULL) {  //如果没有找到，则创建项目添加
        struct hashTable* tmp = malloc(sizeof(struct hashTable)); //为 tmp 申请一个空间，
                                                                  //进行动态分配

        tmp->key = ikey, tmp->val = ival;//将结构体变量的键指向 ikey，将值指向 ival
        HASH_ADD_INT(hashtable, key, tmp); //向 hashtable 添加元素
    } else {  //如果能找到，则替换即可
        it->val = ival;  //将值val 替换成 ival
    }
}

解释：

HASH_ADD_INT(hashtable, key, tmp);

第一个参数 hashtable 是哈希表，第二个参数 key 是键字段的名称。最后一个参数 tmp 是指向要添加的结构的指针。

//实现两数相加功能
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;  //初始化
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);  /寻找满足条件的数据
        if (it != NULL) { //如果找到了
            int* ret = malloc(sizeof(int) * 2);  //为 ret 申请一个空间，进行动态分配
            ret[0] = it->val, ret[1] = i; //ret[0]为target-nums[i]对应的元素下标，ret[1]即为 
                                          //nums[i]对应元素下标

            *returnSize = 2;  //设置返回数组的长度为 2
            return ret;       //返回 ret
        }
        insert(nums[i], i); //如果没有找到，就将其插入进哈希表
    }
    *returnSize = 0; //遍历所有数据后仍未找到匹配元素，则设置返回数组的长度为 0
    return NULL;     //返回为空
}

最后附上完整的代码供大家学习

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

PS：代码来源

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）