数据结构 - 数据结构与算法学习之字典 - 《数据结构与算法》

什么是字典
实现字典
ES6 中的Map
- Map 实例的属性及方法：

什么是字典

字典是一种以 [键，值] 对存储数据的数据结构。在字典中，键名是用来查询特定元素的。字典也称作映射、符号表或关联数组。
**

实现字典

定义 ValuePair 类

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    const key = typeof this.key === 'object' ? JSON.stringify(this.key) : this.key
    return `[#${key}: ${this.value}]`;
  }
}

ValuePair 类将原始的 key 和 value 转换成字符串，便于我们同时将原始的 key 和 value 保存在字典中

定义 defaultToString 函数

const defaultToString = (item) => {
  if (item === null) {
    return 'NULL';
  } else if (item === 'undefined') {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  } else if (typeof item === 'object') {
    return JSON.stringify(item);
  }
  return item.toString();
}

JavaScript 的对象（Object），本质上是键值对的集合（Hash 结构），传统上只能用字符串作为键。因此，我们需要定义一个转换函数，将所有作为键名传入的对象转化为字符串，使得从 Dictionary 类中搜索和获取值更简单。

定义 Dictionary 类

class Dictionary {
    constructor(toStrFn = defaultToString) {
      this.toStrFn = toStrFn;
    this.table = {};
  }
}

在 Dictionary 类中，我们使用 Object 的实例来存储字典中的元素，我们会将 [键, 值] 对保存为 table[key] = { key, value }的形式。

下面，我们为字典定义一些可用的方法：
set(key, value) 向字典中添加新元素
remove(key) 移除健值对应的数据值
hasKey(key) 检查某个健值是否存在于字典中
get(key) 获取字典中的某个健值
clear() 清空字典中的所有值
size() 返回字典中元素的数量
isEmpty() 判断字典是否为空字典
keys() 以数组形式返回字典中的所有键名
values() 以数组的形式返回字典中的所有健值
keyValues() 返回字典中的所有 [键, 值] 对
forEach(callbackFn) 迭代字典中的所有健值对
toString() 返回字典内容的字符串形式

下面，我们逐一实现字典的方法：

set(key, value) 向字典中添加新元素

set(key, value) {
  // key/value 不为 null 或 undefined，将 key/value 添加到字典中
    if (key != null && value != null) {
    // 获取表示 key 的字符串
      const tableKey = this.toStrFn(key);
    // 创建一个新的健值对，将其保存到 table 对象上
    this.table[tableKey] = new ValuePair(key, value);
    // 返回 true 表示key/value已添加到字典中
    return true;
  }
  // 返回 false 表示没有将 key/value 添加到字典中
  return false
}

set 方法用于向字典中添加新的元素或者更新已有的元素。

set 方法接收 key 和 value 作为参数，如果 key 和 value 不是 undefined 或 null，那么我们获取表示 key 的字符串，创建一个新的健值对并将其赋值给 table 对象上的 key 属性，并返回 true，表示key和value已经添加到字典中；否则返回false，表示没有将key和value添加到字典中

remove(key) 移除健名对应的数据值

remove(key) {
    if (this.hasKey(key)) {
      // delete this.table[this.toStrFn(key)];
    // Reflect.deleteProperty方法等同于delete obj[name]，用于删除对象的属性
    Reflect.deleteProperty(this.table, this.toStrFn(key));
    // 返回 true 表示健值移除成功
    return true;
  }
  // 键名不存在
  return false;
}

removeKey 方法根据键名来移除字典中对应的健值。

我们可以使用 delete 运算符来从 table对象中删除 key 属性，也可以使用 Reflect 对象的 deleteProperty 方法来删除 table 对象中的 key 属性，Reflect.deleteProperty 方法等同于 delete obj[name]。如果能将 value 从字典中删除，就返回 true，否则就返回 false。

hasKey(key) 检查某个健值是否存在于字典中

hasKey(key) {
    return this.table[this.toStrFn(key)] != null;
}

hasKey 方法会检查一个给定键名的健值对是否存在于字典中，如果存在，返回 true，否则返回 false

get(key) 获取字典中的某个健值

get(key) {
    const valuePair = this.table[this.toStrFn(key)];
  return valuePair == null ? undefined : valuePair.value;
}

get 方法在字典中查找一个给定的key，并将该 key 对应的 value 返回。

get 方法首先会检索给定的key在字典中是否存在，如果该key对应的 valuePair 对象存在，则返回该值，否则返回一个 undefined 值。

clear() 清空字典中的所有值

clear() {
    this.table = {}
}

clear 方法用于清空字典中的所有值。要清空字典的内容，我们只需要将 table 对象重新赋值为空对象即可。

size() 返回字典中元素的数量

size() {
    return Object.keys(this.table).length;
}

size 方法返回字典中值的个数。我们可以使用 Object.keys 方法来获取 table 对象中的所有键名，然后通过数组的 length 属性获取个数。

isEmpty() 判断字典是否为空字典

isEmpty() {
    return this.size() === 0;
}

size 方法判断字典是否为空。检验字典是否为空，我们可以获取它的 size 是否为 0，如果 size 为 0，表示字典为空。

keys() 以数组形式返回字典中的所有键名

keys() {
    return this.keyValues().map(valuePair => valuePair.key);
}

key 方法返回字典中的所有原始键名。在 keys 方法中，我们调用 keyValues 方法获取所有的健值，然后迭代每一个健值 valuePair，返回存储在 valuePair 中的原始键名。

values() 以数组的形式返回字典中的所有健值

values() {
    return this.keyValues().map(valuePair => valuePair.value);
}

values 方法返回字典中的所有原始value值。在 values 方法中，我们调用 keyValues 方法获取字典中存储的所有健值，然后迭代每一个健值 valuePair，返回存储在 valuePair 中的原始 value 值。

keyValues() 返回字典中的所有 [键, 值] 对

keyValues() {
    const valuePairs = [];
  // 迭代 table 对象
  for (let k in this.table) {
      if (this.hasKey(k)) {
      // 将 table 对象中的值添加到数组中
        valuePairs.push(this.table[k]);
    }
  }
  return valuePairs;
}

keyValues 方法返回字典中存储的所有健值。在方法中，我们迭代 table 对象，如果 key 对应的值存在，我们将值添加到数组 valuePairs 中。

forEach(callbackFn) 迭代字典中的所有健值对

forEach(callbackFn) {
  // 获取字典中所有的健值
    const valuePairs = this.keyValues();
  for(let i = 0; i < valuePairs.length; i++) {
    // 迭代 每个健值，执行 callbackFn 回调函数
      const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
    if (result === false) {
      // 中断 forEach 方法的执行，并打断迭代 valuePairs 的 for 循环
      break;
    }
  }
}

forEach 方法迭代字典中的所有健值对。forEach 方法的参数 callbackFn是一个回调函数，有两个参数：key 和 value。

首先，我们获取字典中存储的所有健值 valuePairs，然后迭代每个健值 valuePair 并执行传入的参数 callbackFn 回调函数，callbackFn将会返回存储在 valuePair 中的原始健名和原始健值。如果 callbackFn 函数调用时返回了 false，我们会中断 forEach 方法的执行，打断正在迭代 valuePairs 的 for 循环。

toString() 返回字典内容的字符串形式

toString() {
  if (this.isEmpty()) {
      return '';
  }
  const valuePairs = this.keyValues();
  let objString = `${valuePairs[0].toString()}`;
  for (let i = i; i < valuePairs.length; i++) {
      objString = `${objString}, ${valuePairs[i].toString()}`;
  }
  return objString;
}

在 toString 方法中，如果字典为空，我们就返回一个空字符串。如果不是，我们迭代字典中的所有健值，调用 toString 方法将每个健值转换为字符串。最后在方法末尾将代表字典内容的字符串返回。

完整代码

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    const key = typeof this.key === 'object' ? JSON.stringify(this.key) : this.key
    return `[#${key}: ${this.value}]`;
  }
}
const defaultToString = (item) => {
  if (item === null) {
    return 'NULL';
  } else if (item === 'undefined') {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  } else if (typeof item === 'object') {
    return JSON.stringify(item);
  }
  return item.toString();
}
class Dictionary {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }
  // 向字典中添加新元素
  set(key, value) {
    if (key != null && value != null) {
      const tableKey = this.toStrFn(key);
      this.table[tableKey] = new ValuePair(key, value);
      return true;
    }
    return false;
  }
  // 移除键名对应的数据值
  remove(key) {
    if (this.hasKey(key)) {
      Reflect.deleteProperty(this.table, this.toStrFn(key));
      return true;
    }
    return false;
  }
  // 检查某个键值是否存在于字典中
  hasKey(key) {
    return this.table[this.toStrFn(key)] != null;
  }
  // 获取字典中的某个键值
  get(key) {
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
  }
  // 清空字典中的所有值
  clear() {
    this.table = {};
  }
  // 返回字典中所有元素的数量
  size() {
    return Object.keys(this.table).length;
  }
  // 判读字典是否为空
  isEmpty() {
    return this.size() === 0;
  }
  // 以数组形式返回字典中的所有键名
  keys() {
    return this.keyValues().map(valuePair => valuePair.key);
  }
  // 以数组形式返回字典中的所有健值
  values() {
    return this.keyValues().map(valuePair => valuePair.value);
  }
  // 返回字典中的所有 [健, 值] 对
  keyValues() {
    return Object.values(this.table);
  }
  // 迭代字典中的所有健值对
  forEach(callbackFn) {
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
      const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
      if (result === false) {
        break;
      }
    }
  }
  // 返回字典内容的字符串形式
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const valuePairs = this.keyValues();
    let objString = `${valuePairs[0].toString()}`;
    for (let i = 1; i < valuePairs.length; i++) {
      objString = `${objString}, ${valuePairs[i].toString()}`;
    }
    return objString;
  }
}

ES6 中的Map

Map 是 ES6 提供的一种数据结构，它类似于对象，是键值对的集合，但是 “键” 的范围不限于字符串，各种类型的值（包括对象）都可以当作键。我们可以将 ES6 理解为我们在上面实现的字典。

Map 实例的属性及方法：

size：返回Map结构的成员数量
get()：返回键值对
set()：添加键值对，返回实例
delete()：删除键值对，返回布尔
has()：检查键值对，返回布尔
clear()：清除所有成员
keys()：返回以键为遍历器的对象
values()：返回以值为遍历器的对象
entries()：返回以键和值为遍历器的对象
forEach()：使用回调函数遍历每个成员

数据结构与算法学习之字典