集合结构
集合是由一组无序且唯一(即不能重复)的项组成的。
class MySet {
items = {}
add(element) {
if (!this.has(element)) {
this.items[element] = element
return true
}
return false
}
delete(element) {
if (this.has(element)) {
delete this.items[element]
return true
}
return false
}
has(element) {
return element in this.items
}
clear() {
this.items = {}
}
size() {
return Object.keys(this.items).length
}
values() {
return Object.values(this.items)
}
}
let myset = new MySet()
let arr = [1, 1, 2, 2, 5, 5, 8, 5]
arr.forEach((item) => {
myset.add(item)
})
console.log(myset.values()) //[1, 2, 5, 8]
ES6的Set
let s1 = new Set([1, 2, 3])
let s2 = new Set([2, 3, 4])
// 并集
let myset = new Set([...s1, ...s2])
console.log(myset) //{1, 2, 3, 4}
// 交集
myset = new Set([...s1].filter((item) => s2.has(item)))
console.log(myset) //{2, 3}
// 差集
myset = new Set([...s1].filter((item) => !s2.has(item)))
console.log(myset) //{1}
字典结构
字典和集合很相似,集合以[值,值]的形式存储元素,字典则是以[键,值]的形式来存储元素。
class ValuePair {
constructor(key, value) {
this.key = key
this.value = value
}
}
class Dictionary {
table = {}
toStr(item) {
if (item === null) {
return "NULL"
} else if (item === undefined) {
return "UNDEFINED"
} else if (typeof item === "string" || item instanceof String) {
return item
}
return JSON.stringify(item)
}
hasKey(key) {
return this.table[this.toStr(key)] != null
}
set(key, value) {
if (key != null && value != null) {
const tableKey = this.toStr(key)
this.table[tableKey] = new ValuePair(key, value)
return true
}
return false
}
get(key) {
const valuePair = this.table[this.toStr(key)]
return valuePair == null ? undefined : valuePair.value
}
remove(key) {
if (this.hasKey(key)) {
delete this.table[this.toStr(key)]
return true
}
return false
}
keys() {
return this.keyValues().map((item) => item.key)
}
values() {
return this.keyValues().map((item) => item.value)
}
keyValues() {
return Object.values(this.table)
}
size() {
return Object.keys(this.table).length
}
isEmpty() {
return this.size() === 0
}
clear() {
this.table = {}
}
forEach(cb) {
const valuePair = this.keyValues()
for (let i = 0; i < valuePair.length; i++) {
cb(valuePair[i].key, valuePair[i].value)
}
}
}
let mymap = new Dictionary()
mymap.set("name", "张三")
mymap.set({ age: 18 }, "年龄")
mymap.forEach((key, value) => {
console.log(key, value)
})
散列表
HashMap类,它是Dictionary类的一种散列表实现方式。散列算法的作用是尽可能快地在数据结构中找到一个值。
class ValuePair {
constructor(key, value) {
this.key = key
this.value = value
}
}
class HashTable {
table = {}
toStr(item) {
if (item === null) {
return "NULL"
} else if (item === undefined) {
return "UNDEFINED"
} else if (typeof item === "string" || item instanceof String) {
return item
}
return JSON.stringify(item)
}
hashCode(key) {
const tableKey = this.toStr(key)
let hash = 5381
for (let i = 0; i < tableKey.length; i++) {
hash = hash * 33 + tableKey.charCodeAt(i)
}
return hash % 1013
}
set(key, value) {
if (key != null && value != null) {
const position = this.hashCode(key)
this.table[position] = new ValuePair(key, value)
return true
}
return false
}
get(key) {
const valuePair = this.table[this.hashCode(key)]
return valuePair == null ? undefined : valuePair.value
}
remove(key) {
const hash = this.hashCode(key)
const valuePair = this.table[hash]
if (valuePair != null) {
delete this.table[hash]
return true
}
return false
}
}
let mymap = new HashTable()
mymap.set("name", "张三")
mymap.set({ age: 18 }, "年龄")
ES6的Map
let mymap = new Map()
mymap.set("name", "张三")
obj = { age: 18 }
mymap.set(obj, "年龄")
console.log(mymap)
obj = null
console.log(mymap)
WeakMap只能是对象为键:
let mymap = new WeakMap()
obj = { age: 18 }
mymap.set(obj, "年龄")
obj = null
console.log(mymap)