5.1 字典
在字典中，存储的是[键, 值]对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值, 值]的形式存储元素，字典则是以[键, 值]的形式来存储元素。字典也称作映射、符号表或关联数组。
在计算机科学中，字典经常用来保存对象的引用地址。
5.1.1 创建字典类
代码语言：javascript复制class Dictionary {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn;
this.table = {};
}
}5.1.2 向字典中添加新元素
代码语言：javascript复制set(key, value) {
if (key != null && value != null) {
const tableKey = this.toStrFn(key);
this.table[tableKey] = new ValuePair(key, value);
return true;
}
return false;
}5.1.3 从字典中获取键值对应的数据值
代码语言：javascript复制get(key) {
const valuePair = this.table[this.toStrFn(key)];
return valuePair == null ? undefined : valuePair.value;
}5.1.4 检测字典中是否存在键值对应的数据值
代码语言：javascript复制hasKey(key) {
return this.table[this.toStrFn(key)] != null;
}5.1.5 从字典中移除键值对应的数据值
代码语言：javascript复制remove(key) {
if (this.hasKey(key)) {
delete this.table[this.toStrFn(key)];
return true;
}
return false;
}5.1.6 将字典所包含的所有数值以数组形式返回
代码语言：javascript复制values() {
return this.keyValues().map(valuePair => valuePair.value);
}5.1.7 将字典所包含的所有键名以数组形式返回
代码语言：javascript复制keys() {
return this.keyValues().map(valuePair => valuePair.key);
}5.1.8 将字典中所有[键, 值]对返回
代码语言：javascript复制keyValues() {
return Object.values(this.table);
}5.1.9 迭代字典
代码语言：javascript复制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;
}
}
}5.1.10 判断字典是否为空
代码语言：javascript复制isEmpty() {
return this.size() === 0;
}5.1.11 返回字典所包含值的数量
代码语言：javascript复制size() {
return Object.keys(this.table).length;
}5.1.12 删除该字典中的所有值
代码语言：javascript复制clear() {
this.table = {};
}5.1.13 实现toSting方法
代码语言：javascript复制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;
}5.2 散列表
散列算法的作用是尽可能快地在数据结构中找到一个值。使用散列函数，就知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。
散列表有一些在计算机科学中应用的例子。因为它是字典的一种实现，所以可以用作关联数组。它也可以用来对数据库进行索引。
另一个很常见的应用是使用散列表来表示对象。JavaScript语言内部就是使用散列表来表示每个对象。此时对象的每个属性和方法（成员）被存储为key对象类型，每个key指向对应的对象成员。
5.2.1 创建散列表
代码语言：javascript复制class HashTable {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn;
this.table = {};
}
}5.2.2 创建（lose lose）散列函数
代码语言：javascript复制loseloseHashCode(key) {
if (typeof key === 'number') {
return key;
}
const tableKey = this.toStrFn(key);
let hash = 0;
for (let i = 0; i < tableKey.length; i ) {
hash = tableKey.charCodeAt(i);
}
return hash % 37;
}
hashCode(key) {
return this.loseloseHashCode(key);
}5.2.3 将键和值加入散列表
代码语言：javascript复制put(key, value) {
if (key != null && value != null) {
const position = this.hashCode(key);
this.table[position] = new ValuePair(key, value);
return true;
}
return false;
}5.2.4 从散列表中获取一个值
代码语言：javascript复制get(key) {
const valuePair = this.table[this.hashCode(key)];
return valuePair == null ? undefined : valuePair.value;
}5.2.5 从散列表中移除一个值
代码语言：javascript复制remove(key) {
const hash = this.hashCode(key);
const valuePair = this.table[hash];
if (valuePair != null) {
delete this.table[hash];
return true;
}
return false;
}5.2.6 获取散列表
代码语言：javascript复制getTable() {
return this.table;
}5.2.7 检查散列表是否为空
代码语言：javascript复制isEmpty() {
return this.size() === 0;
}5.2.8 获取散列表的长度
代码语言：javascript复制size() {
return Object.keys(this.table).length;
}5.2.9 清空散列表
代码语言：javascript复制clear() {
this.table = {};
}5.2.10 实现toString方法
代码语言：javascript复制toString() {
if (this.isEmpty()) {
return '';
}
const keys = Object.keys(this.table);
let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
for (let i = 1; i < keys.length; i ) {
objString = `${objString}, {${keys[i]} => ${this.table[keys[i]].toString()}}`;
}
return objString;
}5.3 处理散列表中的冲突
有时候，一些键会有相同的散列值，不同的值在散列表中对应相同位置的时候，我们称其为冲突。处理冲突有几种方法：分离链接和线性探查。
5.3.1 分离链接
分离链接法包括为散列表的每一位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是在HashTable实例之外还需要额外的存储空间。
5.3.2 线性探查
它处理冲突的方法是将元素直接存储到表中，而不用在单独的数据结构中。
当想向表中某个位置添加一个新元素的时候，如果索引为position的位置已经被占据了，就尝试position 1的位置。如果position 1的位置也被占据了，就尝试position 2的位置。以此类推，直到在散列表中找到一个空闲的位置。
线性探查技术分为两种：
第一种方法是软删除方法：我们使用一个特殊的值（标记）来表示键值对被删除了（惰性删除或软删除）。经过一段时间，散列表被操作过后，我们会得到一个标记了若干删除位置的散列表。这会逐渐降低散列表的效率，因为搜索键值会随时间变得更慢。
第二种方法需要检验是否有必要将一个或多个元素移动到之前的位置。这种方法可以避免找到一个空位置。如果移动元素是必要的，我们就需要在散列表中挪动键值对。
5.4 创建更好的散列函数
我们实现的lose lose散列函数并不是一个表现良好的散列函数，因为它会产生太多的冲突。一个表现良好的散列函数是由几个方面构成的：插入和检索元素的时间（即性能），以及较低的冲突可能性。
另一个可以实现的比lose lose更好的散列函数是djb2：
代码语言：javascript复制djb2HashCode(key) {
const tableKey = this.toStrFn(key);
let hash = 5381;
for (let i = 0; i < tableKey.length; i ) {
hash = (hash * 33) tableKey.charCodeAt(i);
}
return hash % 1013;
}5.5 ES6 Map类
和我们的Dictionary类不同，ES6的Map类的values方法和keys方法都返回Iterator，而不是值或键构成的数组。另一个区别是：我们实现的size方法返回字典中存储的值得个数，而ES6的Map类则有一个size属性。
5.6 ES6 WeakSet类和WeakMap类
除了Set和Map这两种新的数据结构，ES6还增加了它们的弱化版本WeakSet和WeakMap。
基本上，Set和Map与其弱化版本之间仅有的区别是：
1）WeakSet类和WeakMap类没有entries、keys和values等方法；
2）只能用对象作为键。
创建和使用这两个类主要是为了性能。WeakSet类和WeakMap类是弱化的（用对象作为键），没有强引用的键，这使得JavaScript的垃圾回收器可以从中清除整个入口。
另一个优点是，必须用键才可以取出值。这些类没有entries、keys和values等迭代器方法，因此，除非你知道键，否则没有办法取出值。
详细代码：
https://github.com/chenxiaohuan117/learning-javasrcipt-note/tree/main/《学习JavaScript数据结构与算法》(第3版)
