周星星

Appearance

手动实现Map、Set数据结构 ​

轻松教你实现Map、Set数据结构的对象

Map ​

Map是一个JavaScript的对象，本质上是键值对结构（Hash结构），任何值(对象或者原始值) 都可以作为一个键或一个值。

Map与Object的区别 ​

  1. Map的键是可以为任意值，而Object的键是字符串的
  2. Map中有size属性可以计算长度，而Object只能通过手动计算
  3. Map继承自Object，是Object的实例之一
  4. Map支持数组作为构造函数的参数,但必须是二维数组

Map对象的属性 ​

  1. size:返回Map对象中键值对长度
js
const map = new Map([["name","青年野味"],["age","18"]])

map.size //2
const map = new Map([["name","青年野味"],["age","18"]])

map.size //2

Map对象的方法 ​

  1. has(Key)：返回的是Map对象的Key是否存在这个值，有就返回true，否则false
  2. get(Key): 返回的是Map对象Key所对应的Value值，有就返回Value值，否则undefined
  3. set(Key,Value): 用于向Map对象中添加新的元素，如果已经存在则会覆盖原来的
  4. delete(Key): 用于删除Map对象中Key所对应的元素
  5. clear():用于删除Map对象中的所有元素
js
 const map = new Map([["name","青年野味"],["age","18"]])
 
 map.has("name") //true
 map.get("name") //青年野味
 map.set("education","本科")//{'name' => '青年野味', 'age' => '18', 'education' => '本科'}
 map.delete("education") //{'name' => '青年野味', 'age' => '18'}
 map.clear() //undefined
 const map = new Map([["name","青年野味"],["age","18"]])
 
 map.has("name") //true
 map.get("name") //青年野味
 map.set("education","本科")//{'name' => '青年野味', 'age' => '18', 'education' => '本科'}
 map.delete("education") //{'name' => '青年野味', 'age' => '18'}
 map.clear() //undefined

Map对象的遍历方法 ​

  1. entries(): 返回Map对象中的每个元素的键与值
  2. forEach(): 使用回调函数来返回Map对象中的每个元素的键与值，和整个Map对象
  3. keys(): 返回Map对象中的每个元素的Key
  4. values(): 返回Map对象中的每个元素的Value
js
const map = new Map([["name","青年野味"],["age","18"]])
for(let i of  map.entries()){
    console.log(i)
}
//['name', '青年野味']
//['age', '18']

//利用解构的方式
for(let [key,value] of  map.entries()){
    console.log(key,value)
}
//name ，青年野味
//age, 18

map.forEach((Value,Key,array)=>{
    console.log(Value,Key,array)
})
//青年野味 name {'name' => '青年野味', 'age' => '18'}
//18 age {'name' => '青年野味', 'age' => '18'}

for(let i of  map.keys()){
    console.log(i)
}
//name
//age

for(let i of  map.values()){
    console.log(i)
}
//青年野味
//18

//for...of...也可以直接遍历Map对象（跟使用`map.entries()`相同）
for (let [key, value] of map) { 
     console.log(key, value) 
}
//name ，青年野味
//age, 18
const map = new Map([["name","青年野味"],["age","18"]])
for(let i of  map.entries()){
    console.log(i)
}
//['name', '青年野味']
//['age', '18']

//利用解构的方式
for(let [key,value] of  map.entries()){
    console.log(key,value)
}
//name ，青年野味
//age, 18

map.forEach((Value,Key,array)=>{
    console.log(Value,Key,array)
})
//青年野味 name {'name' => '青年野味', 'age' => '18'}
//18 age {'name' => '青年野味', 'age' => '18'}

for(let i of  map.keys()){
    console.log(i)
}
//name
//age

for(let i of  map.values()){
    console.log(i)
}
//青年野味
//18

//for...of...也可以直接遍历Map对象（跟使用`map.entries()`相同）
for (let [key, value] of map) { 
     console.log(key, value) 
}
//name ，青年野味
//age, 18

好了，现在我们就使用完Map对象的相关属性和方法了，现在让我们一起去实现它吧

Map方法手动实现 ​

js
        class yw_Map {
            //首先默认yw_arguments初始化的是空数组
            constructor(yw_arguments = []) {
                // console.log("青年野味来实现Map原理了", yw_arguments)
                //首先需要确定传进来的数组是否可以遍历
                //es6规定，一个数据结构只要具有Symbol.iterator属性，就认为是可以遍历的，for...of循环时会调用这个方法
                if (typeof yw_arguments[Symbol.iterator] !== "function") {
                    throw new TypeError(`${yw_arguments}不是一个可遍历的值`)
                }
                //声明一个新的数组，用来保存数据结构，包含着键与值
                this.newArr = []
                //因为Map中的数组是个二维数组，不管一个数组里边的数据多少个，默认取第一个为Key，第二个为Value
                //同样我们这里需要再次遍历，查看里边的数组是否可遍历
                for (let item of yw_arguments) {
                    if (typeof item[Symbol.iterator] !== "function") {
                        throw new TypeError(`${item}不是一个可遍历的值`)
                    }
                    //通过Symbol.iterator获取到我们所需要的前面两个值
                    const iter = item[Symbol.iterator]()
                    const key = iter.next().value
                    const value = iter.next().value

                    this.set(key, value)
                }
            }
            
            //这个还需要去看一下es6对[Symbol.iterator]的解释
            *[Symbol.iterator]() {
                let i = 0;
                while (this.newArr[i] !== undefined) {
                    yield [this.newArr[i].key, this.newArr[i].value];;
                    ++i;
                }
            }
            
            //size属性
            get size() {
                return this.newArr.length
            }

            //查找在Map对象中是否含有对应元素
            findMap(key) {
                for (let i of this.newArr) {
                    if (this.matching(i["key"], key)) {
                        return i
                    }
                }
            }
            
            //判断数据
            matching(data1, data2) {
                //考虑0和-0、NaN
                if (data1 === 0 && data2 === 0) {
                    return true
                }
                //ES6新增的用来比较两个值是否严格相等的方法，与===的行为基本一致
                return Object.is(data1, data2)
            }
            
            //set方法
            set(key, value) {
                const obj = this.findMap(key)
                if (obj) {
                    obj.value = value
                } else {
                    this.newArr.push({
                        key,
                        value,
                    })
                }
                return this
            }
            
            //get方法
            get(key) {
                const obj = this.findMap(key)
                if (obj) {
                    return obj.value
                } else {
                    return undefined
                }
            }
            
            //delete删除方法
            delete(key) {
                for (let i = 0; i < this.newArr.length; i++) {
                    const ele = this.newArr[i]
                    if (this.matching(ele.key, key)) {
                        this.newArr.splice(i, 1)
                        return true
                    }
                }
            }
            
            //clear方法
            clear() {
                this.newArr.splice(0, this.newArr.length)
            }
            
            //has方法
            has(key) {
                return this.findMap(key) !== undefined
            }
            
           //entries遍历方法
            entries() {
                var list = []
                for (let i of this.newArr) {

                    list.push([i["key"], i["value"]])
                }
                return list
            }
            
            //forEach遍历方法
            forEach(callback) {
                for (let i of this.newArr) {
                    return callback(i["value"], i["key"], this)
                }

            }
            
            //获取所有的keys集合
            keys() {
                var list = []
                for (let i of this.newArr) {
                    list.push(i["key"])
                }
                return list
            }
            
            //获取所有的values集合
            values() {
                var list = []
                for (let i of this.newArr) {
                    list.push(i["value"])
                }
                return list
            }
        }
        class yw_Map {
            //首先默认yw_arguments初始化的是空数组
            constructor(yw_arguments = []) {
                // console.log("青年野味来实现Map原理了", yw_arguments)
                //首先需要确定传进来的数组是否可以遍历
                //es6规定，一个数据结构只要具有Symbol.iterator属性，就认为是可以遍历的，for...of循环时会调用这个方法
                if (typeof yw_arguments[Symbol.iterator] !== "function") {
                    throw new TypeError(`${yw_arguments}不是一个可遍历的值`)
                }
                //声明一个新的数组，用来保存数据结构，包含着键与值
                this.newArr = []
                //因为Map中的数组是个二维数组，不管一个数组里边的数据多少个，默认取第一个为Key，第二个为Value
                //同样我们这里需要再次遍历，查看里边的数组是否可遍历
                for (let item of yw_arguments) {
                    if (typeof item[Symbol.iterator] !== "function") {
                        throw new TypeError(`${item}不是一个可遍历的值`)
                    }
                    //通过Symbol.iterator获取到我们所需要的前面两个值
                    const iter = item[Symbol.iterator]()
                    const key = iter.next().value
                    const value = iter.next().value

                    this.set(key, value)
                }
            }
            
            //这个还需要去看一下es6对[Symbol.iterator]的解释
            *[Symbol.iterator]() {
                let i = 0;
                while (this.newArr[i] !== undefined) {
                    yield [this.newArr[i].key, this.newArr[i].value];;
                    ++i;
                }
            }
            
            //size属性
            get size() {
                return this.newArr.length
            }

            //查找在Map对象中是否含有对应元素
            findMap(key) {
                for (let i of this.newArr) {
                    if (this.matching(i["key"], key)) {
                        return i
                    }
                }
            }
            
            //判断数据
            matching(data1, data2) {
                //考虑0和-0、NaN
                if (data1 === 0 && data2 === 0) {
                    return true
                }
                //ES6新增的用来比较两个值是否严格相等的方法，与===的行为基本一致
                return Object.is(data1, data2)
            }
            
            //set方法
            set(key, value) {
                const obj = this.findMap(key)
                if (obj) {
                    obj.value = value
                } else {
                    this.newArr.push({
                        key,
                        value,
                    })
                }
                return this
            }
            
            //get方法
            get(key) {
                const obj = this.findMap(key)
                if (obj) {
                    return obj.value
                } else {
                    return undefined
                }
            }
            
            //delete删除方法
            delete(key) {
                for (let i = 0; i < this.newArr.length; i++) {
                    const ele = this.newArr[i]
                    if (this.matching(ele.key, key)) {
                        this.newArr.splice(i, 1)
                        return true
                    }
                }
            }
            
            //clear方法
            clear() {
                this.newArr.splice(0, this.newArr.length)
            }
            
            //has方法
            has(key) {
                return this.findMap(key) !== undefined
            }
            
           //entries遍历方法
            entries() {
                var list = []
                for (let i of this.newArr) {

                    list.push([i["key"], i["value"]])
                }
                return list
            }
            
            //forEach遍历方法
            forEach(callback) {
                for (let i of this.newArr) {
                    return callback(i["value"], i["key"], this)
                }

            }
            
            //获取所有的keys集合
            keys() {
                var list = []
                for (let i of this.newArr) {
                    list.push(i["key"])
                }
                return list
            }
            
            //获取所有的values集合
            values() {
                var list = []
                for (let i of this.newArr) {
                    list.push(i["value"])
                }
                return list
            }
        }

我们来实验一下吧

js
        let map = new yw_Map([
            ["name", "青年野味"],
        ])
        
        console.log(map) //{"name" => "青年野味"}
        console.log(map.size) //1
        console.log(map.get("name")) //青年野味
        console.log(map.get("age")) //undefined
        console.log(map.set("age", 18)) //{'name' => '青年野味', 'age' => 18}
        console.log(map.has("age")) //true
        console.log(map.has("education")) //false
        console.log(map.delete("age")) //{"name" => "青年野味"}
        console.log(map.clear()) //undefined
        console.log("自己写的清除后的Map对象",map) //{size: 0}
        
        //遍历方法的效果也是一样的，大家可以自己尝试一下
        let map = new yw_Map([
            ["name", "青年野味"],
        ])
        
        console.log(map) //{"name" => "青年野味"}
        console.log(map.size) //1
        console.log(map.get("name")) //青年野味
        console.log(map.get("age")) //undefined
        console.log(map.set("age", 18)) //{'name' => '青年野味', 'age' => 18}
        console.log(map.has("age")) //true
        console.log(map.has("education")) //false
        console.log(map.delete("age")) //{"name" => "青年野味"}
        console.log(map.clear()) //undefined
        console.log("自己写的清除后的Map对象",map) //{size: 0}
        
        //遍历方法的效果也是一样的，大家可以自己尝试一下

注意：如果Map的键是一个简单类型的值（数字、字符串、布尔值），则只要两个值严格相等，Map将其视为一个键，包括0和-0。另外，虽然NaN不严格相等于自身，但Map将其视为同一个键。

Set ​

Set对象允许你存储任何类型的值，无论是原始值或者是对象引用。它类似于数组，但是成员的值都是唯一的，没有重复的值。

Set 本身是一个构造函数，用来生成Set 数据结构。Set函数可以接受一个数组（或者具有 iterable 接口的其他数据结构）作为参数，用来初始化。

Set中的特殊值 ​

Set 对象存储的值总是唯一的，所以需要判断两个值是否恒等。有几个特殊值需要特殊对待：

  1. +0 与 -0 在存储判断唯一性的时候是恒等的，所以不重复
  2. undefined 与 undefined 是恒等的，所以不重复
  3. NaN 与 NaN 是不恒等的，但是在 Set 中认为NaN与NaN相等，所有只能存在一个，不重复。
  4. 在 Set中两个对象总是不相等的。
js
let set = new Set();

set.add({}) 
set.size // 1 

set.add({}) 
set.size // 2
let set = new Set();

set.add({}) 
set.size // 1 

set.add({}) 
set.size // 2

Set实例对象的属性 ​

  1. size：返回Set实例的成员总数。

Set实例对象的方法 ​

  1. add(value)：添加某个值，返回 Set 结构本身(可以链式调用)。
  2. delete(value)：删除某个值，删除成功返回true，否则返回false。
  3. has(value)：返回一个布尔值，表示该值是否为Set的成员。
  4. clear()：清除所有成员，没有返回值。
const ywSet = new Set(['18', '18', '19', 19, 20, 21])

console.log(ywSet)  // {'18', '19', 19, 20,21}
ywset.add('17').add({'name': '青年野味'})

console.log(ywSet) // {'18', '19', 19, 20,21,'17',{'name': '青年野味'}}
console.log(ywSet.size) // 7

mySet.has(20) // true
const ywSet = new Set(['18', '18', '19', 19, 20, 21])

console.log(ywSet)  // {'18', '19', 19, 20,21}
ywset.add('17').add({'name': '青年野味'})

console.log(ywSet) // {'18', '19', 19, 20,21,'17',{'name': '青年野味'}}
console.log(ywSet.size) // 7

mySet.has(20) // true

Set遍历方法 ​

  • keys()：返回键名的遍历器。
  • values()：返回键值的遍历器。
  • entries()：返回键值对的遍历器。
  • forEach()：使用回调函数遍历每个成员。

由于Set结构没有键名，只有键值（或者说键名和键值是同一个值），所以keys方法和values方法的行为完全一致。

const ywSet = new Set(['a', 'b', 'c'])

for (let item of ywSet.keys()) {
  console.log(item)
}
// a
// b
// c

for (let item of ywSet.values()) {
  console.log(item)
}
// a
// b
// c

for (let item of ywSet.entries()) {
  console.log(item)
}
// ["a", "a"]
// ["b", "b"]
// ["c", "c"]

// 直接遍历set实例，等同于遍历set实例的values方法
for (let i of ywSet) {
  console.log(i)
}
// a
// b
// c

ywSet.forEach((value, key) => console.log(key + ' : ' + value))

// a: a
// b: b
// c: c
const ywSet = new Set(['a', 'b', 'c'])

for (let item of ywSet.keys()) {
  console.log(item)
}
// a
// b
// c

for (let item of ywSet.values()) {
  console.log(item)
}
// a
// b
// c

for (let item of ywSet.entries()) {
  console.log(item)
}
// ["a", "a"]
// ["b", "b"]
// ["c", "c"]

// 直接遍历set实例，等同于遍历set实例的values方法
for (let i of ywSet) {
  console.log(i)
}
// a
// b
// c

ywSet.forEach((value, key) => console.log(key + ' : ' + value))

// a: a
// b: b
// c: c

Set 对象作用 ​

  1. 数组去重(利用扩展运算符)
const ywSet = new Set([1, 2, 3, 4, 4])
[...ywSet] // [1, 2, 3, 4]
const ywSet = new Set([1, 2, 3, 4, 4])
[...ywSet] // [1, 2, 3, 4]
  1. 合并两个set对象
let a = new Set([1, 2, 3])
let b = new Set([4, 3, 2])
let union = new Set([...a, ...b]) // {1, 2, 3, 4}
let a = new Set([1, 2, 3])
let b = new Set([4, 3, 2])
let union = new Set([...a, ...b]) // {1, 2, 3, 4}
  1. 交集
let a = new Set([1, 2, 3])
let b = new Set([4, 3, 2])
let intersect = new Set([...a].filter(x => b.has(x)))  // {2, 3} 利用数组的filter方法
let a = new Set([1, 2, 3])
let b = new Set([4, 3, 2])
let intersect = new Set([...a].filter(x => b.has(x)))  // {2, 3} 利用数组的filter方法
  1. 差集
let a = new Set([1, 2, 3])
let b = new Set([4, 3, 2])
let difference = new Set([...a].filter(x => !b.has(x))) //  {1}
let a = new Set([1, 2, 3])
let b = new Set([4, 3, 2])
let difference = new Set([...a].filter(x => !b.has(x))) //  {1}

好了，现在我们就使用完Set对象的相关属性和方法了，现在让我们一起去实现它吧

Set方法手动实现 ​

js
        class yw_Set {
            constructor(yw_arguments = []) {
                    if (typeof yw_arguments[Symbol.iterator] !== "function") {
                        throw new TypeError(`${yw_arguments}不是一个可遍历的值`)
                    }
                    this.newArr = []
                    for (const data of yw_arguments) {
                        this.add(data)
                    }

                }
                *[Symbol.iterator]() {
                    let i = 0;
                    while (this.newArr[i] !== undefined) {
                        yield this.newArr[i];
                        ++i;
                    }
                }

            size() {
                return this.newArr.length
            }
            add(data) {

                if (!this.has(data)) {
                    this.newArr.push(data)
                    return true
                } else {
                    return false
                }
            }
            has(data) {

                for (const item of this.newArr) {
                    if (item === 0 && data === 0) {
                        return true
                    }
                }
                if (this.newArr.indexOf(data) !== -1) {
                    return true
                }

                return false
            }

            delete(del) {
                if (this.has(del)) {
                    for (let i = 0; i < this.newArr.length; i++) {
                        if (this.newArr[i] === 0 && del === 0) {
                            this.newArr.splice(i, 1)
                            return true
                        } else if (Object.is(del, this.newArr[i])) {
                            this.newArr.splice(i, 1)
                            return true
                        }
                    }
                } else {
                    return false
                }
            }
            clear() {
                this.newArr.splice(0, this.newArr.length)
                return true
            }
            
            //这里就省略了遍历方法的，很简单，就跟Map的差不多的，但是只有value值而已
        }
        class yw_Set {
            constructor(yw_arguments = []) {
                    if (typeof yw_arguments[Symbol.iterator] !== "function") {
                        throw new TypeError(`${yw_arguments}不是一个可遍历的值`)
                    }
                    this.newArr = []
                    for (const data of yw_arguments) {
                        this.add(data)
                    }

                }
                *[Symbol.iterator]() {
                    let i = 0;
                    while (this.newArr[i] !== undefined) {
                        yield this.newArr[i];
                        ++i;
                    }
                }

            size() {
                return this.newArr.length
            }
            add(data) {

                if (!this.has(data)) {
                    this.newArr.push(data)
                    return true
                } else {
                    return false
                }
            }
            has(data) {

                for (const item of this.newArr) {
                    if (item === 0 && data === 0) {
                        return true
                    }
                }
                if (this.newArr.indexOf(data) !== -1) {
                    return true
                }

                return false
            }

            delete(del) {
                if (this.has(del)) {
                    for (let i = 0; i < this.newArr.length; i++) {
                        if (this.newArr[i] === 0 && del === 0) {
                            this.newArr.splice(i, 1)
                            return true
                        } else if (Object.is(del, this.newArr[i])) {
                            this.newArr.splice(i, 1)
                            return true
                        }
                    }
                } else {
                    return false
                }
            }
            clear() {
                this.newArr.splice(0, this.newArr.length)
                return true
            }
            
            //这里就省略了遍历方法的，很简单，就跟Map的差不多的，但是只有value值而已
        }

我们来实验一下吧

js
let set1 = new yw_Set()
set1.add(1).add(2).add(3)
set1.add(1)
console.log(set1) //{1, 2, 3}

set1.delete(1) // { 2, 3}
let set1 = new yw_Set()
set1.add(1).add(2).add(3)
set1.add(1)
console.log(set1) //{1, 2, 3}

set1.delete(1) // { 2, 3}

参考文章 ​

彻底弄懂ES6中的Map和Set

结语 ​

这次是我第一次写文章不太成熟，后续还会写出其他的文章，希望大佬们能指点使我成长。