Leetcode记录：哈希表

3 Aug 2024

哈希表 (Hash Table)

理论基础

哈希表是一种根据关键字key来访问值value的一种数据结构。它通过把key值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。因为本质上是通过索引来访问数组，所以哈希表的插入和查找的效率非常高，时间复杂度都是O(1)。相比于直接寻址法，它将全域缩小到可接受的范围。但存在一个问题：不同的key可能会计算出相同的索引，这就是哈希冲突(collision)

一个最简单的冲突解决方法是链接法(chaining)，在这种方法中，数组索引对应的空间并不直接存储数据，而是存储一个链表的地址，而数据存在链表中。这样发生冲突时，就可将冲突的key对应的数据存在同一个链表上，当需要取数据时，就先找到key对应的链表，然后遍历链表。

还有一种思想为开放寻址法：如果通过哈希函数计算出的索引所对应的空间已经被占用了，就再找一个还没被占用的空间将数据存进去。常见的体现开放寻址思想的方法有:

线性探测法: 简单来说就是从当前被占用的空间的索引开始，向下遍历整个数组，直到找到空闲空间为止。
双重哈希法: 使用多个哈希函数来计算索引，如果第一个哈希函数计算得到的索引所对应的空间已被占用，就用第二个，第二个被占用就用第三个，以此类推，直到计数出没被占用的空间对应的索引。

上面说的方法只能在一定程度上解决哈希冲突，因为毕竟数组的容量有限，当频繁插入数据时，因为数组的容量有限，所以就会使哈希冲突加剧，进而使链表的长度增加，链表的长度增加，就会使得查找的性能降低，这不是我们想看到的结果，所以要对数组扩容。一般装载因子（已插入元素的数量除以数组容量）超过某一阈值时就进行扩容。

因为之前插入的元素都是按照原数组的长度来计算索引的，所以一旦数组扩容后，长度改变，就要重新进行计算，然后将已插入的元素移动到新的位置上，所以数组扩容不仅仅只是将容量增大而已。

另外，我们不难发现哈希函数是整个哈希表的关键。一个好的哈希函数应该近似地满足简单均匀散列假设：每个关键字都被等可能的散列到槽位中的任何一个，并与其他关键字散列到哪个槽位无关。遗憾的是一般无法检查这一条件是否成立。但是有时如果我们知道关键字的概率分布，例如都是随机的实数并且独立均匀分布在$[0,1]$区间，那么哈希函数$h(k) = \lfloor km \rfloor$就能满足简单均匀散列条件。在实际应用中则要根据不同的情况要求来设计好的散列函数。

常见的哈希函数有以下几种：

除法散列法：通过取$k$除以$m$的余数，将关键字$k$映射到$m$个槽位中的某一个。当应用该方法时，应避免$m$取某些值，例如2的幂次，因为如果$m=2^p$的话，$h(k)$就是$k$的$p$个最低位有效数字。通常一个不太接近2的整数幂的素数是比较好的选择。
乘法散列法：先用关键字$k$乘上常数$A\in(0,1)$，并提取其小数部分；再用$m$乘上该小数并向下取整，即为$h(k)=\lfloor m(kA \space mod1)\rfloor$。该方法的优点是对$m$的选择不是很关键

对应STL数据结构

当我们想使用哈希法来解决问题的时候，我们一般会选择vector, set或者map数据结构。在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射	底层实现	key是否有序	key是否可以重复	能否更改key	查询效率	增删效率
std::map	红黑树	有序	否	否	O(log n)	O(log n)
std::multimap	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_map	哈希表	无序	否	否	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

例题

有效的字符异位词

Leetcode 242. 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

使用一个哈希表记录字母出现频数即可：

bool isAnagram(string s, string t) {
    if(s.length() != t.length())
        return false;
    unordered_map<char,int> sMap;
    for(auto c : s){
        sMap[c]++;
    }
    for(auto c :t){
        if(sMap[c] <= 0){
            return false;
        }else{
            sMap[c]--;
        }
    }
    return true;
}

两个数组的交集

Leetcode 349. 给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

一种方法是用两个集合，思路简单不详细写了，另一种就是排序+双指针，空间复杂度降低为 O(logm + logn)，时间复杂度上升为O(mlogm + nlogn)，该方法要注意的是要确保加入元素的唯一性，由于已经进行了排序，也就是要额外判断要加入的元素和最终数组的末尾元素是否相同:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    int length1 = nums1.size(), length2 = nums2.size();
    int index1 = 0, index2 = 0;
    vector<int> intersection;
    while (index1 < length1 && index2 < length2) {
        int num1 = nums1[index1], num2 = nums2[index2];
        if (num1 == num2) {
            // 保证加入元素的唯一性
            if (!intersection.size() || num1 != intersection.back()) {
                intersection.push_back(num1);
            }
            index1++;
            index2++;
        } else if (num1 < num2) {
            index1++;
        } else {
            index2++;
        }
    }
    return intersection;
}

快乐数

Leetcode 202. 编写一个算法来判断一个数 $n$ 是不是快乐数。「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为1，也可能是无限循环但始终变不到1。
如果这个过程结果为1，那么这个数就是快乐数。

一种方法是利用哈希集合检测循环：对于一个数，我们猜测会有以下三种可能：

最终会得到 1。
最终会进入循环。
值会越来越大，最后接近无穷大。

对于第三种情况，我们考虑对于 3 位数的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3 位为止。所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。

bool isHappy(int n) {
    unordered_set<int> numSet;
    while(n != 1){
        if (numSet.count(n)){
            return false;
        }
        numSet.insert(n);
        int sum = 0;
        while(n!=0){
            int b = n%10;
            sum += b*b;
            n = n/10;
        }
        n= sum;
    }
    return true;
}

既然会构成一个循环，那么我们就可以将这个过程看作是一个隐式的链表，我们要做的就是判断这个链表是否存在环路，那么我们利用快慢指针即可实现：

int getNext(int n) {
    int sum = 0;
    while(n!=0){
        int b = n%10;
        sum += b*b;
        n = n/10;
    }
    return sum;
}
bool isHappy(int n) {
    int slow = n;
    int fast = getNext(n);
    while (fast != 1 && slow != fast) {
        fast = getNext(fast);
        fast = getNext(fast);
        slow = getNext(slow);
    }
    return fast == 1;
}

两数之和

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

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hashtable;
    for (int i = 0; i < nums.size(); ++i) {
        auto it = hashtable.find(target - nums[i]);
        if (it != hashtable.end()) {
            return {it->second, i};
        }
        hashtable[nums[i]] = i;
    }
    return {-1,-1};
}

数据结构与算法