当前位置 博文首页 > 司夏的博客：JavaScript 数据结构与算法（字典）
字典和散列表是用来存储唯一值（不重复的值）的数据结构
在集合中，把每个值当作主要元素。在字典（或映射）中，则用[键，值]对的形式来存储数据。在散列表中也是一样（也是以[键，值]对的形式来存储数据）。
集合表示一组互不相同的元素（不重复的元素）。在字典中，存储的是[键，值]对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。字典也称作映射、符号表或关联数组。 在计算机科学中，字典经常用来保存对象的引用地址。
与 Set 类相似，ECMAScript 2015 同样包含了一个 Map 类的实现，即我们所说的字典。
Dictionary 类的骨架。
class Dictionary {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn; // 将 key 转化为字符串的函数
this.table = {}; // 在一个 Object 的实例中存储字典中的元素而不是数组
// 会将[键，值]对保存为 table[key] = {key, value}
}
}
JavaScript 允许我们使用方括号（[]）获取对象的属性，将属性名作为“位置”传入即可。这也是称它为关联数组的原因！
在字典中，理想的情况是用字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象）。但是，由于 JavaScript 不是强类型的语言，我们不能保证键一定是字符串。所以需要把所有作为键名传入的对象转化为字符串，使得从 Dictionary 类中搜索和获取值更简单。
自定义函数 defaultToString 将 key 转化为字符串的函数
defaultToString 函数声明如下。
function defaultToString(item) {
if (item === null) {
return 'NULL';
} else if (item === undefined) {
return 'UNDEFINED';
} else if (typeof item === 'string' || item instanceof String) {
return `${item}`;
}
return item.toString();
}
1. 检测一个键是否存在于字典中
hasKey(key)：如果某个键值存在于该字典中，返回 true，否则返回 false。
hasKey(key) {
return this.table[this.toStrFn(key)] != null;
}
2. 在字典和 ValuePair 类中设置键和值
set(key, value) ：向字典中添加新元素。如果 key 已经存在，那么已存在的 value 会被新的值覆盖。
set(key, value) {
if (key != null && value != null) {
const tableKey = this.toStrFn(key); // 获取表示 key 的字符串
this.table[tableKey] = new ValuePair(key, value); // 实例化 ValuePair 类
return true; // true，表示字典可以将key 和 value 保存下来
}
return false;
}
ValuePair 类的定义
class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}
// 为了字典能更简单地通过 toString 方法输出结果
toString() {
return `[#${this.key}: ${this.value}]`;
}
}
3. 从字典中移除一个值
remove(key) ：通过使用键值作为参数来从字典中移除键值对应的数据值。
remove(key) {
if (this.hasKey(key)) {
delete this.table[this.toStrFn(key)];
return true;
}
return false;
}
4. 从字典中检索一个值
get(key) ：通过以键值作为参数查找特定的数值并返回
方法一：
get(key) {
const valuePair = this.table[this.toStrFn(key)];
return valuePair == null ? undefined : valuePair.value;
}
方法二
get(key) {
if (this.hasKey(key)) {
return this.table[this.toStrFn(key)];
}
return undefined;
}
在第二种方式中，会获取两次 key 的字符串以及访问两次 table 对象：第一次是在 hasKey 方法中，第二次是在 if 语句内。所以第一种方式的消耗更少。
5. keys、values 和 valuePairs 方法
keys() ：将字典所包含的所有键名以数组形式返回。
keys() {
return this.keyValues().map(valuePair => valuePair.key);
}
values()：将字典所包含的所有数值以数组形式返回。
values() {
// 使用了 Array 类中的 map 方法（ES2015（ES6）引入）来迭代
return this.keyValues().map(valuePair => valuePair.value);
}
keyValues()：将字典中所有[键，值]对返回。
keyValues() {
return Object.values(this.table); // Object 类内置的 values 方法（ ECMAScript 2017引入）
}
兼容所有浏览器的 Object.values方法（替代方案）
keyValues() {
const valuePairs = [];
for (const k in this.table) { // 迭代了 table 对象的所有属性
if (this.hasKey(k)) {
valuePairs.push(this.table[k]); // 将 table 对象中的 valuePair 加入结果数组
}
}
return valuePairs;
};
6. 用 forEach 迭代字典中的每个键值对
forEach(callbackFn) ：迭代字典中所有的键值对。callbackFn 有两个参数：key 和 value。该方法可以在回调函数返回 false 时被中止（和 Array 类中的 every 方法相似）。
forEach(callbackFn) {
const valuePairs = this.keyValues(); // 获取字典中所有 valuePair 构成的数组
for (let i = 0; i < valuePairs.length; i++) { // 迭代每个 valuePair
// 执行以参数形式传入 forEach 方法的 callbackFn 函数
const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
if (result === false) {
break;
}
}
}
7. clear、size、isEmpty 和 toString 方法
clear() ：删除该字典中的所有值。
clear() {
this.table = {};
}
size() ：返回字典所包含值的数量。与数组的 length 属性类似。
size() {
return Object.keys(this.table).length;
}
isEmpty()：在 size 等于零的时候返回 true，否则返回 false。
isEmpty() {
return this.size() === 0;
}
toString ()：将字典输出以字符串返回
toString() {
if (this.isEmpty()) {
return '';
}
const valuePairs = this.keyValues();
let objString = `${valuePairs[0].toString()}`; // 将第一个 valuePair 加入结果字符串
for (let i = 1; i < valuePairs.length; i++) {
objString = `${objString},${valuePairs[i].toString()}`; // 如果数组中还有值，同样将其加入结果字符串
}
return objString; // 将字符串返回
}
完整的 Dictionary 类
class Dictionary {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn; // 将 key 转化为字符串的函数
this.table = {}; // 在一个 Object 的实例中存储字典中的元素而不是数组
// 会将[键，值]对保存为 table[key] = {key, value}
};
hasKey(key) {
return this.table[this.toStrFn(key)] != null;
}
set
