Collection of JavaScript data structures and algorithms (Set)_Basic knowledge

Set

Speaking of sets, I remember that when I first entered high school, the first mathematics lesson was about sets. Therefore, it feels more intimate when learning the data structure of collections.
There is one basic property of sets: the elements in the set are not repeated. Because of this property, we chose objects as collection containers instead of arrays.
Although arrays can also achieve all non-repetitions, they are ultimately too cumbersome and not as good as collections.

Collection operations

The basic operations of sets include intersection, union, difference, etc. Here we introduce the implementation of intersection, union, and difference in JavaScipt collections.

Implementation of collections in JavaScipt

First, create a constructor.

/**
 * 集合的构造函数
 */
function Set方法 {
 /**
  * 集合元素的容器，以对象来表示
  * @type {Object}
  */
 var items = {};
}

The collection needs to have the following methods:

1. has(value): Check whether there is an element in the set
2. add(value): Add an element to the collection
3. remove(value): Remove an element from the collection
4. clear(value): Clear the collection
5. size(): Returns the length of the collection
6. values(): Returns the array converted from the set
7. union(otherSet): Returns the union of two sets
8. intersection(otherSet): Returns the intersection of two sets
9. difference(otherSet): Returns the difference between two sets
10. subset(otherSet): Determine whether the set is a subset of the incoming set

has method:

Note: The elements in the set are not repeated. Therefore, before any other operations, you must use the has method to confirm whether the collection has a certain element. The hasOwnProperty method is used here to detect.
Implementation:

/**
 * 检测集合内是否有某个元素
 * @param {Any} value  要检测的元素
 * @return {Boolean}    如果有，返回true
 */
this.has = function(value) {
 // hasOwnProperty的问题在于
 // 它是一个方法，所以可能会被覆写
 return items.hasOwnProperty(value)
};

add method:

Description: Add an element to the collection.
Implementation:

/**
 * 给集合内添加某个元素
 * @param {Any} value 要被添加的元素
 * @return {Boolean}    添加成功返回True。
 */
this.add = function(value) {
 //先检测元素是否存在。
 if (!this.has(value)) {
  items[value] = value;
  return true;
 }
 //如果元素已存在则返回false
 return false;
};

remove method:

Description: Remove an element from the collection
Implementation:

/**
 * 移除集合中某个元素
 * @param {Any} value 要移除的元素
 * @return {Boolean}    移除成功返回True。
 */
this.remove = function(value) {
 //先检测元素是否存在。
 if (this.has(value)) {
  delete items[value];
  return true;
 }
 //如果元素不存在，则删除失败返回false
 return false;
};

clear method:
Description: Clear the collection
Implementation:

/**
 * 清空集合
 */
this.clear = function() {
 this.items = {};
};

size method

Description: Return the length of the collection. There are two methods here. The first method uses the Object.keys API, but only supports IE9 and above. The second one works in all browsers.
Implementation:

/**
 * 返回集合长度，只可用于IE9及以上
 * @return {Number} 集合长度
 */
this.size = function() {
 // Object.keys方法能将对象转化为数组
 // 只可用于IE9及以上，但很方便
 return Object.keys(items).length;
}

/**
 * 返回集合长度，可用于所有浏览器
 * @return {Number} 集合长度
 */
this.sizeLegacy = function() {
 var count = 0;
 for (var prop in items) {
  if (items.hasOwnProperty(prop)) {
   ++count;
  }
 }
 return count;
}

values ​​method

Description: Returns the array of set conversion. There are two methods here. The reason is the same as above. Object.keys is used and can only support IE9 and above.
Implementation:

/**
 * 返回集合转换的数组，只可用于IE9及以上
 * @return {Array} 转换后的数组
 */
this.values = function() {
 return Object.keys(items);
};

/**
 * 返回集合转换的数组，可用于所有浏览器
 * @return {Array} 转换后的数组
 */
this.valuesLegacy = function() {
 var keys = [];
 for (var key in items) {
  keys.push(key)
 };
 return keys;
};

union method

Description: Returns the union of two sets
Implementation:

/**
 * 返回两个集合的并集
 * @param {Set} otherSet 要进行并集操作的集合
 * @return {Set}     两个集合的并集
 */
this.union = function(otherSet) {
 //初始化一个新集合，用于表示并集。
 var unionSet = new Set();
 //将当前集合转换为数组，并依次添加进unionSet
 var values = this.values();
 for (var i = 0; i < values.length; i++) {
  unionSet.add(values[i]);
 }

 //将其它集合转换为数组，依次添加进unionSet。
 //循环中的add方法保证了不会有重复元素的出现
 values = otherSet.values();
 for (var i = 0; i < values.length; i++) {
  unionSet.add(values[i]);
 }

 return unionSet;
};

intersection method

Description: Returns the intersection of two sets
Implementation:

/**
 * 返回两个集合的交集
 * @param {Set} otherSet 要进行交集操作的集合
 * @return {Set}     两个集合的交集
 */
this.intersection = function(otherSet) {
 //初始化一个新集合，用于表示交集。
 var interSectionSet = new Set();
 //将当前集合转换为数组
 var values = this.values();
 //遍历数组，如果另外一个集合也有该元素，则interSectionSet加入该元素。
 for (var i = 0; i < values.length; i++) {

  if (otherSet.has(values[i])) {
   interSectionSet.add(values[i])
  }
 }

 return interSectionSet;
};

difference method

Description: Returns the difference between two sets
Implementation:

/**
 * 返回两个集合的差集
 * @param {Set} otherSet 要进行差集操作的集合
 * @return {Set}     两个集合的差集
 */
this.difference = function(otherSet) {
 //初始化一个新集合，用于表示差集。
 var differenceSet = new Set();
 //将当前集合转换为数组
 var values = this.values();
 //遍历数组，如果另外一个集合没有该元素，则differenceSet加入该元素。
 for (var i = 0; i < values.length; i++) {

  if (!otherSet.has(values[i])) {
   differenceSet.add(values[i])
  }
 }

 return differenceSet;
};

subset method

Description: Determine whether the set is a subset of the incoming set. After I finished writing this code, I compared it with the one in the book and felt that it was super low. The one I wrote requires traversing the array three times, while the one in the book only needs one, and the algorithm complexity is far lower than mine.
Implementation:

/**
 * 判断该集合是否为传入集合的子集
 * @param {Set} otherSet 传入的集合
 * @return {Boolean}   是则返回True
 */
this.subset = function(otherSet) {
 // 第一个判定,如果该集合长度大于otherSet的长度
 // 则直接返回false
 if (this.size() > otherSet.size()) {
  return false;
 } else {
  // 将当前集合转换为数组
  var values = this.values();

  for (var i = 0; i < values.length; i++) {

   if (!otherSet.has(values[i])) {
    // 第二个判定。只要有一个元素不在otherSet中
    // 那么则可以直接判定不是子集，返回false
    return false;
   }
  }

  return true;
 }
};

Collections in ES6

ES6 also provides collections, but I have always been confused by the collection operations of ES6 before. After I implemented it and looked at it again, I felt that the concept was much clearer.
I don’t have a good grasp of the specifics. I’m still learning, so I won’t write it down. I recommend reading the introduction to ES6 Set in Teacher Ruan Yifeng’s "Introduction to ECMAScript 6".
"Introduction to ECMAScript 6" – Set and Map data structures

Impressions

At this point, you have mastered some basic data structures. The rest is a tough nut to crack (for me).

Dictionary hash tables, graphs, trees, and sorting algorithms. It is considered the Four King Kongs, so the recent series of articles on data structures and algorithms may be updated very slowly. For me, it is also a hurdle. I hope I can overcome this hurdle this winter vacation.