LeetCode - 哈希表专题

• 前言
• 一、哈希表
• • 1. 分类
  • 2. 什么情况下要用哈希表？
  • 3. 冲突处理
  • • • ① 拉链法
      • • 含义
        • 操作
        • • 插入一个值 x
          • 查找一个值 x
      • ② 开放寻址法
      • • 含义
        • 操作
        • • 插入一个数 x
          • 查找一个数 x
• 哈希表代码实现
• • 1. 模拟散列表
• 二、刷题

        今天算法的内容是：哈希表。
 

将一个比较庞大的值域映射到一个比较小的区间（区间范围为 0 ~ N）。

例如，操作数的 个数 是10⁵, 操作数值的 范围 是 -10^9^ ~ 10^9^。在一个比较大的值域里面，从中选出来一些数 插入，选出另一些数 查询，选出来数的个数为 10^5^，能快速的支持 插入 和 查询 这两种操作。

思想：通过一个哈希函数，函数的输入为 x（-10⁹ ~ 10⁹ 值域内的一个数），输出为 0 ~ 10⁵ 的一个数，哈希函数的作用是可以将-10⁹ ~ 10⁹ 值域内的一个数内 映射 到 0 ~ 10⁵ 的一个数。

实现： x ∈ ∈ ∈ (-10⁹ ~ 10⁹ )，h 为哈希函数，h(x) ∈ ∈ ∈ ( 0 ~ 10⁵ )为哈希值，h(x) = x % 10⁵。

哈希冲突：因为 x 的范围大，不同的 x 可能映射成相同的 y，即将若干不一样的数映射成了同一个数，需要处理冲突 。

通过一个一维数组来存所有的哈希值，每一个位置都看作是一个 槽 ，将值映射到槽上，每一个槽上都拉一条 链，用来存储当前这个槽上已有的所有的数。

在算法题中哈希表只有 插入 和 查找 这两个操作，操作的时间复杂度都是 O(1)。

求 h(x)，h(x) 对应的是哪个槽，将 x 插到这个槽对应的链（单链表）上即可。

求 h(x)，看 h(x) 对应的是哪个槽，然后遍历一下这个槽对应的单链表，判断是否存在 x 即可。

开一个一维数组，数组的长度为数据范围的 2 ~ 3 倍，h(x) = k，找到第 k 个位置看其是否有数，如果有就跳到下一个位置，直到找到一个没有数的位置将 x 插入。

求 h(x) = k，找到第 k 个位置，然后从第 k 个位置开始往后找，直到找到第一个空的位置为止，然后将 x 插入。

h(x) = k，找到第 k 个位置，从第 k 个位置开始从前往后找，每一次先看一下当前位置有没有数，如果当前位置没有数说明 x 不存在，如果当前位置有数并且是 x 的话就证明找到了 x，如果当前位置有数但不是 x，那么往后看下一个位置，以此类推直到找到为止。

find 操作为核心操作。find(x)，如果 x 在哈希表中已经存在的话，返回 x 所在的位置，如果 x 在哈希表中不存在的话，返回的是 x 应该存储的位置。

AcWing 840. 模拟散列表 原题链接

// 开放寻址法
#include 
#include 

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

// 拉链法
#include 
#include 

using namespace std;

const int N = 100003;

int h[N], e[N], ne[N], idx;

void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}

int main()
{
    int n;
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if (*op == 'I') insert(x);
        else
        {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

LeetCode 1748. 唯一元素的和 原题链接

class Solution {
public:
    int sumOfUnique(vector& nums) {
        int sum = 0;
        vector heap(105, 0);

        for (auto num : nums) heap[num] ++;
        for (auto num : nums) {
            if (heap[num] == 1) 
                sum += num;
        }
        return sum;
    }
};

LeetCode 387. 字符串中的第一个唯一字符 原题链接

class Solution {
public:
    int firstUniqChar(string s) {
        vector heap(26, 0);
        for (auto c : s) heap[c - 'a'] ++;
        for (int i = 0; i < s.size(); i ++) {
            if (heap[s[i] - 'a'] == 1)
                return i;
        }
        return -1;
    }
};

LeetCode 1941. 检查是否所有字符出现次数相同 原题链接

class Solution {
public:
    bool areOccurrencesEqual(string s) {
        vector heap(26, 0);

        for (auto c : s) heap[c - 'a'] ++;
        int v = heap[s[0] - 'a'];

        for (int i = 0; i < 26; i ++) {
            if (heap[i] > 0 && heap[i] != v) 
                return false;
        }
        return true;
    }
};

LeetCode 448. 找到所有数组中消失的数字 原题链接

• 没有空间限制的情况下：开一个长度为 n的 heap数组用来标记 1-n每个数是否出现过，遍历整个 nums数组，标记一下所有出现过的数；之后再从 1-n遍历 heap数组将没有出现过的数输出；
• O(1) 的空间复杂度：对原数组进行修改，如果 x出现过，将 a[x]变成 -a[x]（标记），统计没有改变数的数量；

class Solution {
public:
    vector findDisappearedNumbers(vector& nums) {
        for (auto x : nums) {
            x = abs(x);
            if (nums[x - 1] > 0) nums[x - 1] *= -1; // 没有标记过，进行标记
        }
        vector ret;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] > 0) 
                ret.push_back(i + 1);
        }
        return ret;
    }
};

LeetCode 1512. 好数对的数目 原题链接

class Solution {
public:
    int numIdenticalPairs(vector& nums) {
        vector heap(105, 0);
        int ans = 0;

        for (int i = 0; i < nums.size(); i ++) {
            ans += heap[nums[i]];
            heap[nums[i]] ++;
        }
        return ans;
    }
};