两数之和(哈希表)

Intro

第一题，两数之和，借此学习哈希表的使用方法

---

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

来源：LeetCode

题解

暴力解法(C++/C)

void direct(vector<int> nums, int target) {
    int i, j;
    for (i = 0; i < nums.size() - 1; i++)
    {
        for (j = i + 1; j < nums.size(); j++)
        {
            if (nums[i] + nums[j] == target)
            {
				return {i,j};
            }
        }
    }
    return {i,j};
}

解析:嵌套遍历，时间复杂度为 $O(n^2)$

哈希表(C++/C)

void hashmap(vector<int> nums, int target) {
    map<int, int> a;  //建立hash表存放数组元素
    for (int i = 0; i < nums.size(); i++) {
        a.insert(map<int, int>::value_type(nums[i], i));
    }
    for (int i = 0; i < nums.size(); i++) {
        if (a.count(target - nums[i]) > 0 && (a[target - nums[i]] != i)) {  //判断能否找到并且不是自己本身
            cout << i << endl;
            cout << a[target - nums[i]] << endl;
            break;
        }
    }
}

时间复杂度为 $O(n)$

哈希表

定义

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

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

摘自百度百科

个人理解

从一组数据中查询特定的值，按最原始的方法去遍历搜索无疑是最慢的，如果该值处于最后一位，时间花费就会很大。但是我们可以发现这些值之间会存在某种特点的关系，我们可以按照这些关系进行排序，比如说人名，我们可以按照姓名的首字母来排序，这样搜索起来，通过索引下标，我们就可以快速找到需要的数值。这就是通过一些特定的方法去得到一个特定的值，类似于映射函数，这里叫做哈希函数（hash function）

但是，这种方式有时会导致多个值(value)有了相同的hash值，这就是哈希冲突或者哈希碰撞

为了解决碰撞，实现哈希表可以有以下两种方式：

• 数组 + 链表
• 数组 + 二叉树

哈希冲突

上回我们说到哈希函数加工后得到的下标可能会出现冲突的情况。我们知道哈希表实际上是个数组，既然是个数组，对于哈希冲突，我们可以用开放寻址法和拉链法来解决。

开放寻址法

如果哈希表的索引1下标被占用，那么可以往下寻找，看2号下标是否也被占用，如果没，则把entry（键值对）插入进这个下标，如果也被占用了，则继续往下搜寻，Java中的ThreadLocal正是使用的开放寻址法

哈希扩容

使用开放寻址法时一直找不到可用的下标怎么办。当使用开放寻址时，如果哈希表被占用的过多，哈希冲突的可能性会大大增加，这时候就要进行哈希扩容，我们引入一个概念叫增长因子

增长因子

增长因子大概指的是已经被占用的空间和总空间的比例，例如总空间大小为10，被占用了6，则增长因子为0.6

当增长因子大于一定值时，哈希表需要进行扩容并且重新hash一遍，何谓重新哈希一遍，指的是重新建立一个大小为原来两倍的哈希表并且把原来的所有entry按照新的哈希函数排到新的数组（哈希表）里面

拉链法

拉链法引入了链表，如果1号下标被占用，但又有entry要使用1号下标时，原来的entry(1)需要保留一个next指针来指向entry(2/3/4/5),这就像拉链一样，一个entry后面接了n个entry,但是过长的链表势必会引起性能问题，所以当链表长度大于一定值时，结构要变为树结构

如何通过哈希表查询

如果我们已经按照姓名首字母排序了一个哈希表，假如我们要查询王五这个人，那么就去w那里查，如果第一个不是王五，那么就看第二个，这样就可以快速查询到数据

如何设计一张哈希表

哈希表的核心无疑是哈希函数，好的哈希函数可以避免大多数的哈希冲突，设计哈希函数的方法有很多，如直接定址法，数字分析法，折叠法，随机数法和除留余数法等等，这些就以后再探讨了