Set和Map主要的應(yīng)用場景在于數(shù)組去重和數(shù)據(jù)存儲渐排,幸運的是在讀了關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法之類的書籍后,恍然大悟的發(fā)現(xiàn)
原來Set是一種叫做集合的數(shù)據(jù)結(jié)構(gòu)孔祸,Map是一種叫做字典的數(shù)據(jù)結(jié)構(gòu)
集合
- 集合是由一組無序且唯一(即不能重復(fù))的項組成的隆敢,可以想象成集合是一個既沒有重復(fù)元素,也沒有順序概念的數(shù)組
- ES6提供了新的數(shù)據(jù)結(jié)構(gòu)Set崔慧。它類似于數(shù)組拂蝎,但是成員的值都是唯一的,沒有重復(fù)的值
- Set 本身是一個構(gòu)造函數(shù)惶室,用來生成 Set 數(shù)據(jù)結(jié)構(gòu)
- 這里說的Set其實就是我們所要講到的集合温自,先來看下基礎(chǔ)用法
const s = new Set();
[2, 3, 5, 4, 5, 2, 2].forEach(x => s.add(x));
for (let i of s) {
console.log(i); // 2 3 5 4
}
// 去除數(shù)組的重復(fù)成員
let array = [1,2,1,4,5,3];
[...new Set(array)] // [1, 2, 4, 5, 3]
復(fù)制代碼
具體用法如果還有不清楚的,這里我會在后面一一細說』食現(xiàn)在還是來看一下以ES6中Set類(數(shù)據(jù)結(jié)構(gòu))為基礎(chǔ)實現(xiàn)的集合吧
Set實例的屬性和方法
- Set的屬性:
- size:返回集合所包含元素的數(shù)量
- Set的方法:
- 操作方法
- add(value):向集合添加一個新的項
- delete(value):從集合中移除一個值
- has(value):如果值在集合中存在悼泌,返回true,否則false
- clear(): 移除集合里所有的項
- 遍歷方法
- keys():返回一個包含集合中所有鍵的數(shù)組
- values():返回一個包含集合中所有值的數(shù)組
- entries:返回一個包含集合中所有鍵值對的數(shù)組(感覺沒什么用就不實現(xiàn)了)
- forEach():用于對集合成員執(zhí)行某種操作,沒有返回值
- 操作方法
創(chuàng)建一個集合
function Set(arr = []) { // 可以傳入數(shù)組
let items = {};
this.size = 0; // 記錄集合中成員的數(shù)量
}
module.exports = Set;
這里用{}對象來表示集合夹界,也是因為對象不允許一個鍵指向兩個不同的屬性馆里,保證了集合里的元素都是唯一的
接下來,就需要按照ES6中Set類的實現(xiàn)可柿,添加一些集合的操作方法了
has方法
首先要實現(xiàn)的是has方法也拜,因為在add和delete等其他方法中都會被調(diào)用,下面來看一下它的實現(xiàn)
function Set() {
let items = {};
this.size = 0;
// has(val)方法
this.has = function(val) {
// 對象都有hasOwnProperty方法趾痘,判斷是否擁有特定屬性
return items.hasOwnProperty(val);
};
}
add方法
接下來要實現(xiàn)add方法
// add(val)方法
this.add = function(val) {
if (!this.has(val)) {
items[val] = val;
this.size++; // 累加集合成員數(shù)量
return true;
}
return false;
};
對于給定的val慢哈,可以檢測是否存在于集合中
- 如果不存在,就添加到集合中永票,返回true
- 如果存在卵贱,就直接返回false,不做任何操作
delete和clear方法
繼續(xù)寫著侣集,這回把兩個都寫上
// delete(val)方法
this.delete = function(val) {
if (this.has(val)) {
delete items[val]; // 將items對象上的屬性刪掉
this.size--;
return true;
}
return false;
};
// clear方法
this.clear = function() {
items = {}; // 直接將集合賦一個空對象即可
this.size = 0;
};
在delete方法中键俱,判斷val是否存在于集合中,如果存在就直接從集合中刪掉世分,返回true
以上完成的都是操作方法编振,下面我們再來實現(xiàn)一下遍歷方法
keys、values方法
這兩個方法我們可以放在一起來實現(xiàn)臭埋,因為通過ES6對Object的擴展可以輕松實現(xiàn)對應(yīng)的方法踪央,下面看一下具體實現(xiàn)臀玄,上代碼:
// keys()方法
this.keys = function() {
return Object.keys(items); // 返回遍歷集合的所有鍵名的數(shù)組
};
// values()方法
this.values = function() {
return Object.values(items); // 返回遍歷集合的所有鍵值的數(shù)組
};
使用一下看看
// set.js
const Set = require('./Set.js'); // 導(dǎo)入寫好的Set類
let set = new Set();
set.add(1);
set.add(3);
set.add(2);
console.log(set.keys()); // [ '1', '2', '3' ]
console.log(set.values()); // [ 1, 2, 3 ]
這里我們看到和ES6中的Set有點區(qū)別,因為Object的這幾個方法都是按照數(shù)值大小畅蹂,從小到大遍歷的數(shù)組健无,所以大家知道這一點比較好,具體實現(xiàn)還是有些不同的液斜,哈哈
forEach方法
ES6中Set結(jié)構(gòu)的實例上帶的forEach方法累贤,其實和數(shù)組的forEach方法很相似,只不過Set結(jié)構(gòu)的鍵名就是鍵值少漆,所以第一個參數(shù)與第二個參數(shù)的值永遠都是一樣的
下面就按照實現(xiàn)數(shù)組的forEach方法臼膏,我們來完成Set的forEach方法
// forEach(fn, context)方法
this.forEach = function(fn, context = this) {
for (let i = 0; i < this.size; i++) {
let item = Object.keys(items)[i];
fn.call(context, item, item, items);
}
};
使用forEach方法
// set.js
const Set = require('./Set.js');
let set = new Set();
set.add(1);
set.add(4);
set.add('3');
set.forEach((value, key) => console.log(key + ' : ' + value)); // 1:1, 3:3, 4:4
let arr = set.values(); // [ 1, 3, 4 ]
arr = new Set(arr.map(x => x * 2)).values();
console.log(arr); // [ 2, 6, 8 ]
基本上實現(xiàn)了Set結(jié)構(gòu)的方法,不過示损,發(fā)現(xiàn)一個問題讶请,那就是每次添加一個元素都要add這樣寫起來確實好麻煩,Set是可以接收一個數(shù)組作為參數(shù)的屎媳,那么我們把這個也實現(xiàn)一下
function Set(arr = []) { // 傳入接受的數(shù)組夺溢,如果沒有傳指定一個空數(shù)組做為初始值
let items = {};
this.size = 0;
// has方法
this.has = function (val) {
return items.hasOwnProperty(val);
};
// add方法
this.add = function (val) {
// 如果沒有存在items里面就可以直接寫入
if (!this.has(val)) {
items[val] = val;
this.size++;
return true;
}
return false;
};
arr.forEach((val, i) => { // 遍歷傳入的數(shù)組
this.add(val); // 將數(shù)組里每一項值添加到集合中
});
// 省略...
}
再來看看現(xiàn)在能不能支持傳入的數(shù)組了
// 間接使用map和filter
const Set = require('./Set.js');
let arr = new Set([1, 2, 3]).values();
m = new Set(arr.map(x => x * 2));
f = new Set(arr.filter(x => x>1));
console.log(m.values()); // [ 2, 4, 6 ]
console.log(f.values()); // [ 2, 3 ]
// 數(shù)組去重
let arr2 = new Set([3, 5, 2, 1, 2, 5, 5]).values();
console.log(arr2); // [ 1, 2, 3, 5 ]
現(xiàn)在我們有了一個和ES6中非常類似的Set類實現(xiàn)。如前所述烛谊,也可以用數(shù)組替代對象风响,存儲元素。喜歡動手的同學們丹禀,之后也可以去嘗試一下
除此之外状勤,Set還可以實現(xiàn)并集(union),交集(intersect),差集(difference)
做事還是要做全套的,我們也一一來實現(xiàn)一下吧
union并集和intersect交集
- 并集的數(shù)學概念双泪,集合A和集合B的并集持搜,表示為A∪B
- 交集的數(shù)學概念,集合A和集合B的交集焙矛,表示為A∩B
如圖所示:
現(xiàn)在先來實現(xiàn)union方法
// 并集
this.union = function (other) {
let union = new Set();
let values = this.values();
for (let i = 0; i < values.length; i++) {
union.add(values[i]);
}
values = other.values(); // 將values重新賦值為新的集合
for (let i = 0; i < values.length; i++) {
union.add(values[i]);
}
return union;
};
// 交集
this.intersect = function (other) {
let intersect = new Set();
let values = this.values();
for (let i = 0; i < values.length; i++) {
if (other.has(values[i])) { // 查看是否也存在于other中
intersect.add(values[i]); // 存在的話就像intersect中添加元素
}
}
return intersect;
};
再來看下difference差集的實現(xiàn)葫盼,之后一起再測試一番
difference差集
- 差集的數(shù)學概念,集合A和集合B的差集村斟,表示為A-B
// 差集
this.difference = function (other) {
let difference = new Set();
let values = this.values();
for (let i = 0; i < values.length; i++) {
if (!other.has(values[i])) { // 將不存在于other集合中的添加到新的集合中
difference.add(values[i]);
}
}
return difference;
};
Set完整實現(xiàn)
在此贫导,先給大家貼一下完整的實現(xiàn)代碼
function Set(arr = []) {
let items = {};
this.size = 0;
// has方法
this.has = function (val) {
return items.hasOwnProperty(val);
};
// add方法
this.add = function (val) {
// 如果沒有存在items里面就可以直接寫入
if (!this.has(val)) {
items[val] = val;
this.size++;
return true;
}
return false;
};
arr.forEach((val, i) => {
this.add(val);
});
// delete方法
this.delete = function (val) {
if (this.has(val)) {
delete items[val]; // 將items對象上的屬性刪掉
this.size--;
return true;
}
return false;
};
// clear方法
this.clear = function () {
items = {};
this.size = 0;
};
// keys方法
this.keys = function () {
return Object.keys(items);
};
// values方法
this.values = function () {
return Object.values(items);
}
// forEach方法
this.forEach = function (fn, context = this) {
for (let i = 0; i < this.size; i++) {
let item = Object.keys(items)[i];
fn.call(context, item, item, items);
}
}
// 并集
this.union = function (other) {
let union = new Set();
let values = this.values();
for (let i = 0; i < values.length; i++) {
union.add(values[i]);
}
values = other.values(); // 將values重新賦值為新的集合
for (let i = 0; i < values.length; i++) {
union.add(values[i]);
}
return union;
};
// 交集
this.intersect = function (other) {
let intersect = new Set();
let values = this.values();
for (let i = 0; i < values.length; i++) {
if (other.has(values[i])) {
intersect.add(values[i]);
}
}
return intersect;
};
// 差集
this.difference = function (other) {
let difference = new Set();
let values = this.values();
for (let i = 0; i < values.length; i++) {
if (!other.has(values[i])) {
difference.add(values[i]);
}
}
return difference;
};
// 子集
this.subset = function(other) {
if (this.size > other.size) {
return false;
} else {
let values = this.values();
for (let i = 0; i < values.length; i++) {
console.log(values[i])
console.log(other.values())
if (!other.has(values[i])) {
return false;
}
}
return true;
}
};
}
module.exports = Set;
寫了辣么多一起來測試一下吧
const Set = require('./Set.js');
let set = new Set([2, 1, 3]);
console.log(set.keys()); // [ '1', '2', '3' ]
console.log(set.values()); // [ 1, 2, 3 ]
console.log(set.size); // 3
set.delete(1);
console.log(set.values()); // [ 2, 3 ]
set.clear();
console.log(set.size); // 0
// 并集
let a = [1, 2, 3];
let b = new Set([4, 3, 2]);
let union = new Set(a).union(b).values();
console.log(union); // [ 1, 2, 3, 4 ]
// 交集
let c = new Set([4, 3, 2]);
let intersect = new Set([1,2,3]).intersect(c).values();
console.log(intersect); // [ 2, 3 ]
// 差集
let d = new Set([4, 3, 2]);
let difference = new Set([1,2,3]).difference(d).values();
// [1,2,3]和[4,3,2]的差集是1
console.log(difference); // [ 1 ]
目前為止我們用集合這種數(shù)據(jù)結(jié)構(gòu)就實現(xiàn)了類似ES6中Set類,上面的使用方法也基本一樣蟆盹,大家可以之后有時間的話動手去敲一敲看一看孩灯,走過路過不能錯過
既然我們已經(jīng)完成了Set的實現(xiàn),那么好事要成雙逾滥,一鼓作氣再把Map也一起寫出來峰档,天了擼的,開始
字典
在數(shù)據(jù)結(jié)構(gòu)還有一種結(jié)構(gòu)叫做字典,它就是實現(xiàn)基于ES6中的Map類的結(jié)構(gòu)
那么集合又和字典有什么區(qū)別呢:
共同點:集合讥巡、字典可以存儲不重復(fù)的值
不同點:集合是以[值掀亩,值]的形式存儲元素,字典是以[鍵尚卫,值]的形式存儲
所以這一下讓我們明白了,Map其實的主要用途也是用于存儲數(shù)據(jù)的尸红,相比于Object只提供“字符串—值”的對應(yīng)吱涉,Map提供了“值—值”的對應(yīng)。也就是說如果你需要“鍵值對”的數(shù)據(jù)結(jié)構(gòu)外里,Map比Object更合適
下面來看一下基本使用:
const m = new Map();
const o = {p: 'Hello World'};
m.set(o, 'content')
m.get(o) // "content"
m.has(o) // true
m.delete(o) // true
m.has(o) // false
以上是Map的基本使用怎爵,還有更多有用的方法稍后會隨著實現(xiàn)的深入分別展示
Map的屬性和方法
屬性:
- size:返回字典所包含的元素個數(shù)
操作方法:
- set(key, val): 向字典中添加新元素
- get(key):通過鍵值查找特定的數(shù)值并返回
- has(key):如果鍵存在字典中返回true,否則false
- delete(key): 通過鍵值從字典中移除對應(yīng)的數(shù)據(jù)
- clear():將這個字典中的所有元素刪除
遍歷方法:
- keys():將字典中包含的所有鍵名以數(shù)組形式返回
- values():將字典中包含的所有數(shù)值以數(shù)組形式返回
- forEach():遍歷字典的所有成員
知道了都有哪些屬性和方法,那就閑言少敘盅蝗,開始創(chuàng)建一個字典吧
創(chuàng)建一個字典
function Map() {
let items = {};
}
module.exports = Map; // 導(dǎo)出
創(chuàng)建好了字典這個骨架鳖链,那就開始添加一些方法了
has方法
首當其沖的當然是has了,因為在set和get里都會用到墩莫,實現(xiàn)思路和之前寫的集合也很類似
function Map() {
let items = {};
// has(key)方法
this.has = function(val) {
return items.hasOwnProperty(val);
};
}
實現(xiàn)了has方法后芙委,我們可以來判斷字典中是否包含該屬性了,繼續(xù)來實現(xiàn)其他方法
set和get方法
// set(key, val)方法
// set相同key時狂秦,后面聲明的會覆蓋前面
// 如: new Map().set({}, 'a')
this.set = function(key, val) {
items[key] = val;
};
// get(key)方法
this.get = function(key) {
// 判斷是否有key灌侣,如果有的話直接返回對應(yīng)的值
// 如果讀取一個未知的鍵,則返回undefined
return this.has(key) ? items[key] : undefined;
};
set和get方法寫好了裂问,再接著搞delete和clear方法侧啼,不廢話,看
delete和clear方法
// delete(key)方法
this.delete = function(key) {
if (this.has(key)) { // 如果有key值
delete items[key]; // 直接刪掉items上對應(yīng)的屬性
this.size--; // 讓size總數(shù)減1
return true;
}
return false;
};
// clear()方法
this.clear = function() {
items = {};
this.size = 0;
};
上面把屬性和操作方法都分別完成了堪簿,還剩下最后的遍歷方法了痊乾,繼續(xù)寫下去,堅持到底就是勝利椭更,各位看官也不容易了哪审,加油加油!B瞧佟协饲!
遍歷方法(keys,values,forEach)
// keys()方法
this.keys = function() {
return Object.keys(items);
};
// values()方法
this.values = function() {
return Object.values(items);
};
// forEach(fn, context)方法
this.forEach = function(fn, context = this) {
for (let i = 0; i < this.size; i++) {
let key = Object.keys(items)[i];
let value = Object.values(items)[i];
fn.call(context, value, key, items);
}
};
Now終于完成了Map類的實現(xiàn),我給大家貼一下完整代碼和測試用例缴川,供大家空閑時間來研究分析分析
Map完整實現(xiàn)
function Map() {
let items = {};
this.size = 0;
// 操作方法
// has方法
this.has = function(val) {
return items.hasOwnProperty(val);
};
// set(key, val)方法
this.set = function(key, val) {
items[key] = val;
this.size++;
};
// get(key)方法
this.get = function(key) {
return this.has(key) ? items[key] : undefined;
};
// delete(key)方法
this.delete = function(key) {
if (this.has(key)) {
delete items[key];
this.size--;
return true;
}
return false;
};
// clear()方法
this.clear = function() {
items = {};
this.size = 0;
};
// 遍歷方法
// keys()方法
this.keys = function() {
return Object.keys(items);
};
// values()方法
this.values = function() {
return Object.values(items);
};
// forEach(fn, context)方法
this.forEach = function(fn, context = this) {
for (let i = 0; i < this.size; i++) {
let key = Object.keys(items)[i];
let value = Object.values(items)[i];
fn.call(context, value, key, items);
}
};
}
module.exports = Map;
再來看看下面的測試栗子
// map.js
// 使用Map類
const Map = require('./Map.js');
let m = new Map();
m.set('Jay', 'Jay的Chou');
m.set(true, '真的');
console.log(m.has('Chou')); // false
console.log(m.size); // 2
console.log(m.keys()); // [ 'Jay', 'true' ]
console.log(m.values()); // [ 'Jay的Chou', '真的' ]
console.log(m.get('jay')); // undefined
m.delete(true);
console.log(m.keys()); // [ 'Jay' ]
console.log(m.values()); // [ 'Jay的Chou' ]