[数据结构]哈希表

:::success

• 2006. 差的绝对值为 K 的数对数目
• 1001. 网格照明

:::

数组代替哈希表进行统计， 如：数字、字母（126） :::warning

• 1189. “气球” 的最大数量 :::
  散列表也叫作 哈希表（hash table），这种数据结构提供了 键（Key）和 值（Value）的映射关系。只要给出一个 Key，就可以高效查找到它所匹配的 Value，时间复杂度接近于 O(1)O(1)。

哈希表 是一种使用 哈希函数 组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合和哈希映射。

• 哈希集合 是 集合 的实现方式之一，用于存储 非重复值。
• 哈希映射 是 映射 的实现之一，用于存储 (key, value) 键值对。

在 标准模板库 的帮助下，哈希表是 易于使用的。大多数常见语言（如 Java，C ++ 和 Python）都支持哈希集合和哈希映射。

• 写操作 put。 可能出现哈希碰撞（冲突）
• 读操作 get。
• 扩容 resize。考虑：
  • hashmap的当前长度
  • hashmap的负载因子

数组 VS 哈希表

一般查找，经过关键字逐个判断对比 。
hash优势在于快速实现查找、插入和删除。
hash的关键在于实现一个简单、均匀、存储利用率高的散列函数。

哈希表的 原理 是什么？

如何 设计 哈希表？如何解决 哈希冲突？

• 开放地址法 （增量）
  • 线性探测再扩散
  • 二次探测再散列
  • 伪随机探测再散列
• 链地址法
• 公共溢出区法（先来先放， 其余咱放公共区）

常用

• 开放寻址法。 已被占用， 向后移动寻找空位置
• 链表法。

如何使用 哈希集合 解决与重复元素相关的问题？

如何使用 哈希映射 解决与滑动窗口相关的问题？

如何在使用哈希表时设计正确的键？

实现哈希表

705. 设计哈希集合

class MyHashSet {
    base: number;
    data: Array<Array<number>>;
    constructor() {
        this.base = 769;
        this.data = Array.from({ length: this.base }, () => new Array());
    }
    hash(key: number): number {
        return key % this.base;
    }
    add(key: number): void {
        const h = this.hash(key);
        for (let item of this.data[h]) {
            if (item == key) {
                return;
            }
        }
        this.data[h].push(key);
    }
    remove(key: number): void {
        const h = this.hash(key);
        const items = this.data[h];
        for (let i = 0; i < items.length; i++) {
            if (items[i] == key) {
                items.splice(i, 1)
                return;
            }
        }
    }
    contains(key: number): boolean {
        const h = this.hash(key);
        for (let item of this.data[h]) {
            if (item == key) {
                return true;
            }
        }
        return false;
    }
}

706. 设计哈希映射

练习1:

剑指 Offer 50. 第一个只出现一次的字符

hashTable用于存储是否重出现的状态, true/false 来标记

var firstUniqChar = function(s) {
    if (s.length == 0) return " ";
    let hashTable = new Map();
    for (let i = 0; i < s.length; i++) {
        let cur = s.charAt(i);
        if (hashTable.has(cur)) {
            hashTable.set(cur, false)
        } else {
            hashTable.set(cur, true)
        }
    }
    for (let k of hashTable.keys()) {
        if (hashTable.get(k)) {
            return k
        }
    }
    return " ";
};

剑指 Offer 48. 最长不含重复字符的子字符串

🔑 滑动窗口+哈希表
hashTable存储最近一次访问的位置， Number: index来标记

var lengthOfLongestSubstring = function(s) {
    // 滑动窗口+哈希表
    // if (s.length < 2) return s.length;
    let left = 0;
    let hashTable = new Map();
    let res = 0;
    for (let right = 0; right < s.length; right++) {
        let cur = s.charAt(right)
        if (!hashTable.has(cur) || left > hashTable.get(cur)) {
            res = Math.max(res, right - left + 1)
        } else if (left <= hashTable.get(cur)) {
            left = hashTable.get(cur) + 1
        }
        hashTable.set(cur, right)
    }

    return res
};

练习2：

面试题 01.02. 判定是否互为字符重排

var CheckPermutation = function(s1, s2) {
    let n1 = s1.length, n2 = s2.length;
    if (n1 != n2) return false;
    let counter = {};
    for (let i=0; i<n1; i++) {
        let cur1 = s1.charAt(i), cur2 = s2.charAt(i);
        counter[cur1] = (counter[cur1] || 0) + 1;
        counter[cur2] = (counter[cur2] || 0) - 1;
    }
    return Object.values(counter).every(v => v == 0);
};

练习3

1640. 能否连接形成数组

case 1： arr = [85], pieces = [[85]] => true
Map(1) { 85 => [ 85 ] }
[ 85 ]

case 2: arr = [15,88], pieces = [[88],[15]] => true

Map(2) { 88 => [ 88 ], 15 => [ 15 ] }
[ 15 ]
[ 88 ]

case 3: arr = [49,18,16], pieces = [[16,18,49]] => false

Map(1) { 16 => [ 16, 18, 49 ] }
undefined

case 4: arr = [91,4,64,78], pieces = [[78],[4,64],[91]] => true

Map(3) { 78 => [ 78 ], 4 => [ 4, 64 ], 91 => [ 91 ] }
[ 91 ]
[ 4, 64 ]
[ 78 ]

LC练习

350. 两个数组的交集 II

var intersect = function(nums1, nums2) {
    let counter = {};
    for (let num of nums1) {
        counter[num] = (counter[num] || 0) + 1;
    }
    let res = [];
    for (let num of nums2) {
        if (counter[num] > 0) {
            res.push(num);
            counter[num] -= 1;
        }
    }
    return res;
};

970. 强整数

暴力法+哈希表