哈希表、映射、集合

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

应用场景：

• 电话簿
• 用户信息表
• 缓存（LRU Cache）
• 键值对存储（Redis）

不同的值通过散列函数得到的值相同的现象，叫做哈希碰撞（Hash Collisions）。

这种情况可以通过链表的方式解决。如果很多的元素堆积，会导致链表的长度增加，如果链表很长，查询效率会退化，从 O(1) 退化到 O(n) 。所以需要设计好的哈希函数，这样会使发生哈希碰撞的概率很小，这样，在平均时刻的查询时间就是 O(1)。

工业级应用中，通常使用 Map 和 Set，它们是从哈希表基础上抽象出来的。

Java Set 文档
Java Map 文档

HashSet 在 Java 中实际上就是使用的 HashMap。
HashMap 实现比较复杂，Node 分为 HashNode 和 TreeNode 两种，可以研究一下 put（putVal） 和 get（getNode） 方法。

HashMap 的复杂度可以看图中的 Hash Table。
TreeMap 和 TreeSet 复杂度可以看图中的 Red-Black Tree。高级语言的 TreeMap 和 TreeSet 都是通过红黑树来实现的。

有效的字母异位词（亚马逊、Facebook、谷歌在半年内面试中考过）
字母异位词分组（亚马逊在半年内面试中常考）
两数之和（亚马逊、字节跳动、谷歌、Facebook、苹果、微软、腾讯在半年内面试中常考）

// 有效的字母异位词
// 异位词：字母出现的次数一致，但是顺序不同

// 思路1：暴力，sort 排序，比较 sorted_str 是否相等，O(nlogn)
// 思路2：hash 表，map 统计字符频次，判断两个字符串出现频次一致

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  if (s.length != t.length) return false;

  const s1 = s.split('');
  const t1 = t.split('');

  s1.sort();
  t1.sort();

  return s1.join() === t1.join();
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  if (s.length != t.length) return false;

  const letters = new Array(26).fill(0);

  const base = 'a'.charCodeAt();

  for (const i of s) {
    letters[i.charCodeAt() - base]++;
  }
  for (const i of t) {
    if (!letters[i.charCodeAt() - base]) return false;
    letters[i.charCodeAt() - base]--;
  }

  return true;
};

// 字母异位词分组

// 思路1：排序做法
// 思路2：计数

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  const map = new Map();

  for (const str of strs) {
    const key = str.split('').sort().join();

    map.has(key) ? map.get(key).push(str) : map.set(key, [str]);
  }

  return Array.from(map.values());
};

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  const map = new Map();

  const base = 'a'.charCodeAt();

  for (const str of strs) {
    const letters = new Array(26).fill(0);

    for (const s of str) {
      letters[s.charCodeAt() - base]++;
    }

    const key = letters.join();

    map.has(key) ? map.get(key).push(str) : map.set(key, [str]);
  }

  return Array.from(map.values());
};

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  const cache = {};
  const base = 'a'.charCodeAt();

  for (const str of strs) {
    const letters = new Array(26).fill(0);

    for (const s of str) {
      letters[s.charCodeAt() - base]++;
    }

    // 对象存储时，会调用 toString 方法作为 key，但是执行效率好像也不高
    cache[letters] ? cache[letters].push(str) : cache[letters] = [str];
  }

  return Object.values(cache);
};

// 两数之和
// target - a 是否在 map 中

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const map = new Map();

  let curr;

  for (let i = 0; i < nums.length; i++) {
    curr = target - nums[i]

    if (map.has(curr)) {
      return [map.get(curr), i];
    }
    map.set(nums[i], i);
  }

  return [];
};