3、哈希表、映射、集合的实现与特性

05 极客大学-算法训练营-覃超-第五课.pdf

实战题目 / 课后作业

• 有效的字母异位词（亚马逊、Facebook、谷歌在半年内面试中考过）

  /**
  * 计算每个字符串字母出现的次数
  * 1、遍历字符串s, 声明一个map, 以字母为key, 字母出现的次数为val, 统计每个字符串出现的次数
  * 2、遍历字符串t, 如果字符号中的字母在map中，则对应的次数减1
  * 3、遍历map中的values，判断val 是否为0
  */
  var isAnagram = function (s, t) {
  if (s.length !== t.length) {
    return false;
  }
  let strMap = new Map();
  for (let i = 0; i < s.length; i++) {
    strMap.set(s[i], (strMap.get(s[i]) || 0) + 1);
    strMap.set(t[i], (strMap.get(t[i]) || 0) - 1);
  }
  return [...strMap.values()].every((item) => {
    return item === 0;
  });
  };

• 字母异位词分组（亚马逊在半年内面试中常考）

  //     /**
  //      * 排序法
  //      * 1、声明一个map， 遍历数组
  //      * 2、以item的排序作为map 的key， 如果后续的item 是当前key的字母异位词，存放到当前key 的数组中
  //      * 3、如果不是，另存为一个map 的key
  //      * 4、遍历map的values
  //      */
  var groupAnagrams = function (strs) {
  let strMap = new Map();
  for (let str of strs) {
    let key = str.split("").sort().join("");
    if (strMap.has(key)) {
      let arrVal = strMap.get(key);
      arrVal.push(str);
      strMap.set(key, arrVal);
    } else {
      strMap.set(key, [str]);
    }
  }
  return [...strMap.values()];
  };

• 两数之和（亚马逊、字节跳动、谷歌、Facebook、苹果、微软、腾讯在半年内面试中常考）

Set & WeakSet

Set

ES6 新增的数据结构，类似于数组，但成员的值都是唯一的

操作方法

遍历方法

WeakSet

• weakSet的成员只能是对象 ```javascript const a = [[1,2],[3,4]]; const ws = new WeakSet(a) // 正确🙆 WeakSet([1,2],[3,4])

const b = [1,2] const ws2 = new WeakSet(b) // 错误🙅 Uncaught TypeError: Invalid value used in weak set

// 成为WeakSet的成员的是a数组的成员，而不是a数组本身，这意味着，数组的只能是对象

- weakSet中的对象都是弱引用 ==> 垃圾回收机制不考虑存放在weakSet中的对象引用 ==> **WeakSet不可遍历**
**
---
<a name="iqHTd"></a>
## Map & WeakMap
<a name="lNLtR"></a>
### Map
> 类似于对象，也是键值对的集合，但是“键”的范围不限于字符串（对象的键需要是字符串）
```javascript
// 只有对同一个对象的引用，Map结构才将其视为同一个键
const map = new Map()
map.set(['a'], 555)
map.get(['a']) // undefined
--------------------------------------
let arr = ['a']
const map2 = new Map()
map2.set(arr, 'arrVal')
ma2.get(arr) // arrVal

操作方法

遍历方法

WeakMap

• WeakMap只接受对象作为键名（null除外）不接受其他类型的值作为键名 ```javascript const map = new WeakMap() map.set(null, ‘null’) // Uncaught TypeError: Invalid value used as weak map key

map.set(Symbol(), ‘symbol’) // Uncaught TypeError: Invalid value used as weak map key ```

• WeakMap的键名所指向的对象不计入垃圾回收机制 ==> 垃圾回收机制不考虑存放在WeakMap中的对象引用 ==> WeakMap不可遍历