数据结构与算法 - Map

优质

小牛编辑

120浏览

2023-12-01

与Set类似，ES6同样实现了一个Map类，即我们所说的字典

是一种以键-值对形式存储数据的数据结构，就如同我们平时查看通讯录一样，要找一个电话，首先先找到该号码的机主名字，名字找到了，紧接着电话号码也就有了。

这里的键就是你用来查找的东西，本例中指代的就是名字，值就是查找得到的结果，也就是对应的电话号码。

在JavaScript 中的 Object 类就是以字典的形式设计的，下面我们将会借助 Object 类的特性，自主实现一个 Dictionary 类，让这种字典类型的对象使用起来更加方便。

代码实现

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
  class Dictionary {
    constructor() {
      this.items = {}
    }

    // 检查键是否存在
    has(key) {
      // return items.hasOwnProperty(key)
      return key in this.items
    }

    set(key, value) {
      this.items[key] = value
    }

    delete(key) {
      if (this.has(key)) {
        delete this.items[key]
        return true
      }
      return false
    }

    get(key) {
      if (this.has(key)) {
        return this.items[key]
      }
      return undefined
    }

    getItems() {
      return this.items
    }
  }

  let dic = new Dictionary()
  dic.set('AAA', 13012345678)
  dic.set('BBB', 13112345678)
  dic.set('CCC', 13012345678)

  /**
   * dic
   Dictionary {items: {…}}
       items:
           AAA: 13012345678
           BBB: 13112345678
           CCC: 13012345678
   */

</script>
</body>
</html>

通过上面代码我们可以回顾，先总结下相同点：

集合元素不能重复
字典 key不能重复，但存储的值可以重复

不同点：

集合是以 [value, value] 的形式储存元素
字典是以 [key, value] 的形式储存

以下内容摘自阮一峰 ECMAScript 6 入门

JavaScript 的对象（Object），本质上是键值对的集合（Hash 结构），但是传统上只能用字符串当作键。这给它的使用带来了很大的限制。

const data = {};
const element = document.getElementById('myDiv');
data[element] = 'metadata';
data['[object HTMLDivElement]'] // "metadata"

上面代码原意是将一个 DOM 节点作为对象data的键，但是由于对象只接受字符串作为键名，所以element被自动转为字符串[object HTMLDivElement]。

为了解决这个问题，ES6 提供了 Map 数据结构。它类似于对象，也是键值对的集合，但是“键”的范围不限于字符串，各种类型的值（包括对象）都可以当作键。也就是说，Object 结构提供了“字符串—值”的对应，Map 结构提供了“值—值”的对应，是一种更完善的 Hash 结构实现。

如果你需要“键值对”的数据结构，Map 比 Object 更合适。

实例的属性和操作方法

size属性

返回 Map 结构的成员总数。

Map.prototype.set(key, value)

set方法设置键名key对应的键值为value，然后返回整个 Map 结构。如果key已经有值，则键值会被更新，否则就新生成该键。

Map.prototype.get(key)

get方法读取key对应的键值，如果找不到key，返回undefined。

Map.prototype.has(key)

has方法返回一个布尔值，表示某个键是否在当前 Map 对象之中。

Map.prototype.delete(key)

delete方法删除某个键，返回true。如果删除失败，返回false。

Map.prototype.clear()

clear方法清除所有成员，没有返回值。

遍历方法

Map 结构原生提供三个遍历器生成函数和一个遍历方法。

Map.prototype.keys()

返回键名的遍历器。

Map.prototype.values()

返回键值的遍历器。

Map.prototype.entries()

返回所有成员的遍历器。

Map.prototype.forEach()

遍历 Map 的所有成员。

示例：

const map = new Map([
  ['F', 'no'],
  ['T',  'yes'],
]);

for (let key of map.keys()) {
  console.log(key);
}
// "F"
// "T"

for (let value of map.values()) {
  console.log(value);
}
// "no"
// "yes"

for (let item of map.entries()) {
  console.log(item[0], item[1]);
}
// "F" "no"
// "T" "yes"

// 或者
for (let [key, value] of map.entries()) {
  console.log(key, value);
}
// "F" "no"
// "T" "yes"

// 等同于使用map.entries()
for (let [key, value] of map) {
  console.log(key, value);
}
// "F" "no"
// "T" "yes"

  const m = new Map()
  const o = {p: 'Hello World'}

  m.set(o, 'content') // 把o对象作业键
  m.get(o)  // "content"

  m.set('city', '上海')

  m.has(o)    // true
 // m.delete(o) // true
 // m.has(o)    // false

Map构造函数接受数组作为参数

// 传入的是一个二维数组 
const map = new Map([
    ['name', '张三'],
    ['title', 'Author']
  ]);

  map.size // 2
  map.has('name') // true
  map.get('name') // "张三"
  map.has('title') // true
  map.get('title') // "Author"

Map 构造函数接受数组作为参数，实际上执行的是下面的算法。

const items = [
  ['name', '张三'],
  ['title', 'Author']
];
const map = new Map();
items.forEach(
  ([key, value]) => map.set(key, value)
);

事实上，不仅仅是数组，任何具有 Iterator 接口、且每个成员都是一个双元素的数组的数据结构都可以当作Map构造函数的参数。这就是说，Set和Map都可以用来生成新的 Map。

const set = new Set([
  ['foo', 1],
  ['bar', 2]
]);
const m1 = new Map(set);
m1.get('foo') // 1

const m2 = new Map([['baz', 3]])
const m3 = new Map(m2)

m3.get('baz') // 3

上面代码中，我们分别使用 Set 对象和 Map 对象，当作Map构造函数的参数，结果都生成了新的 Map 对象。

key

不能重复

如果对同一个键多次赋值，后面的值将覆盖前面的值。

const map = new Map();
map
.set(1, 'aaa')
.set(1, 'bbb');
map.get(1) // "bbb"

上面代码对键1连续赋值两次，后一次的值覆盖前一次的值。

new Map().get('asfddfsasadf')
// undefined

如果读取一个未知的键，则返回undefined。

对象作为Key

const map = new Map();
map.set(['a'], 555);
map.get(['a']) // undefined

上面代码的set和get方法，表面是针对同一个键，但实际上这是 两个不同的数组实例，内存地址是不一样的，因此get方法无法读取该键，返回undefined。

同样的值的两个实例，在 Map 结构中被视为两个键。

const map = new Map();

const k1 = ['a'];
const k2 = ['a'];

map
.set(k1, 111)
.set(k2, 222);

map.get(k1) // 111
map.get(k2) // 222

上面代码中，变量k1和k2的值是一样的，但是它们在 Map 结构中被视为两个键。

由上可知，Map 的键实际上是跟内存地址绑定的，只要内存地址不一样，就视为两个键。即值可以重复，但键值不可以复重。

这就解决了同名属性碰撞（clash）的问题，我们扩展别人的库的时候，如果使用对象作为键名，就不用担心自己的属性与原作者的属性同名。

简单类型的值作为Key

如果 Map 的键是一个简单类型的值（数字、字符串、布尔值），则只要两个值严格相等，Map 将其视为一个键，比如0和-0就是一个键，布尔值true和字符串true则是两个不同的键。

另外，undefined和null也是两个不同的键。虽然NaN不严格相等于自身，但 Map 将其视为同一个键。

let map = new Map();
map.set(-0, 123);
map.get(+0) // 123

map.set(true, 1);
map.set('true', 2);
map.get(true) // 1

map.set(undefined, 3);
map.set(null, 4);
map.get(undefined) // 3

map.set(NaN, 123);
map.get(NaN) // 123

Map 结构转为数组结构

 // Map 结构转为数组结构

  const map = new Map([
    [1, 'one'],
    [2, 'two'],
    [3, 'three'],
  ])

  console.log([...map.keys()])      // [1,2,3]
  console.log([...map.values()])    // ['one', 'two', 'three']
  console.log([...map.entries()])   // [[1,'one'], [2, 'two'], [3, 'three']]
  console.log([...map])             // [[1,'one'], [2, 'two'], [3, 'three']]

详细的可以看阮一峰《ECMAScript 6 入门》 Set 和 Map 数据结构一章

语法含义

WeakMap结构与Map结构类似，也是用于生成键值对的集合。
WeakMap只接受对象作为键名（null除外），不接受其他类型的值作为键名。
WeakMap只有四个方法可用：get()、set()、has()、delete()。没有size属性，也没有遍历操作。

// WeakMap 可以使用 set 方法添加成员
const wm1 = new WeakMap();

const key = {foo: 1};
wm1.set(key, 2);
wm1.get(key) // 2

// WeakMap 也可以接受一个数组，
// 作为构造函数的参数
const k1 = [1, 2, 3];
const k2 = [4, 5, 6];
const wm2 = new WeakMap([[k1, 'foo'], [k2, 'bar']]);
wm2.get(k2) // "bar"

设计目的

weakMap的设计目的在于，有时我们想在某个对象上面存放一些数据，但是这会形成对于这个对象的引用。

const e1 = document.getElementById('foo');
const e2 = document.getElementById('bar');
const arr = [
  [e1, 'foo 元素'],
  [e2, 'bar 元素'],
];

上面代码中，e1和e2是两个对象，我们通过arr数组对这两个对象添加一些文字说明。这就形成了arr 对 e1 和 e2 的引用。

一旦不再需要这两个对象，我们就必须手动删除这个引用，否则垃圾回收机制就不会释放e1和e2占用的内存。

// 不需要 e1 和 e2 的时候
// 必须手动删除引用
arr [0] = null;
arr [1] = null;

上面这样的写法显然很不方便。一旦忘了写，就会造成内存泄露。

WeakMap 就是为了解决这个问题而诞生的，它的键名所引用的对象都是弱引用，即垃圾回收机制不将该引用考虑在内。因此，只要所引用的对象的其他引用都被清除，垃圾回收机制就会释放该对象所占用的内存。无需手动清除。

const wm = new WeakMap();
const element = document.getElementById('example');

wm.set(element, 'some information');
wm.get(element) // "some information"

上面的 DOM 节点对象的引用计数是1，而不是2。这时，一旦消除对该节点的引用，它占用的内存就会被垃圾回收机制释放。 Weakmap 保存的这个键值对，也会自动消失。

WeakMap 弱引用的只是键名，而不是键值。键值依然是正常引用。