Set令哟、Map數(shù)據(jù)結(jié)構(gòu)

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

如圖所示:


image.png

現(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
image.png
    // 差集
    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' ]

鏈接:https://juejin.im/post/6844903589920374792

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末茉稠,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子把夸,更是在濱河造成了極大的恐慌而线,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,376評論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異膀篮,居然都是意外死亡嘹狞,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,126評論 2 385
  • 文/潘曉璐 我一進店門誓竿,熙熙樓的掌柜王于貴愁眉苦臉地迎上來磅网,“玉大人,你說我怎么就攤上這事筷屡〗担” “怎么了?”我有些...
    開封第一講書人閱讀 156,966評論 0 347
  • 文/不壞的土叔 我叫張陵毙死,是天一觀的道長燎潮。 經(jīng)常有香客問我,道長扼倘,這世上最難降的妖魔是什么确封? 我笑而不...
    開封第一講書人閱讀 56,432評論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮再菊,結(jié)果婚禮上爪喘,老公的妹妹穿的比我還像新娘。我一直安慰自己纠拔,他們只是感情好腥放,可當我...
    茶點故事閱讀 65,519評論 6 385
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著绿语,像睡著了一般秃症。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上吕粹,一...
    開封第一講書人閱讀 49,792評論 1 290
  • 那天种柑,我揣著相機與錄音,去河邊找鬼匹耕。 笑死聚请,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的稳其。 我是一名探鬼主播驶赏,決...
    沈念sama閱讀 38,933評論 3 406
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼既鞠!你這毒婦竟也來了煤傍?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,701評論 0 266
  • 序言:老撾萬榮一對情侶失蹤嘱蛋,失蹤者是張志新(化名)和其女友劉穎蚯姆,沒想到半個月后五续,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,143評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡龄恋,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,488評論 2 327
  • 正文 我和宋清朗相戀三年疙驾,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片郭毕。...
    茶點故事閱讀 38,626評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡它碎,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出显押,到底是詐尸還是另有隱情扳肛,我是刑警寧澤,帶...
    沈念sama閱讀 34,292評論 4 329
  • 正文 年R本政府宣布煮落,位于F島的核電站敞峭,受9級特大地震影響踊谋,放射性物質(zhì)發(fā)生泄漏蝉仇。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,896評論 3 313
  • 文/蒙蒙 一殖蚕、第九天 我趴在偏房一處隱蔽的房頂上張望轿衔。 院中可真熱鬧,春花似錦睦疫、人聲如沸害驹。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,742評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽宛官。三九已至,卻和暖如春瓦糕,著一層夾襖步出監(jiān)牢的瞬間底洗,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,977評論 1 265
  • 我被黑心中介騙來泰國打工咕娄, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留亥揖,地道東北人。 一個月前我還...
    沈念sama閱讀 46,324評論 2 360
  • 正文 我出身青樓圣勒,卻偏偏與公主長得像费变,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子圣贸,可洞房花燭夜當晚...
    茶點故事閱讀 43,494評論 2 348