关于javascript:前端算法系列之三数据结构数据集合

在之前曾经介绍了数据结构：栈、队列、链表，并且晓得了这些数据结构的个性和实现形式，以及如何在理论的开发过程中通过这些数据结构来奇妙的解决一些理论问题，包含怎么去实现一个四则运算、怎么去实现最优取币形式等等；这篇接着介绍数据结构：汇合、字典散列；
前端算法系列之二：数据结构链表、双向链表、闭环链表、有序链表
前端算法系列之一：工夫复杂度、空间复杂度以及数据结构栈、队列的实现

一、汇合

汇合是由一组无序且惟一（即不能反复）的项组成的。该数据结构应用了与无限汇合雷同的数学概念，但利用在计算机科学的数据结构中。留神汇合的个性：1、无序；2、惟一；这和咱们数学概念的汇合大体是统一的，在数学中咱们用大括号来示意汇合，把满足条件的元素归类于放在一块造成了汇合，例如把大于等于0的整数放入汇合N = {0,1,2,3,4,5,6…}；汇合也可能是没有任何元素的，比方把没写过bug的程序猿归类在一个汇合那后果就是N = {};那怎么去实现一个汇合呢？
在es6当前JavaScript有一个原生反对汇合的Set，这个就是一个汇合，那咱们在es6以前的怎么去实现一个汇合呢？咱们能够模拟es6中Set相干来实现；
定义相干api:
add(ele):向汇合中增加一个元素；
delete(ele): 删除汇合中一个元素；
has(ele): 汇合中是否蕴含某个元素
clear(): 清空集合
size(): 计算汇合的大小
values(): 获取汇合的所有元素，返回一个数组

class MySet {
    constructor() {
     this.items = {};
    }
    add(element) {
     const key = this.keyToString(element);
     if(!this.has(element)) {
      this.items[key] = element;
     return true;
     }
     return false;
    }
    delete(element) {
     if(this.has(element)) {
      delete this.items[this.keyToString(element)];
     return true;
     }
     return false;
    }
    keyToString(str) {
     return keyToString(str);
    }
    has(element) {
     return Object.prototype.hasOwnProperty.call(this.items, this.keyToString(element));
    }
    clear() {
     this.items = {};
     return true;
    }
    size() {
     return Object.keys(this.items).length;
    }
    values() {
     return Object.values(this.items);
    }
}

注：下面代码中有一个将键转换为字符串的函数keyToString，这是为了当增加的元素是对象或者其余非凡类型时候间接作为对象的键可能会引发谬误；

function keyToString(str) {
 if (str === null) {
  return 'null';
 } else if (str === undefined) {
  return 'undefined';
 } else if(typeof str === 'function') {
  return str.toString();
 }
 return JSON.stringify(str)
}

实例测试：

const myset = new MySet();
myset.add(1); // true
myset.add(2); // true
myset.add(3); // true
myset.add({a:1}); // true
myset.add({b:1}); // true
console.log(myset.has(2)); // true
console.log(myset.has({a:1})); // true
console.log(myset.has({a:2})); // false
console.log(myset.size());// 5
console.log(myset.values());// [1, 2, 3, {a:1}, {b:1}]
myset.delete({a:1});
console.log(myset.values());// [1, 2, 3, {b:1}]
console.log(myset.has({a:1})); // false
console.log(myset.size(); // 4
myset.clear();
console.log(myset.values());// []
console.log(myset.size(); // 0

通过下面的代码实现汇合还是比拟容易了解的，就是对一个对象键值对的增删改查之类的操作，没有波及到什么简单的使用，但咱们晓得汇合的利用远远不止是这样；汇合的利用其实在于汇合间的操作，比方咱们查找数据的时候，从两个不同的表外面查出了两个汇合的数据，咱们能够通过汇合的运算来实现汇合的并集、交加、差集等操作，从而失去满足需要的数据；

1、汇合的并集

在数学概念中两个汇合A\B的并集是在元素存在于A或者存在于B中，用数学表达式表白如下：
A∪B = {x | x ∈ A ∨ x ∈ B}；

// 并集
union(otherSet) {
 const unionSet = new MySet();
 const values = this.values();
 const otherSetValues = otherSet.values();
 for (let i = 0; i < values.length; i++) {
  unionSet.add(values[i]);
 }
 for (let i = 0; i < otherSetValues.length; i++) {
  unionSet.add(otherSetValues[i]);
 }
 return unionSet;
}

测试并集：

const setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);

const setB = new MySet();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);
const unionSet = setA.union(setB);
unionSet.values(); // [1,2,3,4,5,6]

2、交加

A∩B = {x | x ∈ A ∧ x ∈ B}意思是x（元素）存在于A中，且x存在于B中。下图展现了交加运算。

// 交加
intersection(otherSet) {
 const intersectionSet = new MySet();
 const values = this.values();
 const otherSetValues = otherSet.values();
 const lenSelf = values.length;
 const lenOther = otherSetValues.length;
 if (lenSelf < lenOther) {
  for (let i = 0; i < lenSelf; i++) {
   if(otherSet.has(values[i])){
    intersectionSet.add(values[i])
   }
  }
 } else {
  for (let i = 0; i < lenOther; i++) {
   if(this.has(otherSetValues[i])){
    intersectionSet.add(otherSetValues[i])
   }
  }
 };
 return intersectionSet;
}

测试代码：

const setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new MySet();
setB.add(2);
setB.add(3);
setB.add(4);
const interse = setA.intersection(setB);
console.log(interse.values()); // [2,3]

3、差集

汇合A和汇合B的差集示意为A – B，定义如下。A-B= {x|x∈A∧x∉B}意思是x（元素）存在于A中，且x不存在于B中。下图展现了汇合A和汇合B的差集运算。

实现代码：

// 差集
difference(otherSet) {
 const differenceSet = new MySet();
 this.values().forEach(v => {
  if(!otherSet.has(v)) {
   differenceSet.add(v);
 }
 });
 return differenceSet;
}

测试代码：

const setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new MySet();
setB.add(2);
setB.add(3);
setB.add(4);
const differenceSet = setA.difference(setB);
console.log(differenceSet.values()); // [1]

4、子集

子集示意如下。
A ⊆ B该汇合定义如下。{x | ∀x ∈ A ⇒ x ∈ B}意思是汇合A中的每一个x（元素），也须要存在于汇合B中。下图展现了汇合A是汇合B的子集。

实现形式：

isChildSet(otherSet) {
 if (this.size() > otherSet.size()) {
  return false;
 }
 let res = false;
 otherSet.values().every(v => {
  if (!otherSet.has(v)) {
   res = false;
 return false
 }
  return true;
 })
 return res;
}

上面咱们来验证一下测试一下子集的验证

const setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);
const setB = new MySet();
setB.add(1);
setB.add(2);
setB.add(3);
setB.add(4);
const setChild = setA.isChildSet(setB);
console.log(setChild.values()); // true

小结

es6新增了Set类作为JavaScript API的一部分。咱们下面是实现了本人的汇合，当初来看一下es6原生的set有哪些不同；

const setA = new Set();
setA.add(1);
setA.add(2);
console.log(setA.size); // 2
setA.delete(2);// true
console.log(setA.values());//SetIterator

原生api的Set对于汇合长度有一个属性size，通过属性能够拿到汇合的长度，咱们实现的时候也能够把size办法转变成属性值的，此外原生values办法返回的不是间接的一个数组，而是一个Set迭代器SetIterator可进行迭代拜访；原生Set没有提供汇合的交加、并集、差集、子集的办法，不过也能够进行扩大实现，而且使用es6的一些新型的语法个性以及api可能比较简单的实现，这里不再赘述；

想理解更多请看：源码
或者搜寻公众号：非驰名bug认证师