📚 哈希表 Map, 集合 Set

Map 和 Set 的底层结构都是用哈希表来实现。
哈希表，是根据关键码值而直接进行访问的数据结构。通过关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数也叫做散列函数，也叫哈希函数，存放记录的数组叫做哈希表。
哈希函数有可能会导致哈希碰撞。

经常用于需要键值对存储的地方

  • 电话号码本
  • 用户信息表


🏫 经典题目

1. 两数之和(最优解法: 哈希表)

两数之和除了 sort 之后，左右夹逼的解法，最优解法是哈希表，时间复杂度为n
遍历到数字 a 时，用 target - a，就会得到 b，若 b 存在于哈希表中，我们就可以直接返回结果了。若 b 不存在，那么我们需要将 a 存入哈希表，好让后续遍历的数字使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
var twoSum = function (nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const a = nums[i];
    const b = target - nums[i];
    if (map.has(b)) {
      return [map.get(b), i];
    } else {
      map.set(a, i);
    }
  }
  return [];
};


242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 数组是一个性能更优的哈希表
const isAnagram = (s, t) => {
  if (s.length !== t.length) return false;
  const counter = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    counter[s[i].charCodeAt() - 97]++;
    counter[t[i].charCodeAt() - 97]--;
  }
  for (let j = 0; j < 26; j++) {
    if (counter[j] != 0) {
      return false;
    }
  }
  return true;
};