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

共计 3068 个字符，预计需要花费 8 分钟才能阅读完成。

集合结构

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

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)