JavaScript数据结构与算法(集合与字典)

集合结构

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

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)