数据结构之集合和映射

ES6 的集合和映射#

在 ES6 中新增了集合 Set 和映射 Map 的内置数据结构。

Set 类似于内置的 Array 结构，但是成员的值都是唯一的，没有重复的值。而 Map 类似于内置的 Object 结构，也是键值对的集合，但是它的 key 值不限定于字符串，其他的数据类型也可以作为 key 值。

注意，这里只专注于 ES6 的集合和映射的特性，与其他语言的集合和映射可能会有所不同。

集合#

ES6 的集合中公有四个方法has、add、delete、clear和两个属性constructor、size，另外还有四个遍历方法。

下面通过其他的数据结构来实现 ES6 的集合，四个方法都可以实现，两个属性只实现size属性，四个遍历方法暂未实现。

使用数组实现集合#

因为集合的元素是不能重复的，而在 JavaScript 中数组的元素是可以重复的，只要限制数组重复元素的特性，就能很好的实现集合。

class ArraySet {
  constructor() {
    this.array = [];
  }
 
  get size() {
    return this.array.length;
  }
 
  has(element) {
    return this.array.includes(element);
  }
 
  add(element) {
    if (!this.has(element)) {
      this.array.push(element);
    }
    return this;
  }
 
  delete(element) {
    const index = this.array.indexOf(element);
    if (index > -1) {
      this.array.splice(index, 1);
      return true;
    }
    return false;
  }
 
  clear() {
    this.array.length = 0;
  }
}

使用 Map 实现集合#

JavaScript 原生的 Map 的 key 值是唯一的值，不会重复，而且可以是任类似的值，用来实现 Set 最好不过了。

实现后的 Set 成员也是键值对，但是 key 值和 value 值的值是相同的。

class MapSet {
  constructor() {
    this.map = new Map();
  }
 
  get size() {
    return this.map.size;
  }
 
  has(element) {
    return this.map.has(element);
  }
 
  add(element) {
    if (!this.has(element)) {
      this.map.set(element, element);
    }
    return this;
  }
 
  delete(element) {
    if (this.has(element)) {
      this.map.delete(element);
      return true;
    }
    return false;
  }
 
  clear() {
    this.map.clear();
  }
}

使用链表实现集合#

需要导入链表结构LinkedList，在添加链表元素的时候，需要判断链表中节点是否存在相等的值，只有不同的值才能增加到链表中，这样就是避免链表中出现重复的值。

class LinkedListSet {
  constructor() {
    this.list = new LinkedList();
  }
 
  get size() {
    return this.list.size();
  }
 
  has(element) {
    return this.list.contains(element);
  }
 
  add(element) {
    if (!this.has(element)) {
      this.list.addFirst(element);
    }
    return this;
  }
 
  delete(element) {
    if (this.has(element)) {
      this.list.removeElement(element);
      return true;
    }
    return false;
  }
 
  clear() {
    this.list = new LinkedList();
  }
}

使用二分搜索树实现集合#

需要导入链表结构BST，因为二分搜索树的特性，节点的值都是唯一的，不会重复，这符合集合的特性，但是只能添加数字类型的元素。

另外除了二分搜索树，其它的树状结构，比如红黑树、AVL 树也是可以实现集合，这里就不做更多介绍了。

class BSTSet {
  constructor() {
    this.bst = new BST();
  }
 
  get size() {
    return this.bst.size();
  }
 
  has(element) {
    return this.bst.contains(element);
  }
 
  add(element) {
    this.bst.add(element);
    return this;
  }
 
  delete(element) {
    if (this.has(element)) {
      this.bst.remove(element);
      return true;
    }
    return false;
  }
 
  clear() {
    this.bst = new BST();
  }
}

代码测试#

简单测试下上面实现的代码

// const set = new ArraySet()
// const set = new MapSet()
// const set = new LinkedListSet()
const set = new BSTSet();
 
set.add(1);
set.add(3);
 
console.log(set.has(1)); // true
console.log(set.has(2)); // false
console.log(set.size); // 2
 
console.log(set.delete(2)); // false
console.log(set.delete(1)); // true
console.log(set.size); // 1
 
set.clear();
console.log(set.size); // 0

映射#

ES6 的映射中公有五个方法has、get、set、delete、clear和一个属性size，另外还有四个遍历方法。

下面通过其他的数据结构来实现 ES6 的集合，五个方法都可以实现和一个属性size都可以实现，四个遍历方法暂未实现。实现映射只是为了更好的理解映射的结构，在实际应用中还是建议使用 ES6 原生的映射，原生性能更好。

使用链表实现映射#

链表可以非常好的实现映射，链表中的节点增加一个属性，和原来的属性组成一组键值对。key 值和原生的映射一样，可以使用各种类型的数据。

class Node {
  constructor(key = null, value = null, next = null) {
    this.key = key;
    this.value = value;
    this.next = next;
  }
}
 
class LinkedListMap {
  constructor() {
    this.dummyHead = new Node();
    this.count = 0;
  }
 
  get size() {
    return this.count;
  }
 
  // 通过 key 获取对应的节点
  _getNode(key) {
    let cur = this.dummyHead.next;
 
    while (cur != null) {
      if (cur.key === key) {
        return cur;
      }
      cur = cur.next;
    }
 
    return null;
  }
 
  has(key) {
    return this._getNode(key) != null;
  }
 
  get(key) {
    const node = this._getNode(key);
    return node == null ? undefined : node.value;
  }
 
  set(key, value) {
    const node = this._getNode(key);
 
    if (node == null) {
      this.dummyHead.next = new Node(key, value, this.dummyHead.next); // 头部位置增加
      this.count++;
    } else {
      node.value = value;
    }
  }
 
  delete(key) {
    let prev = this.dummyHead;
 
    while (prev.next != null) {
      if (prev.next.key === key) {
        break;
      }
      prev = prev.next;
    }
 
    if (prev.next != null) {
      const delNode = prev.next;
      prev.next = delNode.next;
      delNode.next = null;
      this.count--;
      return true;
    }
 
    return false;
  }
 
  clear() {
    this.dummyHead.next = null;
    this.size = 0;
  }
}

使用二分搜索树实现映射#

使用二分搜索树实现映射的节点不在是单独的一个值，而是增加了一个属性，和原来的值一起变成一组键值对。其它的就和二分搜索树一样了，都有左右孩子。

另外受限于二分搜索树的特性，使用 key 值作为节点的值进行比较，所以 key 值是唯一的，而且它的类型必需是数字类型，这样限制比较大。而 value 值可以是重复的，也可以是其它的类型。

另外除了二分搜索树，其它的树状结构，比如红黑树、AVL 树也是可以实现映射，这里就不做更多介绍了。

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
 
class BSTMap {
  constructor() {
    this.root = null;
    this.count = 0;
  }
 
  get size() {
    return this.count;
  }
 
  set(key, value) {
    this.root = this._set(this.root, key, value);
  }
 
  _set(node, key, value) {
    if (node == null) {
      this.count++;
      return new Node(key, value);
    }
 
    if (key < node.key) {
      node.left = this._set(node.left, key, value);
    } else if (key > node.key) {
      node.right = this._set(node.right, key, value);
    } else {
      node.value = value;
    }
 
    return node;
  }
 
  _getNode(node, key) {
    if (node == null) {
      return null;
    }
 
    if (key === node.key) {
      return node;
    } else if (key < node.key) {
      return this._getNode(node.left, key);
    } else {
      return this._getNode(node.right, key);
    }
  }
 
  has(key) {
    return this._getNode(this.root, key) != null;
  }
 
  get(key) {
    const node = this._getNode(this.root, key);
    return node == null ? undefined : node.value;
  }
 
  _minimum(node) {
    if (node.left == null) {
      return node;
    }
 
    return this._minimum(node.left);
  }
 
  _deleteMin(node) {
    if (node.left == null) {
      const rightNode = node.right;
      node.right = null;
      this.count--;
      return rightNode;
    }
 
    node.left = this._deleteMin(node.left);
    return node;
  }
 
  delete(key) {
    const node = this._getNode(this.root, key);
 
    if (node != null) {
      this.root = this._delete(this.root, key);
      return true;
    }
 
    return false;
  }
 
  _delete(node, key) {
    if (node == null) {
      return null;
    }
 
    if (key < node.key) {
      node.left = this._delete(node.left, key);
      return node;
    } else if (key > node.key) {
      node.right = this._delete(node.right, key);
      return node;
    } else {
      if (node.left == null) {
        const rightNode = node.right;
        node.right = null;
        this.count--;
        return rightNode;
      }
 
      if (node.right == null) {
        const leftNode = node.left;
        node.left = null;
        this.count--;
        return leftNode;
      }
 
      const successor = this._minimum(node.right);
      successor.right = this._deleteMin(node.right);
      successor.left = node.left;
 
      node.left = node.right = null;
      return successor;
    }
  }
 
  clear() {
    this.root = null;
    this.size = 0;
  }
}

代码测试#

简单测试下上面实现的代码

// const map = new LinkedListMap()
const map = new BSTMap();
 
map.set(1, "abc");
// map.set('1', 456) // 测试链表结构
map.set(3, 456); // 测试二分搜索树结构
 
console.log(map.size); // 2
 
console.log(map.has(1)); // true
console.log(map.has(2)); // false
 
console.log(map.get(1)); // abc
console.log(map.get(2)); // undefined
 
console.log(map.delete(2)); // false
console.log(map.delete(1)); // true
console.log(map.size); // 1
 
map.clear();
console.log(map.size); // 0

WeakSet 和 WeakMap#

在 ES6 中还新增了 WeakSet 和 WeakMap 这两种特殊的类型结构。

WeakSet#

WeakSet 结构与 Set 类似，也是不重复的值的集合，但是它与 Set 有两个区别：

WeakSet 的集合成员必须是对象类型object，不能是其他的类型
WeakSet 中的对象是弱引用。在 JavaScript 的垃圾回收采用的方法就是标记清除的方法，从全局对象出发，找所有从这个全局对象开始引用的对象进行标记，然后再去找这些对象引用的对象。在 JavaScript 中对象是引用类型的，如果对象被引用是不会被回收的。但是 WeakSet 中的对象是弱引用，它引用的对象如果没有其他的引用，引用的对象就不会被标记，就会被垃圾回收机制清除，也就是说 WeakSet 中的对象不记录到引用的标记中。

因为 WeakSet 的对象是弱引用，很容易被清除，自然就不需要clear方法，WeakSet 只有has、add、delete这三个方法，另外也没有属性，没有遍历方法。

WeakSet 合适临时存放一组对象，以及存放跟对象绑定的信息。这些对象在外部消失后，它在 WeakSet 里面的引用也会跟着自动消失，不需要手动去清理，可以有效防止内存泄漏。不过这样的例子很难演示，因为垃圾回收机制的运行是不可预测的，清除未标记对象的时间就不好把控，无法确定引用何时消失。

const set = new WeakSet();
class Foo {
  constructor() {
    set.add(this);
  }
  method() {
    if (!set.has(this)) {
      throw new TypeError("Foo.prototype.method 只能在Foo的实例上调用！");
    }
  }
}

实例化 Foo 的时候，会把实例加入到 set 中，如果你使用实例后又把实例删除掉，这时候，set 里面的实例已经没有其他引用，会被垃圾机制回收掉。

WeakMap#

WeakMap 结构与 Map 类似，也是键值对的集合，但是它与 Map 也有两个区别：

WeakMap 只接受对象作为键（key）名（null 除外），不接受其他的类型
WeakMap 键名的对象也是弱引用，不记录到垃圾回收机制的引用标记中，容易被回收。

WeakMap 也没有clear方法，只有has、get、set、delete这四个方法，没有size属性和遍历方法。

WeakMap 的应用场景和 WeakSet 类似。当外面的对象被删除后，WeakMap 里面的键名也会自动消失，不需要手动去清理，可以有效防止内存泄漏。

WeakMap 其中的一个应用场景就是 DOM 节点作为键名。一旦这个 DOM 节点删除，WeakMap 里面的键名就会被清除掉，键名对应的值也会跟着消失，不会造成内存泄漏。

let myElement = document.getElementById("logo");
let myWeakMap = new WeakMap();
 
myWeakMap.set(myElement, { timesClicked: 0 });
 
myElement.addEventListener(
  "click",
  function () {
    let logoData = myWeakMap.get(myElement);
    logoData.timesClicked++;
  },
  false
);

WeakMap 的另一个用处是部署私有属性。

const _counter = new WeakMap();
const _action = new WeakMap();
 
class Countdown {
  constructor(counter, action) {
    _counter.set(this, counter);
    _action.set(this, action);
  }
  dec() {
    let counter = _counter.get(this);
    if (counter < 1) return;
    counter--;
    _counter.set(this, counter);
    if (counter === 0) {
      _action.get(this)();
    }
  }
}
 
const c = new Countdown(2, () => console.log("DONE"));
 
c.dec();
c.dec();
// DONE

上面代码中，Countdown 类的两个内部属性_counter和_action，是实例的弱引用，所以如果删除实例，它们也就随之消失，不会造成内存泄漏。

注意，本节 WeakSet 和 WeakMap 的用法和示例都引用了阮一峰老师的电子书 ECMAScript6 入门的内容。

总结#

ES6 的 Set 和 Map 极大的扩展了 JavaScript 数据结构类型，使得 JavaScript 语言更加完善，更像一门现代化的语言。