Map/set WeakMap/WeakSet hash

发表于
字数统计 1.5k 字 | 阅读时长 5 分钟

javascript Map/set WeakMap/WeakSet hash

什么是 hash

hash(散列，hash)指的是把任意长度的一段数据通过 Hash 算法映射到固定长度的一段域上。常见的 hash 算法有 md5，sha1 等。

好的 hash 算法的特点有：

  1. 不可以反推原数据
  2. 输入微小的改动都会导致输出的 hash 值发生巨大变化
  3. 哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
  4. hash 算法的冲突概率要小

Map

基于 hash 的一种数据结构，以键值对存储数据。

创建

1
2
3
4
5
6
7
8
9
10
11
12
// 使用嵌套数组初始化映射 const m1 = new Map([
      ["key1", "val1"],
      ["key2", "val2"],
      ["key3", "val3"]
    ]);
    alert(m1.size); // 3
// 使用自定义迭代器初始化映射 const m2 = new Map({
      [Symbol.iterator]: function*() {
        yield ["key1", "val1"];
        yield ["key2", "val2"];
        yield ["key3", "val3"];
} });

特性

  1. Map 的 key 可以是任意类型的值。
  2. Map 中的元素会按照插入的顺序排序。
  3. Map 是可迭代对象，因此可以对其使用for of 和 forEach

与 object 的不同

  1. object key 只能是 number，string 或 symbol
  2. 元素不按照插入顺序，非负整数会最先被列出，排序是从小到大的数字顺序。然后所有字符串，负整数，浮点数会被列出，顺序是根据插入的顺序。最后才会列出 Symbol，Symbol 也是根据插入的顺序进行排序的。
  3. Map 上修改 key 对应 value 时不会覆盖原型，object 会。
  4. object 上的 key 是不可迭代的，只能使用 for in 或者 Object.keys 访问

可枚举可迭代指得是什么

可迭代对象指的是实现了 @@iterator 方法，符合了可迭代协议。一些对象例如 Array,Map 就是如此，被称为内置可迭代对象。object 则没有实现@@iterator 因此不可迭代

实现@@iterator 方法意味着这个对象或者它的原型上一定会有一个 key 等于@@iterator 的属性，这个属性可以用Symbol.iterator访问得到

1
2
3
4
5
new Map()[Symbol.iterator]
// ƒ entries() { [native code] }
//map的@@iterator 方法叫entries
new Map().entries()
// MapIterator {}

当一个对象需要被迭代的时候（比如被置入一个 for…of 循环时），首先，会不带参数调用它的 @@iterator 方法，然后使用此方法返回的迭代器获得要迭代的值。

值得注意的是调用此零个参数函数时，它将作为对可迭代对象的方法进行调用。 因此，在函数内部，this 关键字可用于访问可迭代对象的属性，以决定在迭代过程中提供什么。

要实现迭代器协议，就必须在 Symbol.iterator 实现一个方法，方法返回了一个 next 函数，next 函数会返回一个对象包含 value 和 dome，调用.next 就可以遍历数据，并且遇到 yield 为止

可枚举

可枚举属性是指那些内部 “可枚举” 标志设置为 true 的属性。对于通过直接的赋值和属性初始化的属性，该标识值(enumerable)默认为即为 true。但是对于通过 Object.defineProperty 等定义的属性，该标识值默认为 false。可枚举的属性可以通过 for…in 循环进行遍历（除非该属性名是一个 Symbol），或者通过 Object.keys()方法返回一个可枚举属性的数组。Object.getOwnPropertyNames()遍历自身对象的所有属性，包括可枚举不可枚举，但是原型上的属性是无法遍历的。

选择 Map 还是 object

大量插入删除操作时使用 map，大量查找 object

使用 Map：1.储存的键不是字符串/数字/或者 Symbol 时，选择 Map，因为 Object 并不支持 2.储存大量的数据时，选择 Map，因为它占用的内存更小 3.需要进行许多新增/删除元素的操作时，选择 Map，因为速度更快 4.需要保持插入时的顺序的话，选择 Map，因为 Object 会改变排序 5.需要迭代/遍历的话，选择 Map，因为它默认是可迭代对象，迭代更为便捷使用 Object：只是简单的数据结构时，选择 Object，因为它在数据少的时候占用内存更少，且新建时更为高效需要用到 JSON 进行文件传输时，选择 Object，因为 JSON 不默认支持 Map 需要对多个键值进行运算时，选择 Object，因为句法更为简洁需要覆盖原型上的键时，选择 Object
链接：https://zhuanlan.zhihu.com/p/358378689

WeakMap

WeakMap 中“weak”表示弱映射的键是“弱弱地拿着”的。意思就是，这些键不属于正式的引用， 不会阻止垃圾回收。value 的引用只要值还在则不会被垃圾回收

WeakMap 内部有多少个成员，取决于垃圾回收机制有没有运行，运行前后很可能成员个数是不一样的，而垃圾回收机制何时运行是不可预测的，因此 ES6 规定 WeakMap 不可遍历。

Set

可以看作增强 map，绝大部分差不多。但是 set 中元素不会重复

WeakSet

WeakMap 的键是弱引用，weakSet 值是弱引用会被 gc 回收

用 Map 实现 lruCache

lru 的意思是最短最近使用，也就是说缓存中的数据在获取到后要把它移动到最开头，同时新插入的数据也是要按照顺序的，正好 map 就是会自动维护元素顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class LRUCache {
  cache = new Map()
  capacity
  //capacity是缓存的大小
  constructor(capacity) {
    this.capacity = capacity
  }
  get(key) {
    if (this.cache && this.cache.has(key)) {
      const val = this.cache.get(key)
      this.cache.delete(key)
      this.put([key, val])
      return val
    } else {
      return -1
    }
  }
  put(key, val) {
    if (key && val) {
      if (this.cache.has(key)) {
        this.cache.delete(key)
      } else if (this.cache.size >= this.capacity) {
        this.cache.delete(this.cache.keys().next().value)
      }

      if (this.cache) {
        this.cache.set(key, val)
      }
    }
  }
}