|
数据结构-学习笔记整合
数据结构-栈(学习笔记)
数据结构-队列(学习笔记)
数据结构-链表(学习笔记)
数据结构-集合(学习笔记)
数据结构|字典和散列表(前端管它叫对象)
数据结构-二叉树和二叉搜索树
数据结构|二叉堆
前言
在集合(Set)中，我们的关注点放在集合(Set)的每个值本身，集合(Set)以[值，值]的形式存储元素，而在字典中，是用[键，值]对的形式存储数据。字典也称作映射，符号表或者关联数组。
散列表(也叫HashTable类 或 HashMap类)，是字典的一种散列表实现方式。JavaScript的对象(Object)，本质上是键值对的集合(Hash结构)，但是传统上只能用字符串当作键，因此ES6 带来了Map类和Map类的弱化版本WeakMap类。
集合、散列表与字典都是用来存储唯一值(不重复的值)的数据结构。
字典(Dictionary类)
定义
在字典中，是用[键，值]对的形式存储数据。字典也称作映射，符号表或者关联数组。
实际中的字典
一个实际的字典（单词和它们的释义）
地址簿、通讯录
代码实现
字典在理想状态下，使用字符串作为键名，值可以是任何数据类型，所以需要一个方法把所有键名转换为字符串。使字典类更容易搜索或获取值。
/**
* 字典的理想状态下是将字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象）
* 此方法把传入的键名转换为字符串
* @param {*} item 传入的键名
* @returns {string}
*/
export function defaultToString(item) {
if (item === null) { // 如果key是null
return 'NULL'; // 以NULL字符串返回
}
if (item === undefined) { // 如果key是undefined
return 'UNDEFINED'; // 以UNDEFINED字符串返回
}
if (typeof item === 'string' || item instanceof String) { // 如果是一个字符串，那么直接返回它
return `${item}`;
}
return item.toString(); // 否则将其转换为字符串返回
}
复制代码
在字典中，为了方便后续延伸字典类，字典中的值需要把原始的key和value都保存到字典中。
/**
* ValuePair 类
* 为了保存信息的需要，我们同样要保存原始的 key 和 value
* @class ValuePair
*/
export class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}
/**
*
* 将key和value通过字符串的方式返回出来
* @returns {string}
* @memberof ValuePair
*/
toString() {
return `[#${this.key}: ${this.value}]`;
}
}
复制代码
有了它们，便可以着手实现最终的字典类。
/**
* 在集合(Set)中，我们的关注点放在集合(Set)的每个值本身，集合(Set)以[值，值]的形式存储元素，而在字典中，是用[键，值]对的形式存储数据。字典也称作映射，符号表或者关联数组。
散列表(也叫HashTable类 或 HashMap类)，是字典的一种散列表实现方式。JavaScript的对象(Object)，本质上是键值对的集合(Hash结构)，但是传统上只能用字符串当作键，因此ES2015 带来了Map类和Map类的弱化版本WeakMap类。
集合、散列表与字典都是用来存储唯一值(不重复的值)的数据结构。
*/
/**
* 字典的理想状态下是将字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象）
* 此方法把传入的键名转换为字符串
* @param {*} item 传入的键名
* @returns {string}
*/
export function defaultToString(item) {
if (item === null) { // 如果key是null
return 'NULL'; // 以NULL字符串返回
}
if (item === undefined) { // 如果key是undefined
return 'UNDEFINED'; // 以UNDEFINED字符串返回
}
if (typeof item === 'string' || item instanceof String) { // 如果是一个字符串，那么直接返回它
return `${item}`;
}
return item.toString(); // 否则将其转换为字符串返回
}
/**
* ValuePair 类
* 为了保存信息的需要，我们同样要保存原始的 key 和 value
* @class ValuePair
*/
export class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}
/**
*
* 将key和value通过字符串的方式返回出来
* @returns {string}
* @memberof ValuePair
*/
toString() {
return `[#${this.key}: ${this.value}]`;
}
}
// 基于 ES2015 的 Map 类的设计思想来实现 Dictionary 类
export class Dictionary {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn; // 也可以传入自定义的函数来指定如何将 key 转化为字符串
this.table = {}; // 用一个Object的实例存储字典中的元素
}
/**
* 向字典中添加新元素。如果 key 已经存在，那么已存在的 value 会被新的值覆盖
* @param {string} key 需要添加新项的key
* @param {*} value 需要添加新项的value
* @return {boolean} 如果添加成功返回true，否则返回false
*/
set(key, value) {
if (key != null && value != null) { // 如果 key 和 value 都不是 undefined 或 null
const tableKey = this.toStrFn(key); // 获取表示 key 的字符串
this.table[tableKey] = new ValuePair(key, value); // 创建一个新的键值对并将其赋值给 table 对象上的 key属性（tableKey）
return true; // 添加/覆盖成功返回true
}
// 否则返回false
return false;
}
/**
*通过以键值作为参数查找特定的数值并返回
* @param {*} key 需要获取的key值
* @returns {*} 返回获取到的valuePair或者undefined
*/
get(key) {
const valuePair = this.table[this.toStrFn(key)]; // 获取指定key值的valuePair
return valuePair === null ? undefined : valuePair.value; // 如果 valuePair 对象存在，将返回该值，否则将返回一个 undefined 值
}
/**
*
*如果某个键值存在于该字典中，返回 true，否则返回 false
* @param {*} key
* @returns {boolean}
*/
hasKey(key) {
return this.table[this.toStrFn(key)] != null;
}
/**
*
*通过使用键值作为参数来从字典中移除键值对应的数据值
* @param {*} key 要删除的key值
* @returns {boolean} 是否删除成功
*/
remove(key) {
if (this.hasKey(key)) { // 如果key存在
delete this.table[this.toStrFn(key)]; // 在table对象删除指定的key
return true; // 成功返回true
}
// key不存在，返回false
return false;
}
/**
*
*将字典所包含的所有数值以数组形式返回
* @returns {array}
*/
values() {
return this.keyValues().map(valuePair => valuePair.value);
}
/**
*
* 将字典所包含的所有键名以数组形式返回
* @returns {array}
*/
keys() {
return this.keyValues().map(valuePair => valuePair.key);
}
/**
*
*将字典中所有[键，值]对返回
* @returns {array}
*/
keyValues() {
return Object.values(this.table);
}
/**
*迭代字典中所有的键值对。callbackFn 有两个参数：key和value。
*该方法可以在回调函数返回 false 时被中止（和 Array 类中的 every 方法相似）。
* @param {*} callbackFn
*/
forEach(callbackFn) {
const valuePairs = this.keyValues(); // 获取字典的所有键值对
for (let i = 0; i < valuePairs.length; i++) { // 遍历字典
const result = callbackFn(valuePairs[i].key, valuePairs[i].value); //执行以参数形式传入 forEach 方法的 callbackFn 函数
if (result === false) { // 如果回调函数返回了 false
break; // 会中断 forEach 方法的执行,打断正在迭代 valuePairs 的 for 循环
}
}
}
/**
*在 size 等于零的时候返回 true，否则返回 false
* @returns
*/
isEmpty() {
return this.size() === 0;
}
/**
*
*返回字典所包含值的数量。与数组的 length 属性类似
* @returns {Number}
*/
size() {
return Object.keys(this.table).length;
}
/**
* 删除该字典中的所有值
*/
clear() {
this.table = {};
}
/**
* 以字符串的方式输出字典的值
* @returns {string}
*/
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;
}
}
复制代码
体验Dictionary类
创建字典类实例,并传入三个键值对
const dictionary = new Dictionary();
dictionary.set('Gandalf', '[email protected]');
dictionary.set('John', '[email protected]');
dictionary.set('Tyrion', '[email protected]');
复制代码
查找 Gandalf 是否在字典类实例中
console.log(dictionary.hasKey('Gandalf')); // 返回true
复制代码
获取字典类实例的大小
console.log(dictionary.size()); // 返回3
复制代码
获取字典类实例的所有key
console.log(dictionary.keys()); // ["Gandalf", "John", "Tyrion"]
复制代码
获取字典类实例的所有value
console.log(dictionary.values()); // ["[email protected]", "[email protected]", "[email protected]"]
复制代码
获取字典类实例中的Tyrion
console.log(dictionary.get('Tyrion')); // [email protected]
复制代码
删除字典类实例中的John，并查看是否已经删除。
dictionary.remove('John');
console.log(dictionary.keyValues()); // [{key: "Gandalf", value: "[email protected]"}, {key: "Tyrion", value:"[email protected]"}]
复制代码
forEach循环迭代字典类实例
dictionary.forEach((k, v) => {
console.log('forEach: ', `key: ${k}, value: ${v}`);
});
// forEach: key: Gandalf, value: [email protected]
// forEach: key: Tyrion, value: [email protected]
复制代码
散列表(又称哈希表、HashTable、HashMap)
定义
散列表(也叫HashTable类 或 HashMap类)，是字典的一种散列表实现方式。JavaScript的对象(Object)，本质上是键值对的集合(Hash结构)，但是传统上只能用字符串当作键，因此ES2015 带来了Map类和Map类的弱化版本WeakMap类。
散列表在实际中应用的场景也很多:
因为它是字典的一种实现，所以可以用作关联数组
JavaScript的对象(Object)，本质上是键值对的集合(Hash结构)，JavaScript 语言内部就是使用散列表来表示每个对象。
在数据库（如 MySQL、Microsoft SQL Server、 Oracle，等等）中进行索引，散列表可以用来保存键和对表中记录的引用
为什么要用散列表
散列表，是根据键值对而直接进行访问的数据结构。
也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射过程中使用的算法叫做散列算法，存放记录的数组叫做散列表。
散列表几个基本概念
装填因子
装填因子：a=n/m 其中n 为key个数，m为散列表的大小。
装填因子表示散列表的填充程度。
装填因子越大，填满的元素越多，空间利用率高，发生散列冲突的可能性更大了。
装填因子越小，填满的元素越少，发生散列冲突的可能性更小，但是空间利用率低了。
在冲突的可能性和空间的利用率之间需要寻找合适的平衡。
散列算法
散列算法的作用是尽可能快地在数据结构中找到一个值。散列算法是用于将一个数据转换为固定长度数值的函数。
笔记中用到的两个散列算法:
/**
* 散列函数 loseloseHashCode
* 将传入的key转换为hash值并返回，如果传入的key已经是hash值，则直接返回
* @returns {number} 返回hash值
*/
loseloseHashCode = (key) => {
if (typeof key === 'number') { // 先检验 key 是否是一个数字
return key; // 是，我们直接将其返回
}
// key不是一个数字
const tableKey = this.toStrFn(key); // 将 key 转化为字符串
let hash = 0; // 配置一个 hash 变量来存储hash总和
for (let i = 0; i < tableKey.length; i++) { // 遍历 key
hash += tableKey.charCodeAt(i); // 从 ASCII表中查到的每个字符对应的 ASCII 值加到 hash 变量中
}
return hash % 37; // 为了得到比较小的数值，我们会使用 hash 值和一个任意数做除法的余数（%）(可以避免操作数超过数值变量最大表示范围的风险)
}
/**
* 散列函数 djb2HashCode
*/
djb2HashCode(key) {
const tableKey = this.toStrFn(key); // 将键转化为字符串
let hash = 5381; // 初始的hash变量，数值为质数(大多数实现都使用 5381)
for (let i = 0; i < tableKey.length; i++) { // 然后迭代参数 key
hash = (hash * 33) + tableKey.charCodeAt(i); // 将 hash 与 33 相乘（用作一个幻数-[幻数在编程中指直接使用的常数]),并和当前迭代到的字符的 ASCII 码值相加
}
return hash % 1013; // 最后，将使用相加的和与另一个随机质数相除的余数进行返回
// 这并不是最好的散列函数，但这是最受社区推崇的散列函数之一。
// 也有一些为数字键值准备的散列函数，可以在 http://t.cn/Eqg1yb0 找到一系列的实现。
}
复制代码
散列冲突
多个元素通过散列算法计算得到的散列值相同，此时保存重复散列值的数据，会覆盖掉老的相同散列值的数据。使用一个数据结构来保存数据的目的显然不是丢失这些数据，而是通过某种方法将它们全部 保存起来。因此，常规处理散列冲突有几种方法：
分离链接
线性探查
双散列法
后续会介绍前两种散列冲突解决方法
基础散列表
代码实现
/**
* 在集合(Set)中，我们的关注点放在集合(Set)的每个值本身，集合(Set)以[值，值]的形式存储元素，而在字典中，是用[键，值]对的形式存储数据。字典也称作映射，符号表或者关联数组。
散列表(也叫HashTable类 或 HashMap类)，是字典的一种散列表实现方式。JavaScript的对象(Object)，本质上是键值对的集合(Hash结构)，但是传统上只能用字符串当作键，因此ES2015 带来了Map类和Map类的弱化版本WeakMap类。
集合、散列表与字典都是用来存储唯一值(不重复的值)的数据结构。
*/
/**
* 散列表(Dictionary 类的一种散列表实现方式)的理想状态下是将字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象）
* 此方法把传入的键名转换为字符串
* @param {*} item 传入的键名
* @returns {string}
*/
export function defaultToString(item) {
if (item === null) { // 如果key是null
return 'NULL'; // 以NULL字符串返回
}
if (item === undefined) { // 如果key是undefined
return 'UNDEFINED'; // 以UNDEFINED字符串返回
}
if (typeof item === 'string' || item instanceof String) { // 如果是一个字符串，那么直接返回它
return `${item}`;
}
return item.toString(); // 否则将其转换为字符串返回
}
/**
* ValuePair 类
* 为了保存信息的需要，我们同样要保存原始的 key 和 value
* @class ValuePair
*/
export class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}
/**
*
* 将key和value通过字符串的方式返回出来
* @returns {string}
* @memberof ValuePair
*/
toString() {
return `[#${this.key}: ${this.value}]`;
}
}
// 基于 ES2015 的 Map 类来实现 Dictionary 类
export class Dictionary {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn; // 也可以传入自定义的函数来指定如何将 key 转化为字符串
this.table = {}; // 用一个Object的实例存储字典中的元素
}
/**
* 散列函数
* 将传入的key转换为hash值并返回，如果传入的key已经是hash值，则直接返回
* @returns {number} 返回hash值
*/
loseloseHashCode = (key) => {
if (typeof key === 'number') { // 先检验 key 是否是一个数字
return key; // 是，我们直接将其返回
}
// key不是一个数字
const tableKey = this.toStrFn(key); // 将 key 转化为字符串
let hash = 0; // 配置一个 hash 变量来存储hash总和
for (let i = 0; i < tableKey.length; i++) { // 遍历 key
hash += tableKey.charCodeAt(i); // 从 ASCII表中查到的每个字符对应的 ASCII 值加到 hash 变量中
}
return hash % 37; // 为了得到比较小的数值，我们会使用 hash 值和一个任意数做除法的余数（%）(可以避免操作数超过数值变量最大表示范围的风险)
}
/**
* 转换hash码
* 将传入的key经过loseloseHashCode方法转换为hash码返回
* @returns {number} 返回hash值
*/
hashCode(key) {
return this.loseloseHashCode(key);
}
/**
* 向散列表增加一个新的项（也能更新散列表）
* put 方法和 Dictionary 类中的 set 方法逻辑相似。我们也可以将其命名为 set，但是大多数的编程语言会在 HashTable 数据结构中使用 put 方法，因此我们遵循相同的命名方式。
* @param {string} key 需要添加新项的key
* @param {*} value 需要添加新项的value
* @return {boolean} 如果添加成功返回true，否则返回false
*/
put(key, value) {
if (key != null && value != null) { // 检验 key 和 value 是否合法
const position = this.hashCode(key); // 获取key值对应的hash码
this.table[position] = new ValuePair(key, value); // 创建一个新的键值对并将其赋值给 table 对象上的 key属性（position）
return true; // 添加/覆盖成功返回true
}
// 如果不合法就返回 false
return false;
}
/**
*返回根据键值检索到的特定的值
* @param {*} key 需要获取的key值
* @returns {*} 返回获取到的valuePair或者undefined
*/
get(key) {
const valuePair = this.table[this.hashCode(key)]; // 根据指定key值获取对应的hashCode，再根据hashCode获取指定key值的valuePair
return valuePair === null ? undefined : valuePair.value; // 如果 valuePair 对象存在，将返回该值，否则将返回一个 undefined 值
}
/**
*
*根据键值从散列表中移除值
* @param {*} key 要删除的key值
* @returns {boolean} 是否删除成功
*/
remove(key) {
// 要从 HashTable 中移除一个值，首先需要知道值所在的位置
const hash = this.hashCode(key); // 使用 hashCode 函数来获取 hash
const valuePair = this.table[hash]; // 在 hash 的位置获取到 valuePair
if (valuePair !== null) { // 如果 valuePair不是 null 或 undefined
delete this.table[hash]; // 在table对象删除指定的hash
return true; // 成功返回true
}
// 否则返回 false
return false;
}
/**
* 获取整个散列表
* @returns
*/
getTable() {
return this.table;
}
/**
*在 size 等于零的时候返回 true，否则返回 false
* @returns
*/
isEmpty() {
return this.size() === 0;
}
/**
*
*返回字典所包含值的数量。与数组的 length 属性类似
* @returns {Number}
*/
size() {
return Object.keys(this.table).length;
}
/**
* 删除该字典中的所有值
*/
clear() {
this.table = {};
}
/**
* 以字符串的方式输出字典的值
* @returns {string}
*/
toString() {
if (this.isEmpty()) { // 检验字典是否为空
return ''; // 如果为空，就返回 空字符串
}
// 如果字典不为空
const keys = Object.keys(this.table); // 获取散列表的所有key
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;
}
}
复制代码
使用基础散列表实例
创建一个散列表，传入三个键值对
const hash = new HashTable();
hash.put('Gandalf', '[email protected]');
hash.put('John', '[email protected]');
hash.put('Tyrion', '[email protected]');
console.log(hash.hashCode('Gandalf') + ' - Gandalf');
console.log(hash.hashCode('John') + ' - John');
console.log(hash.hashCode('Tyrion') + ' - Tyrion');
/**
19 - Gandalf
29 - John
16 - Tyrion
*/
复制代码
测试散列表的部分方法
console.log(hash.get('Gandalf')); // [email protected]
console.log(hash.get('Loiane')); // undefined
hash.remove('Gandalf');
console.log(hash.get('Gandalf')); // undefined
复制代码
测试散列表的散列冲突
/**
* 有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。例如，我们看看下面的代码会得到怎样的输出结果。
*/
const hash1 = new HashTable();
hash.put('Ygritte', '[email protected]');
hash.put('Jonathan', '[email protected]');
hash.put('Jamie', '[email protected]');
hash.put('Jack', '[email protected]');
hash.put('Jasmine', '[email protected]');
hash.put('Jake', '[email protected]');
hash.put('Nathan', '[email protected]');
hash.put('Athelstan', '[email protected]');
hash.put('Sue', '[email protected]');
hash.put('Aethelwulf', '[email protected]');
hash.put('Sargeras', '[email protected]');
/**
4 - Ygritte
5 - Jonathan
5 - Jamie
7 - Jack
8 - Jasmine
9 - Jake
10 - Nathan
7 - Athelstan
5 - Sue
5 - Aethelwulf
10 - Sargeras
*/
// 实际输出
console.log(hashTable.toString())
/**
{4 => [#Ygritte: [email protected]]}
{5 => [#Aethelwulf: [email protected]]}
{7 => [#Athelstan: [email protected]]}
{8 => [#Jasmine: [email protected]]}
{9 => [#Jake: [email protected]]}
{10 => [#Sargeras: [email protected]]}
*/
/**
Jonathan、Jamie、Sue 和 Aethelwulf 有相同的散列值，也就是 5。由于 Aethelwulf是最后一个被添加的，它将是在 HashTable 实例中占据位置 5 的元素。首先 Jonathan 会占据这个位置，然后 Jamie 会覆盖它，Sue 会再次覆盖，最后 Aethelwulf 会再覆盖一次。这对于其他发生冲突的元素来说也是一样的。
使用一个数据结构来保存数据的目的显然不是丢失这些数据，而是通过某种方法将它们全部保存起来。因此，当这种情况发生的时候就要去解决。处理冲突有几种方法：分离链接、线性探查和双散列法。
*/
复制代码
使用分离链接法解决散列冲突
介绍
为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决散列冲突的最简单的方法，但是在 散列表 实例之外还需要占用额外的存储空间。
代码实现
import {
LinkedList
} from '/LinkedList/app.js';
/**
* 在集合(Set)中，我们的关注点放在集合(Set)的每个值本身，集合(Set)以[值，值]的形式存储元素，而在字典中，是用[键，值]对的形式存储数据。字典也称作映射，符号表或者关联数组。
散列表(也叫HashTable类 或 HashMap类)，是字典的一种散列表实现方式。JavaScript的对象(Object)，本质上是键值对的集合(Hash结构)，但是传统上只能用字符串当作键，因此ES2015 带来了Map类和Map类的弱化版本WeakMap类。
集合、散列表与字典都是用来存储唯一值(不重复的值)的数据结构。
*/
/**
* 散列表(Dictionary 类的一种散列表实现方式)的理想状态下是将字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象）
* 此方法把传入的键名转换为字符串
* @param {*} item 传入的键名
* @returns {string}
*/
export function defaultToString(item) {
if (item === null) { // 如果key是null
return 'NULL'; // 以NULL字符串返回
}
if (item === undefined) { // 如果key是undefined
return 'UNDEFINED'; // 以UNDEFINED字符串返回
}
if (typeof item === 'string' || item instanceof String) { // 如果是一个字符串，那么直接返回它
return `${item}`;
}
return item.toString(); // 否则将其转换为字符串返回
}
/**
* ValuePair 类
* 为了保存信息的需要，我们同样要保存原始的 key 和 value
* @class ValuePair
*/
export class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}
/**
*
* 将key和value通过字符串的方式返回出来
* @returns {string}
* @memberof ValuePair
*/
toString() {
return `[#${this.key}: ${this.value}]`;
}
}
// 基于 ES2015 的 Map 类来实现 Dictionary 类
export class HashTableSeparateChaining {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn; // 也可以传入自定义的函数来指定如何将 key 转化为字符串
this.table = {}; // 用一个Object的实例存储字典中的元素
}
/**
* 散列函数
* 将传入的key转换为hash值并返回，如果传入的key已经是hash值，则直接返回
* @returns {number} 返回hash值
*/
loseloseHashCode = (key) => {
if (typeof key === 'number') { // 先检验 key 是否是一个数字
return key; // 是，我们直接将其返回
}
// key不是一个数字
const tableKey = this.toStrFn(key); // 将 key 转化为字符串
let hash = 0; // 配置一个 hash 变量来存储hash总和
for (let i = 0; i < tableKey.length; i++) { // 遍历 key
hash += tableKey.charCodeAt(i); // 从 ASCII表中查到的每个字符对应的 ASCII 值加到 hash 变量中
}
return hash % 37; // 为了得到比较小的数值，我们会使用 hash 值和一个任意数做除法的余数（%）(可以避免操作数超过数值变量最大表示范围的风险)
}
/**
* 转换hash码
* 将传入的key经过loseloseHashCode方法转换为hash码返回
* @returns {number} 返回hash值
*/
hashCode(key) {
return this.loseloseHashCode(key);
}
/**
* 向散列表增加一个新的项
* put 方法和 Dictionary 类中的 set 方法逻辑相似。我们也可以将其命名为 set，但是大多数的编程语言会在 HashTable 数据结构中使用 put 方法，因此我们遵循相同的命名方式。
* @param {string} key 需要添加新项的key
* @param {*} value 需要添加新项的value
* @return {boolean} 如果添加成功返回true，否则返回false
*/
put(key, value) {
if (key != null && value != null) { // 检验 key 和 value 是否合法
const position = this.hashCode(key); // 获取key值对应的hash码
if (this.table[position] === null) { // 验证要加入新元素的位置是否已经被占据
this.table[position] = new LinkedList(); //如果是第一次向该位置加入元素，我们会在该位置上初始化一个链表的实例
}
this.table[position].push(new ValuePair(key, value)); //向链表添加一个ValuePair 实例（键和值）
return true; // 成功返回true
}
// 如果不合法就返回 false
return false;
}
/**
*返回根据键值检索到的特定的值
* @param {*} key 需要获取的key值
* @returns {*} 返回获取到的valuePair或者undefined
*/
get(key) {
const position = this.hashCode(key); // 获取key值对应的hash码
const linkedList = this.table[position]; // 获取key值position对应的链表实例
// 如果对应的链表实例存在，而且不是空的链表
if (linkedList !== null && !linkedList.isEmpty()) {
let current = linkedList.getHead(); // 获取链表表头的引用
while (current != null) { // 从链表的头部迭代到尾部，直到最末尾，current.next将会是 null，结束迭代
if (current.element.key === key) { //element 属性保存着 ValuePair 的实例，如果此时的key值跟传入的key值相同
return current.element.value; // 则找到需要检索的值，返回value的值
}
// 如果不相同，就继续迭代链表，访问下一个节点
current = current.next;
}
}
// 如果没有，则返回一个 undefined 表示在 HashTable 实例中没有找到这个值
return undefined;
/**
* 另一个实现算法的思路如下：除了在 get 方法内部搜索 key，还可以在 put 方法中实例化LinkedList，向 LinkedList 的构造函数传入自定义的 equalsFn，只用它来比较元素的 key属性（即 ValuePair 实例）。我们要记住，默认情况下，LinkedList 会使用===运算符来比较它的元素实例，也就是说会比较 ValuePair 实例的引用。这种情况下，在 get 方法中，我们要使用 indexOf 方法来搜索目标 key，如果返回大于或等于零的位置，则说明元素存在于链表中。有了该位置，我们就可以使用 getElementAt 方法来从链表中获取 ValuePair 实例。
*/
}
/**
*
*根据键值从散列表中移除值
* @param {*} key 要删除的key值
* @returns {boolean} 是否删除成功
*/
remove(key) {
const position = this.hashCode(key); // 获取key值对应的hash码
const linkedList = this.table[position]; // 获取key值position对应的链表实例
// 如果对应的链表实例存在，而且不是空的链表
if (linkedList != null && !linkedList.isEmpty()) {
let current = linkedList.getHead(); // 获取链表表头的引用
while (current != null) { // 从链表的头部迭代到尾部，直到最末尾，current.next将会是 null，结束迭代
if (current.element.key === key) { //element 属性保存着 ValuePair 的实例，如果此时的key值跟传入的key值相同
linkedList.remove(current.element); // 则使用 remove 方法将其从链表中移除
if (linkedList.isEmpty()) { // 如果链表为空了(链表中不再有任何元素了)
delete this.table[position]; // 使用 delete 运算符将散列表的该位置删除,这样搜索一个元素的时候，就可以跳过这个位置了
}
return true; // 返回 true 表示该元素已经被移除
}
current = current.next; // 如果不是我们要找的元素，那么和 get 方法中一样继续迭代下一个元素
}
}
return false; // 返回 false表示该元素在散列表中不存在
}
/**
* 获取整个散列表
* @returns
*/
getTable() {
return this.table;
}
/**
*在 size 等于零的时候返回 true，否则返回 false
* @returns
*/
isEmpty() {
return this.size() === 0;
}
/**
*
*返回字典所包含值的数量。与数组的 length 属性类似
* @returns {Number}
*/
size() {
return Object.keys(this.table).length;
}
/**
* 删除该字典中的所有值
*/
clear() {
this.table = {};
}
/**
* 以字符串的方式输出字典的值
* @returns {string}
*/
toString() {
if (this.isEmpty()) { // 检验字典是否为空
return ''; // 如果为空，就返回 空字符串
}
// 如果字典不为空
const keys = Object.keys(this.table); // 获取散列表的所有key
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;
}
}
复制代码
使用 线性探查法解决散列冲突
介绍
线性探查之所以称作线性，是因为它处理冲突的方法是将元素直接存储到表中，而不是在单独的数据结构中。当想向表中某个位置添加一个新元素的时候，如果散列值的位置已经被占据了，就尝试寻找散列值的下一个位置，如果仍然被占据，则再往下找下一个位置，以此类推，直到找到空闲位置，填充新值。
使用线性探查移除元素会导致散列表出现异常，所以需要对移除的元素作处理，通常使用的方法为以下两种:
软删除
删除后检查并挪动删除副作用影响的键值对元素
线性探查(软删除法)
介绍
使用一个删除标记来标记键值对被删除了，而不是真的从散列表中删除它，但是会随着删除次数的增加，散列表冗余了许多无用的软删除标记，逐渐降低散列表的效率。
代码实现
/**
* 在集合(Set)中，我们的关注点放在集合(Set)的每个值本身，集合(Set)以[值，值]的形式存储元素，而在字典中，是用[键，值]对的形式存储数据。字典也称作映射，符号表或者关联数组。
散列表(也叫HashTable类 或 HashMap类)，是字典的一种散列表实现方式。JavaScript的对象(Object)，本质上是键值对的集合(Hash结构)，但是传统上只能用字符串当作键，因此ES2015 带来了Map类和Map类的弱化版本WeakMap类。
集合、散列表与字典都是用来存储唯一值(不重复的值)的数据结构。
*/
/**
* 散列表(Dictionary 类的一种散列表实现方式)的理想状态下是将字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象）
* 此方法把传入的键名转换为字符串
* @param {*} item 传入的键名
* @returns {string}
*/
export function defaultToString(item) {
if (item === null) { // 如果key是null
return 'NULL'; // 以NULL字符串返回
}
if (item === undefined) { // 如果key是undefined
return 'UNDEFINED'; // 以UNDEFINED字符串返回
}
if (typeof item === 'string' || item instanceof String) { // 如果是一个字符串，那么直接返回它
return `${item}`;
}
return item.toString(); // 否则将其转换为字符串返回
}
/**
* ValuePair 类
* 为了保存信息的需要，我们同样要保存原始的 key 和 value
* @class ValuePair
*/
export class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}
/**
*
* 将key和value通过字符串的方式返回出来
* @returns {string}
* @memberof ValuePair
*/
toString() {
return `[#${this.key}: ${this.value}]`;
}
}
// 基于 ES2015 的 Map 类来实现 Dictionary 类
export class HashTableLinearProbingLazy {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn; // 也可以传入自定义的函数来指定如何将 key 转化为字符串
this.table = {}; // 用一个Object的实例存储字典中的元素
}
/**
* 散列函数
* 将传入的key转换为hash值并返回，如果传入的key已经是hash值，则直接返回
* @returns {number} 返回hash值
*/
loseloseHashCode = (key) => {
if (typeof key === 'number') { // 先检验 key 是否是一个数字
return key; // 是，我们直接将其返回
}
// key不是一个数字
const tableKey = this.toStrFn(key); // 将 key 转化为字符串
let hash = 0; // 配置一个 hash 变量来存储hash总和
for (let i = 0; i < tableKey.length; i++) { // 遍历 key
hash += tableKey.charCodeAt(i); // 从 ASCII表中查到的每个字符对应的 ASCII 值加到 hash 变量中
}
return hash % 37; // 为了得到比较小的数值，我们会使用 hash 值和一个任意数做除法的余数（%）(可以避免操作数超过数值变量最大表示范围的风险)
}
/**
* 散列函数 djb2HashCode
*/
djb2HashCode(key) {
const tableKey = this.toStrFn(key); // 将键转化为字符串
let hash = 5381; // 初始的hash变量，数值为质数(大多数实现都使用 5381)
for (let i = 0; i < tableKey.length; i++) { // 然后迭代参数 key
hash = (hash * 33) + tableKey.charCodeAt(i); // 将 hash 与 33 相乘（用作一个幻数-[幻数在编程中指直接使用的常数]),并和当前迭代到的字符的 ASCII 码值相加
}
return hash % 1013; // 最后，将使用相加的和与另一个随机质数相除的余数进行返回
// 这并不是最好的散列函数，但这是最受社区推崇的散列函数之一。
// 也有一些为数字键值准备的散列函数，可以在 http://t.cn/Eqg1yb0 找到一系列的实现。
}
/**
* 转换hash码
* 将传入的key经过loseloseHashCode方法转换为hash码返回
* @returns {number} 返回hash值
*/
hashCode(key) {
return this.loseloseHashCode(key);
}
/**
* 向散列表增加一个新的项
* put 方法和 Dictionary 类中的 set 方法逻辑相似。我们也可以将其命名为 set，但是大多数的编程语言会在 HashTable 数据结构中使用 put 方法，因此我们遵循相同的命名方式。
* @param {string} key 需要添加新项的key
* @param {*} value 需要添加新项的value
* @return {boolean} 如果添加成功返回true，否则返回false
*/
put(key, value) {
if (key != null && value != null) { // 检验 key 和 value 是否合法
const position = this.hashCode(key); // 获取key值对应的hash码
if (this.table[position] == null || (this.table[position] != null && this.table[position].isDeleted)) {
// 要加入新元素的位置没有被被占据或者这个位置的元素是已删除状态
this.table[position] = new ValuePair(key, value); //在这个位置添加新元素
} else {
// 如果该位置已经被占据了，需要找到下一个没有被占据的位置（position 的值是 undefined或 null）
let index = position + 1; // 当前位置的下一个位置
while (this.table[index] !== null && !this.table[position].isDeleted) { // 验证该位置是否被占据，或者是否被删除
index++; // 如果被占据了而且值不是被删除的状态，继续将 index 递增,直到找到一个没有被占据的位置
}
// 找到合适的位置后，将值分配到该位置
this.table[index] = new ValuePair(key, value);
}
return true; // 成功返回true
}
// 如果不合法就返回 false
return false;
}
/**
*返回根据键值检索到的特定的值
* @param {*} key 需要获取的key值
* @returns {*} 返回获取到的valuePair或者undefined
*/
get(key) {
const position = this.hashCode(key); // 获取key值对应的hash码
if (this.table[position] != null) { // 如果这个键存在
if (this.table[position].key === key && !this.table[position].isDeleted) { // 当前位置的key和传入的key相等并且未被删除
return this.table[position].value; // 则直接返回这个位置的散列表项
}
let index = position + 1; //如果不是，就在散列表的下一个位置继续查找
while (this.table[index] != null && (this.table[index].key !== key || this.table[index].isDeleted)) { // 会按位置递增的顺序查找散列表上的元素直到找到我们要找的元素或者一个空位置
if (this.table[index].key === key && this.table[index].isDeleted) { // 如果找到的key跟我们传入的key符合，但是状态是已删除
return undefined; // 说明要查找的值在散列表中已被删除，因此可以返回 undefined
}
index++; // 不符合继续递增
}
// 当从 while 循环跳出的时候，验证元素的键是否是我们要找的键
if (
this.table[index] != null
&& this.table[index].key === key
&& !this.table[index].isDeleted
) {
return this.table[position].value; // 如果是，就返回它的值
}
}
// 如果这个键不存在，说明要查找的值不在散列表中，因此可以返回 undefined
return undefined;
}
/**
*
*根据键值从散列表中移除值
* @param {*} key 要删除的key值
* @returns {boolean} 是否删除成功
*/
remove(key) {
const position = this.hashCode(key); // 获取key值对应的hash码
if (this.table[position] != null) { // 如果这个键存在
if (this.table[position].key === key && !this.table[position].isDeleted) { // 当前位置的key和传入的key相等并且未被删除
this.table[position].isDeleted = true; // 则软删除这个位置的散列表项
return true; // 返回删除成功
}
let index = position + 1; //如果不是，就在散列表的下一个位置继续查找
while (
this.table[index] != null
&& (this.table[index].key !== key || this.table[index].isDeleted)
) { // 会按位置递增的顺序查找散列表上的元素直到找到我们要找的元素或者一个空位置
index++; // 不符合继续递增
}
// 当从 while 循环跳出的时候，验证元素的键是否是我们要找的键
if (
this.table[index] != null
&& this.table[index].key === key
&& !this.table[index].isDeleted
) {
this.table[position].isDeleted = true; // 则软删除这个位置的散列表项
return true; // 返回删除成功
}
}
return false;
}
/**
*
*
* @param {*} key 被删除的 key
* @param {*} removedPosition 该 key 被删除的位置
*/
verifyRemoveSideEffect(key, removedPosition) {
const hash = this.hashCode(key); //获取被删除的 key 的 hash 值
let index = removedPosition + 1; //从下一个位置开始迭代散列表
while (this.table[index] != null) { //直到找到一个空位置,结束循环(此时所有符合条件的元素都已经被处理到合适的位置上，不需要进行移动)
const posHash = this.hashCode(this.table[index].key); // 计算当前位置上元素的 hash 值
if (posHash ${this.table[keys[i]].toString()}}`;
}
// 以字符串的方式输出字典的值
return objString;
}
}
复制代码
线性探查(挪动删除副作用影响的键值对元素)
介绍
真正的把元素从散列表中删除，随后对它后续的所有元素进行判断是否需要移动到删除后空闲的位置，随着散列表的大小增加，存在跟数组类似的挪动元素成本。
代码实现
import {
LinkedList
} from '/LinkedList/app.js';
/**
* 在集合(Set)中，我们的关注点放在集合(Set)的每个值本身，集合(Set)以[值，值]的形式存储元素，而在字典中，是用[键，值]对的形式存储数据。字典也称作映射，符号表或者关联数组。
散列表(也叫HashTable类 或 HashMap类)，是字典的一种散列表实现方式。JavaScript的对象(Object)，本质上是键值对的集合(Hash结构)，但是传统上只能用字符串当作键，因此ES2015 带来了Map类和Map类的弱化版本WeakMap类。
集合、散列表与字典都是用来存储唯一值(不重复的值)的数据结构。
*/
/**
* 散列表(Dictionary 类的一种散列表实现方式)的理想状态下是将字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象）
* 此方法把传入的键名转换为字符串
* @param {*} item 传入的键名
* @returns {string}
*/
export function defaultToString(item) {
if (item === null) { // 如果key是null
return 'NULL'; // 以NULL字符串返回
}
if (item === undefined) { // 如果key是undefined
return 'UNDEFINED'; // 以UNDEFINED字符串返回
}
if (typeof item === 'string' || item instanceof String) { // 如果是一个字符串，那么直接返回它
return `${item}`;
}
return item.toString(); // 否则将其转换为字符串返回
}
/**
* ValuePair 类
* 为了保存信息的需要，我们同样要保存原始的 key 和 value
* @class ValuePair
*/
export class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}
/**
*
* 将key和value通过字符串的方式返回出来
* @returns {string}
* @memberof ValuePair
*/
toString() {
return `[#${this.key}: ${this.value}]`;
}
}
// 基于 ES2015 的 Map 类来实现 Dictionary 类
export class HashTableSeparateChaining {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn; // 也可以传入自定义的函数来指定如何将 key 转化为字符串
this.table = {}; // 用一个Object的实例存储字典中的元素
}
/**
* 散列函数
* 将传入的key转换为hash值并返回，如果传入的key已经是hash值，则直接返回
* @returns {number} 返回hash值
*/
loseloseHashCode = (key) => {
if (typeof key === 'number') { // 先检验 key 是否是一个数字
return key; // 是，我们直接将其返回
}
// key不是一个数字
const tableKey = this.toStrFn(key); // 将 key 转化为字符串
let hash = 0; // 配置一个 hash 变量来存储hash总和
for (let i = 0; i < tableKey.length; i++) { // 遍历 key
hash += tableKey.charCodeAt(i); // 从 ASCII表中查到的每个字符对应的 ASCII 值加到 hash 变量中
}
return hash % 37; // 为了得到比较小的数值，我们会使用 hash 值和一个任意数做除法的余数（%）(可以避免操作数超过数值变量最大表示范围的风险)
}
/**
* 转换hash码
* 将传入的key经过loseloseHashCode方法转换为hash码返回
* @returns {number} 返回hash值
*/
hashCode(key) {
return this.loseloseHashCode(key);
}
/**
* 向散列表增加一个新的项
* put 方法和 Dictionary 类中的 set 方法逻辑相似。我们也可以将其命名为 set，但是大多数的编程语言会在 HashTable 数据结构中使用 put 方法，因此我们遵循相同的命名方式。
* @param {string} key 需要添加新项的key
* @param {*} value 需要添加新项的value
* @return {boolean} 如果添加成功返回true，否则返回false
*/
put(key, value) {
if (key != null && value != null) { // 检验 key 和 value 是否合法
const position = this.hashCode(key); // 获取key值对应的hash码
if (this.table[position] === null) { // 验证要加入新元素的位置是否已经被占据
this.table[position] = new LinkedList(); //如果是第一次向该位置加入元素，我们会在该位置上初始化一个链表的实例
}
this.table[position].push(new ValuePair(key, value)); //向链表添加一个ValuePair 实例（键和值）
return true; // 成功返回true
}
// 如果不合法就返回 false
return false;
}
/**
*返回根据键值检索到的特定的值
* @param {*} key 需要获取的key值
* @returns {*} 返回获取到的valuePair或者undefined
*/
get(key) {
const position = this.hashCode(key); // 获取key值对应的hash码
const linkedList = this.table[position]; // 获取key值position对应的链表实例
// 如果对应的链表实例存在，而且不是空的链表
if (linkedList !== null && !linkedList.isEmpty()) {
let current = linkedList.getHead(); // 获取链表表头的引用
while (current != null) { // 从链表的头部迭代到尾部，直到最末尾，current.next将会是 null，结束迭代
if (current.element.key === key) { //element 属性保存着 ValuePair 的实例，如果此时的key值跟传入的key值相同
return current.element.value; // 则找到需要检索的值，返回value的值
}
// 如果不相同，就继续迭代链表，访问下一个节点
current = current.next;
}
}
// 如果没有，则返回一个 undefined 表示在 HashTable 实例中没有找到这个值
return undefined;
/**
* 另一个实现算法的思路如下：除了在 get 方法内部搜索 key，还可以在 put 方法中实例化LinkedList，向 LinkedList 的构造函数传入自定义的 equalsFn，只用它来比较元素的 key属性（即 ValuePair 实例）。我们要记住，默认情况下，LinkedList 会使用===运算符来比较它的元素实例，也就是说会比较 ValuePair 实例的引用。这种情况下，在 get 方法中，我们要使用 indexOf 方法来搜索目标 key，如果返回大于或等于零的位置，则说明元素存在于链表中。有了该位置，我们就可以使用 getElementAt 方法来从链表中获取 ValuePair 实例。
*/
}
/**
*
*根据键值从散列表中移除值
* @param {*} key 要删除的key值
* @returns {boolean} 是否删除成功
*/
remove(key) {
const position = this.hashCode(key); // 获取key值对应的hash码
const linkedList = this.table[position]; // 获取key值position对应的链表实例
// 如果对应的链表实例存在，而且不是空的链表
if (linkedList != null && !linkedList.isEmpty()) {
let current = linkedList.getHead(); // 获取链表表头的引用
while (current != null) { // 从链表的头部迭代到尾部，直到最末尾，current.next将会是 null，结束迭代
if (current.element.key === key) { //element 属性保存着 ValuePair 的实例，如果此时的key值跟传入的key值相同
linkedList.remove(current.element); // 则使用 remove 方法将其从链表中移除
if (linkedList.isEmpty()) { // 如果链表为空了(链表中不再有任何元素了)
delete this.table[position]; // 使用 delete 运算符将散列表的该位置删除,这样搜索一个元素的时候，就可以跳过这个位置了
}
return true; // 返回 true 表示该元素已经被移除
}
current = current.next; // 如果不是我们要找的元素，那么和 get 方法中一样继续迭代下一个元素
}
}
return false; // 返回 false表示该元素在散列表中不存在
}
/**
* 获取整个散列表
* @returns
*/
getTable() {
return this.table;
}
/**
*在 size 等于零的时候返回 true，否则返回 false
* @returns
*/
isEmpty() {
return this.size() === 0;
}
/**
*
*返回字典所包含值的数量。与数组的 length 属性类似
* @returns {Number}
*/
size() {
return Object.keys(this.table).length;
}
/**
* 删除该字典中的所有值
*/
clear() {
this.table = {};
}
/**
* 以字符串的方式输出字典的值
* @returns {string}
*/
toString() {
if (this.isEmpty()) { // 检验字典是否为空
return ''; // 如果为空，就返回 空字符串
}
// 如果字典不为空
const keys = Object.keys(this.table); // 获取散列表的所有key
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;
}
}
复制代码
ES6 Map类
ECMAScript 2015 新增了 Map 类。可以基于 ES2015 的 Map 类开发我们的 Dictionary 类。
const map = new Map();
map.set('Gandalf', '[email protected]');
map.set('John', '[email protected]');
map.set('Tyrion', '[email protected]');
console.log(map.has('Gandalf')); // true
console.log(map.size); // 3
console.log(map.keys()); // 输出{"Gandalf", "John", "Tyrion"}
console.log(map.values()); // 输出{"[email protected]", "[email protected]",
"[email protected]"}
console.log(map.get('Tyrion')); // [email protected]
map.delete('John'); // 删除map中的元素
map.clear(); //重置 map 数据结构，这跟我们在 Dictionary 类里实现的一样。
复制代码
跟先前开发的字典类，不同点在于ES2015 的 Map 类的 values 方法和 keys 方法都返回 Iterator（第 3 章提到过），而不是值或键构成的数组。
ES6 WeakMap 类和 WeakSet 类
WeakSet 和 WeakMap 是 Set 和 Map 的弱化版本
主要区别在于：
WeakSet 或 WeakMap 类没有 entries、keys 和 values 等方法；
只能用对象作为键。
const map = new WeakMap();
const ob1 = { name: 'Gandalf' };
const ob2 = { name: 'John' };
const ob3 = { name: 'Tyrion' };
map.set(ob1, '[email protected]');
map.set(ob2, '[email protected]');
map.set(ob3, '[email protected]');
console.log(map.has(ob1)); // true
console.log(map.get(ob3)); // [email protected]
map.delete(ob2);
复制代码
由于WeakSet 或 WeakMap 类没有强引用的键，能够提升JavaScript垃圾回收的性能，并且因为没有迭代器方法，在不知道键的情况下，无法取出值。
（可以使用WeakMap 类封装 ES6 类的私有属性）
|