JavaScript 集合 (set) 可以使用集合对象 Map、Set 和 WeakMap 存储值和对象。通过这些对象, 可以使用键或值而非索引来轻松添加和检索成员。
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
集合 (Set)
说起集合,就想起刚进高中时,数学第一课讲的就是集合。因此在学习集合这种数据结构时,倍感亲切。
集合的基本性质有一条: 集合中元素是不重复的。因为这种性质,所以我们选用了对象来作为集合的容器,而非数组。
虽然数组也能做到所有不重复,但终究过于繁琐,不如集合。
集合的操作
集合的基本操作有交集、并集、差集等。这儿我们介绍 JavaScipt 集合中交集、并集、差集的实现。
JavaScipt 中集合的实现
首先,创建一个构造函数。
- /**
- * 集合的构造函数
- */
- function Set方法 {
- /**
- * 集合元素的容器,以对象来表示
- * @type {Object}
- */
- var items = {};
- }
集合需要有如下方法:
has 方法:
说明: 集合中元素是不重复的。所以在其它任何操作前,必须用 has 方法确认集合是否有某个元素。这儿使用了 hasOwnProperty 方法来检测。
实现:
- /**
- * 检测集合内是否有某个元素
- * @param {Any} value 要检测的元素
- * @return {Boolean} 如果有,返回true
- */
- this.has = function(value) {
- // hasOwnProperty的问题在于
- // 它是一个方法,所以可能会被覆写
- return items.hasOwnProperty(value)
- };
add 方法:
说明: 给集合内添加某个元素。
实现:
- /**
- * 给集合内添加某个元素
- * @param {Any} value 要被添加的元素
- * @return {Boolean} 添加成功返回True。
- */
- this.add = function(value) {
- //先检测元素是否存在。
- if (!this.has(value)) {
- items[value] = value;
- return true;
- }
- //如果元素已存在则返回false
- return false;
- };
remove 方法:
说明: 移除集合中某个元素
实现:
- /**
- * 移除集合中某个元素
- * @param {Any} value 要移除的元素
- * @return {Boolean} 移除成功返回True。
- */
- this.remove = function(value) {
- //先检测元素是否存在。
- if (this.has(value)) {
- delete items[value];
- return true;
- }
- //如果元素不存在,则删除失败返回false
- return false;
- };
clear 方法:
说明: 清空集合
实现:
- /**
- * 清空集合
- */
- this.clear = function() {
- this.items = {};
- };
size 方法
说明: 返回集合长度,这儿有两种方法。第一种方法使用了 Object.keys 这个 Api,但只支持 IE9 及以上。第二种则适用于所有浏览器。
实现:
- /**
- * 返回集合长度,只可用于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 方法
说明: 返回集合转换的数组,这儿也有两种方法。理由同上。使用了 Object.keys,只能支持 IE9 及以上。
实现:
- /**
- * 返回集合转换的数组,只可用于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 方法
说明: 返回两个集合的并集
实现:
- /**
- * 返回两个集合的并集
- * @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 方法
说明: 返回两个集合的交集
实现:
- /**
- * 返回两个集合的交集
- * @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 方法
说明: 返回两个集合的差集
实现:
- /**
- * 返回两个集合的差集
- * @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 方法
说明: 判断该集合是否为传入集合的子集。这段代码在我自己写完后与书上一比对,觉得自己超级 low。我写的要遍历数组三次,书上的只需要一次,算法复杂度远远低于我的。
实现:
- /**
- * 判断该集合是否为传入集合的子集
- * @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;
- }
- };
ES6 中的集合
ES6 也提供了集合,但之前看 ES6 的集合操作一直迷迷糊糊的。实现一遍后再去看,感觉概念清晰了很多。
具体的我掌握的不是很好,还在学习中,就不写出来啦~ 推荐看阮一峰老师的《ECMAScript 6 入门》中对 ES6 Set 的介绍。
《ECMAScript 6 入门》– Set 和 Map 数据结构
感想
到了这儿,已经掌握了一些基本的数据结构。剩下的都是难啃的骨头了 (对我而言)。
字典的散列表、图、树、排序算法。算是四大金刚,所以近期关于数据结构与算法系列的文章,可能会更新的很慢。对我来说,也算是一个坎。希望这个寒假,能跨过这个坎。
来源: http://www.phperz.com/article/17/0221/267284.html