集合结构

集合是由一组无序且唯一(即不能重复)的项组成的。

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)