数据结构与算法-字典

ES6中新增了字典Map，这里我们基于对象来实现Map。

认识字典

字典的特点：

• 字典存储的是键值对，字典的主要特点是一一对应的关系。
• 字典中 key 是不能重复且无序的，而 value 可以重复。

字典和映射的关系：

• 有些编程语言中称这种映射关系为字典，因为它确实和生活中的字典比较相似，如比如Swift中Dictionary，Python中的dict
• 有些编程语言中称这种映射关系为Map 映射。比如Java中有HashMap、TreeMap等

字典和对象:

• 很多编程语言(比如Java)中对字典和对象区分比较明显，对象通常是一种在编译期就确定下来的结构，不可以动态的添加或者删除属性。而字典通常会使用类似于哈希表的数据结构去实现一种可以动态的添加数据的结构。
• 但是在JavaScript中，似乎对象本身就是一种字典。所有在早期的JavaScript中，没有字典这种数据类型，因此完全可以使用对象去代替。

字典

常见操作

• set(key,value) 向字典中添加新元素。
• remove(key) 通过使用键值来从字典中移除键值对应的数据值。
• has(key) 如果某个键值存在于这个字典中，则返回 true，反之则返回 false。
• get(key) 通过键值查找特定的数值并返回。
• clear() 将这个字典中的所有元素全部删除。
• size() 返回字典所包含元素的数量。与数组的 length 属性类似。
• keys() 将字典所包含的所有键名以数组形式返回。
• values() 将字典所包含的所有数值以数组形式返回。

封装

/**
 * 字典 基于对象
 */
module.exports = class Map {
  constructor () {
    this.items = {}
  }

  // 向字典中添加新元素
  set (key, value) {
    this.items[key] = value
  }

  // 如果某个键值存在于这个字典中，则返回 `true`，反之则返回 `false`
  has (key) {
    return this.items.hasOwnProperty(key)
  }

  // 通过使用键值来从字典中移除键值对应的数据值
  remove (key) {
    if (!this.has(key)) return false

    delete this.items[key]
    return true
  }

  // 通过键值查找特定的数值并返回
  get (key) {
    return this.has(key) ? this.items[key] : undefined
  }

  // 将这个字典中的所有元素全部删除
  clear () {
    this.items = {}
  }

  // 将字典所包含的所有键名以数组形式返回
  keys () {
    return Object.keys(this.items)
  }

  // 将字典所包含的所有数值以数组形式返回
  values() {
    return Object.values(this.items)
  }

  // 返回字典所包含元素的数量
  size () {
    return Object.keys(this.items).length
  }
}

测试

const Map = require('../../lib/Map')

const map = new Map()

// set
console.log('set', map.set('a', 'A'))
console.log('set', map.set('b', 'B'))
console.log('set', map.set('c', 'C'))
console.log('Map', map) // Map Map { items: { a: 'A', b: 'B', c: 'C' } }

// has
console.log('has', map.has('a')) // has true
console.log('has', map.has('b')) // has true

// remove
console.log('remove', map.remove('a')) // remove true
console.log('Map', map) // Map Map { items: { b: 'B', c: 'C' } }

// get
console.log('get', map.get('b')) // get B

// keys
console.log('keys', map.keys()) // keys [ 'b', 'c' ]

// values
console.log('values', map.values()) // values [ 'B', 'C' ]

// size
console.log('size', map.size()) // size 2