前言
字典(Map)与散列表(HashMap)是一种采用[键(key)，值(value)]对的形式来存储数据的数据结构。
本文将详细讲解字典与散列表的实现思路并使用TypeScript将其实现，欢迎各位感兴趣的前端开发者阅读本文。
实现思路
字典与散列表存储数据的方式是键值对的形式来存储，因此我们可以使用JavaScript中的对象来实现。
字典的实现
字典通过键值对的形式来存储数据，它的键是字符串类型，调用者传的key是什么，它的键就是什么。
一个完整的字典类需要具备：判断一个键是否在字典中、向字典中添加元素、根据key移除字典中存的元素、根据key查找字典中的元素、获取字典中存储的所有元素等方法，接下来我们来分析下这些方法的实现思路。
- 向字典中添加元素（set）
- set方法接收两个参数：key & value
- 判断参数的有效性，key & value不为null | undefined时向字典中添加元素，否则直接返回false
- 参数有效时，将参数key转为字符串
- 将转换为字符串的key作为字典中的key，将key & value放进一个对象中，将这个对象存进转换为字符串的key中。
- 讲过上述操作后，我们就成功的向字典中添加了一个元素，返回true。
- 判断一个键是否在字典中 (hasKey)
- hasKey方法接收一个参数：key
- 由于字典中的数据是以对象的形式存储的，因此我们可以直接将key转为字符串，然后将其作为属性传给字典对象，判断其返回结果是否为 undefined | null就可以知道这个key是否在字典中了。
- 根据key获取字典中存储的value值 (get)
- get方法接收一个参数：key
- 将key转为字符串，将其作为属性传给字典对象，用一个变量来接收其返回值。
- 判断返回值是否null | undefined
- 如果返回值不为null | undefined则返回其对象中的value值，否则返回undefined。
- 根据key从字典中移除一个元素 (remove)
- remove方法接收一个参数：key
- 判断目标参数是否存在于字典对象中(调用hasKey方法)，如果不存在直接返回false
- 如果目标元素存在于字典对象中，将key转为字符串，然后将其作为参数传给字典对象，最后调用对象的delete方法删除目标key，返回true
- 获取字典中存储的所有对象 (keyValues)
- keyValues方法不接收任何参数，返回值为一个对象数组
- 首先，声明一个数组变量(valuePairs)用于存储获取到的对象
- 获取字典对象中所有的key
- 遍历获取到的key，将遍历到的key作为参数传给字典对象。
- 将字典对象返回的值放进valuePairs中，将其返回。
- 获取字典中存储的所有key (keys) & 获取字典中存储的所有value (value)
- keys方法接收任何参数
- 声明一个数组变量(keys)用于存储获取到的key | 声明一个数组变量(values)用于存储获取到的value
- 获取字典中存储的所有对象(调用keyValues方法)
- 遍历获取到的对象数组
- 如果想获取key则将当前遍历到的元素的key的值放进keys数组中，否则将values的值放进values数组中。
- 返回 keys | values
- 迭代字典中的数据(forEach)
- forEach方法接收一个回调函数作为参数，其回调函数有两个参数：key & value
- 获取字典中的所有数据
- 遍历获取到的数据，调用回调函数参数将当前遍历到的对象的key和value传给回调函数，用一个变量(result)保存其结果
- 如果result为false时，代表字典中的元素已经遍历完，退出循环
- 获取字典的大小 (size)，调用keyValues方法，返回其数组长度
- 判断字典是否为空 (isEmpty)，调用size方法，判断其是否0，返回判断结果。
- 清空字典(clear)，直接将字典对象初始化为空对象即可
- 将字典中的数据转为字符串 (toString)
- toString方法不接收任何参数
- 如果字典为空，则直接返回空字符串。
- 字典不为空时，获取字典中的所有数据。
- 声明一个变量(objString)，用于存放字典中的每个对象，其初始值为字典对象数组中的0号
- 遍历获取到的对象，将objString与遍历到的数据进行拼接，返回objString。
散列表的实现
散列表又叫哈希表，它是字典的另一种实现，它与字典的不同之处在于其key值的存储。
字典存储元素时会将key转为字符串后再存储元素。
散列表存储元素时会将key进行hash计算，得到hash值后再存储元素。
在查找元素时，字典需要去迭代整个数据结构来查找目标元素，而散列表是通过hash值来存储的，我们只需要对目标元素进行hash值计算，就可以快速找到目标元素的位置。因此，散列表的效率要比字典的效率高。
由于散列表相比哈希表有着许多相同的地方，但是他们存储数据的key不一样，因此我们需要把其用到的方法写到一个接口里，分别根据各自的特点来实现这个接口，接下来我们来分析下哈希表中与字典中不同的地方其方法的实现。
- 向哈希表中添加元素(put)
- 跟字典的实现一样，同样也是接收两个参数，判断其是否有效
- 以key为参数，调用hashCode函数(我们自己来实现)计算其hash值
- 将得到的哈希值作为key存进哈希表中，其值与字典的保持一致
- 计算hash值(hashCode)
- 生成hash值有多种解决方案，本文只介绍两种最常用的。
- 调用需要使用的hash函数(loseloseHashCode | djb2HashCode)
- loseloseHashCode计算哈希值
- 首先，我们判断下key是否为数字，如果为数字不执行直接将其返回，不执行哈希运算
- 将key转为字符串，声明一个变量(hash)用于存储hash值
- 遍历转为字符串的key，调用js的charCodeAt函数求出每个字符的Unicode编码，将获取到的Unicode码与hash相加
- 遍历结束后，为了避免数值过大，将hash值除以37取其余数，返回hash。
- djb2HashCode计算哈希值
- 与loseloseHashCode方法一样，判断key是否为数字，然后将其转为字符串
- 不同的地方是，hash有一个初始值5381
- 遍历转为字符串后的key，获取遍历到的每个字符的Unicode码，将hash值乘以33然后将获取到的Unicode码与其相加
- 遍历结束后，将hash值除以1013取其余数，返回hash
- 根据key获取哈希表中的元素 (get)
- 将key进行hash运算，得到结果，将其作为参数传给哈希表对象，获取目标key存在哈希表中的元素
- 判断其结果是否为 null | undefined，如果是则返回undefined，否则返回其value值
- 根据key移除哈希表中的元素 (remove)
- 将key进行hash运算，判断其哈希值是否在哈希中，如果不在则返回false
- key在哈希表中，将计算出来的hash值当作属性传给哈希表，调用delete方法删除目标元素的key，返回true
- 其他方法与字典中的实现基本一样，唯一不同的地方在于它们对键的处理。
处理哈希表中Hash值冲突
我们在使用HashMap时，如果调用的是loseloseHashCode方法来计算的哈希值，那么其冲突率会很高，此处介绍两种比较常用的处理哈希冲突问题的方法。
分离链接
分离链接法，会为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突最简单的方法，但是它会占用额外的存储空间。
由于分离链接的方法只是改变了HashMap的存储结构，因此我们可以继承HashMap重写与HashMap不同的方法即可。
- 更换私有属性表的变量名，由于分离链接方法其value是一个链表类型而HashMap用的是ValuePair类型，js里没有真正的私有属性，继承时不能改变其表属性的类型，因此我们需要更换变量名(tableLink)
- 重写put方法
- 与HashMap一样，判断其key & value的有效性
- 计算key的hash值，用一个变量（position）存起来
- 将position作为参数传给tableLink判断其是否为null | undefined
- 如果不为null | undefined，在tableLink的position位置创建一个链表
- 在在tableLink的position位置的链表中添加Key & value对象
- 添加成功，返回true
- 重写get方法 (需要从链表中获取元素)
- 计算key的hash值，用一个变量（position）存起来
- 获取position位置存储的链表结构元素
- 如果链表不为空，从链表头部开始遍历，直至当前遍历到的链表元素的key与目标参数的key相同，则返回其对应的value值
- 链表为空则返回undefined
- 重写remove方法 (需要从链表中移除元素)
- 计算key的hash值，用一个变量（position）存起来
- 获取position位置的链表结构元素
- 如果链表不为空，从链表头部开始遍历。
- 当前遍历到的链表元素与目标参数key相同，则将当前链表中的元素从链表中移除。
- 移除后，如果链表为空，直接删除tableLink的position位置元素
- 链表为空则返回undefined
- 重写clear方法，将tableLink指向空对象即可
- 重写keyValues方法，HashMap中存储的是链表，需要从链表中获取存储的对象(valuePair)
- 声明一个数组变量(valuePairs)用于存储获取到的ValuePair对象
- 获取tableLink中的所有key，将其转为int类型后，用一个变量存起来(keys)
- 遍历keys，获取当前遍历到的链表结构元素数据，用变量(linkedList)存起来
- 如果linkedList不为空，从链表头部开始遍历链表中的数据，获取当前遍历到的链表中的元素，将其存进valuePairs中。
- 返回valuePairs
线性探查
另一种解决冲突的方法是线性探查，之所以成为线性，是因为它处理冲突的方法是将元素直接存到表中，而不是在单独的数据结构中。
当想向表中某个位置添加一个新元素的时候，如果索引为position的位置已经被占据了，就尝试position 1的位置，如果position 1的位置也被占据了，就尝试position 2的位置，以此类推，直到在哈希表中找到一个空闲的位置。
接下来，我们就来看下用线性探查解决冲突，需要重写哪些方法
- 重写put方法
- 与HashMap一样，需要判断其参数的有效性以及传的参数数量
- 计算key的hash值，用一个变量存起来(position)
- 判断table的position位置是否被占据
- 如果没有被占据，则在position位置新建一个对象将key & value存进去
- 如果被占据，用一个变量(index)来接收position 1位置的值
- 遍历table的index位置的值，如果不为空index就一直自增。
- 当找到table中的空余位置时，在table的index位置新建一个对象将Key与Value存进去，返回true
- 重写get方法
- 计算key的hash值，用一个变量存起来(position)
- 判断table的position位置的元素是否为null | undefined,如果不是则返回undefined
- 判断table的position位置元素的key是否等于目标参数的key，如果等于则直接返回position位置的value值
- 如果不等于，用一个变量(index)来存储position 1位置的值
- 遍历table的index位置的值，如果index位置的值不为空并且index位置的key不等于目标参数的key，index就自增
- 循环结束后，判断当前table的index位置元素的key是否等于目标参数的key，如果相等则返回index位置的value值
- 重写remove方法
- 计算key的hash值，用一个变量存起来(position)
- 判断table的position位置是否为null，如果为null直接返回false
- 如果table的position位置的key等于目标参数的key，删除position位置的元素，验证本次删除是否有副作用，调整元素的位置，返回true
- 如果不相等，需要声明一个变量(index)查找position后面的值，默认值为position 1
- 遍历table的index位置的元素，如果其不为null并且其key与目标key不相等，index就自增
- 遍历技术后，如果index位置的元素不为null且index位置元素的key等于目标参数的key，则删除table中index位置的元素，验证本次删除是否有副作用，调整元素的位置，返回true
- 新增验证删除操作是否有副作用方法 (verifyRemoveSideEffect)，如果元素删除后产生了冲突，就需要将冲突的元素移动至一个之前的位置，这样就不会产生空位置。
- verifyRemoveSideEffect方法接收来那个参数：被删除的key，被删除key在table中的位置(removedPosition)
- 计算key的hash值，用一个变量存起来(hash)
- 用一个变量接收被删除key位置的下一个位置(index)，默认为removedPosition 1
- 遍历表，如果index位置的元素不为null，获取当前index位置的key的hash值，将其存进一个变量里(posHash)
- 如果posHash小于等于hash 或者 posHash小于等于removedPosition，将table中index位置的元素赋值给removedPosition位置
- 删除table中index位置的元素
- 将index赋值给removedPosition
- 继续下一轮循环判断
实现代码
经过分析后我们得到了实现思路，接下来我们就将上述思路转换为代码。
编写Map接口
我们知道字典和散列表有着很多共有方法，因此我们需要将共有方法分离成接口，然后根据不同的需求来实现不同的接口即可。
- 新建Map.ts文件
- 新建dictionary-list-models.ts文件
- 在dictionary-list-models中添加一个ValuePair类并将其导出，这个类用于存储字典中value值
// 生成一个对象
export class ValuePair<K,V>{
constructor(public key: K,public value: V) {}
toString(){
return `[#${this.key}: ${this.value}]`;
}
}
- 在Map中导入ValuePair类，添加并定义我们后面需要用到的方法并规定其返回值类型
import {ValuePair} from "../../utils/dictionary-list-models.ts";
export default interface Map<K,V> {
hasKey(key: K): boolean;
set?(key: K, value: V): boolean;
put?(key: K, value: V): boolean;
hashCode?(key: K): number;
remove(key: K): boolean;
get(key: K): V|undefined;
keyValues(): ValuePair<K, V>[];
keys(): K[];
values(): V[];
forEach(callbackFn: (key: K, value: V) => any): void;
size(): number;
isEmpty(): boolean;
clear():void;
toString():string;
}
实现字典类
- 新建Dictionary.ts文件，添加Dictionary类实现Map接口
export default class Dictionary<K, V> implements Map<K, V> {
}
- 声明私有属性table，用于字典的存储
private table: { [key: string]: ValuePair<K, V> };
- 在构造器中初始化table，声明值转字符串函数并赋予其默认值
// toStrFn用于将一个值转为字符串，可以自己来实现这部分逻辑，实例化时传进来
constructor(private toStrFn: (key: K) => string = defaultToString) {
this.table = {};
}
- 实现set方法
// 向字典中添加元素
set(key: K, value: V) {
if (key != null && value != null) {
// 将key转为字符串，字典中需要的key为字符串形式
const tableKey = this.toStrFn(key);
this.table[tableKey] = new ValuePair(key, value);
return true;
}
return false;
}
- 实现hasKey方法
hasKey(key: K) {
return this.table[this.toStrFn(key)] != null;
}
- 实现get方法
get(key: K) {
const valuePair = this.table[this.toStrFn(key)];
return valuePair == null ? undefined : valuePair.value;
}
- 实现remove方法
remove(key: K) {
if (this.hasKey(key)) {
delete this.table[this.toStrFn(key)];
return true;
}
return false;
}
- 实现keyValues方法
keyValues(): ValuePair<K, V>[] {
/* 使用ES2017引入的Object.values方法可以直接获取对象里存储的所有对应key的value值存进数组中 */
const valuePairs = [];
const keys = Object.keys(this.table);
for (let i = 0; i < keys.length; i ){
valuePairs.push(this.table[keys[i]])
}
return valuePairs;
}
- 实现keys方法
keys() {
// 可以直接使用map获取对象的key
// return this.keyValues().map(valuePair=> valuePair.key);
const keys = [];
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i ) {
keys.push(valuePairs[i].key);
}
return keys;
}
- 实现values方法
values() {
const values = [];
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i ) {
values.push(valuePairs[i].value);
}
return values;
}
- 实现forEach方法
forEach(callbackFn: (key: K, value: V) => any) {
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;
}
}
}
- 实现size、isEmpty、clear方法
size() {
return this.keyValues().length;
}
isEmpty() {
return this.size() === 0;
}
clear() {
this.table = {};
}
- 实现toString方法
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.ts
编写测试代码
上面我们实现了字典类，接下来我们来测试下上述代码是否都执行正常
代码语言：javascript复制const dictionary = new Dictionary();
dictionary.set("name","张三");
dictionary.set("age",20);
dictionary.set("id",198);
console.log("判断name是否在dictionary中",dictionary.hasKey("name"));
// 移除名为id的key
dictionary.remove("id");
console.log("判断id是否为dictionary中",dictionary.hasKey("id"));
console.log("将字典中存储的数据转为字符串",dictionary.toString())
// 获取dictionary中名为name的值
console.log("dictionary中名为name的值",dictionary.get("name"));
// 获取字典中所有存储的值
console.log("dictionary中所有存储的值",dictionary.keyValues());
// 获取字典中所有的键
console.log("dictionary中所有存储的键",dictionary.keys());
// 获取字典中所有的值
console.log("dictionary中所有存储的值",dictionary.values());
// 迭代字典中的每个键值对
const obj = {};
dictionary.forEach(function (key,value) {
obj[key] = value;
})
console.log(obj)
完整代码请移步：DictionaryTest.js
实现哈希表
- 新建HashMap类，实现Map接口。
export class HashMap<K,V> implements Map<K, V>{
}
- 声明table，并规定其类型
protected table:{ [key:number]: ValuePair<K, V> };
- 在构造器中初始化table，并规定值转字符串函数，允许调用者传一个值字符串函数
constructor(protected toStrFn: (key: K) => string = defaultToString) {
this.table = {};
}
- 实现hashCode、loseloseHashCode、djb2HashCode方法
// 生成哈希码
hashCode(key: K): number {
return this.loseloseHashCode(key);
}
// loselose实现哈希函数
loseloseHashCode(key: K): number {
if (typeof key === "number"){
return key;
}
const tableKey = this.toStrFn(key);
let hash = 0;
for (let i = 0; i < tableKey.length; i ){
// 获取每个字符的ASCII码将其拼接至hash中
hash = tableKey.charCodeAt(i);
}
return hash % 37;
}
// djb2实现哈希函数
djb2HashCode(key: K): number {
if (typeof key === "number"){
return 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;
}
- 实现put方法
put(key: K, value: V): boolean {
if (key != null && value != null){
const position = this.hashCode(key);
this.table[position] = new ValuePair(key, value);
return true;
}
return false;
}
- 实现get方法
get(key: K): V|undefined {
const valuePair = this.table[this.hashCode(key)];
return valuePair == null ? undefined : valuePair.value;
}
- 实现hasKey方法
hasKey(key: K): boolean {
return this.table[this.hashCode(key)] != null;
}
- 实现remove方法
remove(key: K): boolean {
if(this.hasKey(key)){
delete this.table[this.hashCode(key)];
return true;
}
return false;
}
- 实现keyValues、keys、values方法
keyValues(): ValuePair<K, V>[] {
const valuePairs = [];
// 获取对象中的所有key并将其转为int类型数组
const keys = Object.keys(this.table).map(item => parseInt(item));
for (let i = 0; i < keys.length; i ){
valuePairs.push(this.table[keys[i]]);
}
return valuePairs;
}
keys(): K[] {
const keys = [];
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i ){
keys.push(valuePairs[i].key);
}
return keys;
}
values(): V[] {
const values = [];
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i ){
values.push(valuePairs[i].value);
}
return values;
}
- 实现isEmpty、size、clear方法
isEmpty(): boolean {
return this.values().length === 0;
}
size(): number {
return this.keyValues().length;
}
clear(): void {
this.table= {};
}
- 实现forEach方法
forEach(callbackFn: (key: K, value: V) => any): void {
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方法
toString(): string {
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;
}
完整代码请移步: HashMap.ts
编写测试代码
我们测试下上述代码是否都正常执行
代码语言：javascript复制const hashMap = new HashMap();
hashMap.put("name", "张三");
hashMap.put("id", 1);
hashMap.put("class", "产品");
console.log("判断class是否存在与HashMap中", hashMap.hasKey("class"));
hashMap.remove("id");
console.log("判断id是否存在于HashMap中", hashMap.hasKey("id"))
console.log(hashMap.get("name"));
hashMap.forEach(((key, value) => {
console.log(key "=" value);
}))
console.log("判断HashMap中的数据是否为空",hashMap.isEmpty());
console.log("输出HashMap中所有key对应的value",hashMap.keyValues());
console.log("获取HashMap中的所有key值",hashMap.keys());
console.log("获取HashMap中的所有Value值",hashMap.values());
console.log("获取HashMap的大小",hashMap.size());
console.log("HashMap中的数据转字符串输出",hashMap.toString());
console.log("清空HashMap中的数据");
hashMap.clear();
// 测试hash值冲突问题
hashMap.put('Ygritte', 'ygritte@email.com');
hashMap.put('Jonathan', 'jonathan@email.com');
hashMap.put('Jamie', 'jamie@email.com');
hashMap.put('Jack', 'jack@email.com');
hashMap.put('Jasmine', 'jasmine@email.com');
hashMap.put('Jake', 'jake@email.com');
hashMap.put('Nathan', 'nathan@email.com');
hashMap.put('Athelstan', 'athelstan@email.com');
hashMap.put('Sue', 'sue@email.com');
hashMap.put('Aethelwulf', 'aethelwulf@email.com');
hashMap.put('Sargeras', 'sargeras@email.com');
console.log(hashMap.toString());
完整代码请移步：HashMapTest.js
分离链表法解决哈希冲突问题
执行上述测试代码后我们发现，有一些值冲突了，被替换掉了，产生了数据丢失问题。
我们来看看如何结合链表如何解决冲突问题。
- 新建HashMapSeparateChaining.ts文件，添加HashMapSeparateChaining类继承自HashMap
export default class HashMapSeparateChaining<K,V> extends HashMap<K, V> {
}
- 声明私有属性tableLink，并定义其类型，用于表的存储。
private tableLink:{ [key: number]: LinkedList<ValuePair<K, V>> };
- 在构造器中声明toStrFn方法赋予默认值，初始化父类和tableLink
constructor(protected toStrFn: (key: K) => string = defaultToString) {
super(toStrFn);
this.tableLink = {};
}
- 重写put方法
put(key: K, value: V): boolean {
if (key != null && value != null) {
const position = this.hashCode(key);
if (this.tableLink[position] == null){
// 如果当前要添加元素的位置为空则创建一个链表
this.tableLink[position] = new LinkedList<ValuePair<K, V>>();
}
// 往当前要添加元素的链表中添加当前当前元素
this.tableLink[position].push(new ValuePair(key,value));
return true;
}
return false;
}
- 重写get方法
get(key: K): V | undefined {
// 获取参数的hash值
const position = this.hashCode(key);
// 获取目标元素位置存储的链表结构元素
const linkedList = this.tableLink[position];
if (linkedList !=null && !linkedList.isEmpty()){
// 获取链表头部数据
let current = linkedList.getHead();
while (current != null){
// 遍历链表，找到链表中与目标参数相同的数据
if (current.element.key === key){
// 返回目标key对应的value值
return current.element.value;
}
current = current.next;
}
}
return undefined;
}
- 重写remove方法
remove(key: K): boolean {
const position = this.hashCode(key);
// 获取目标元素位置存储的链表结构元素
const linkedList = this.tableLink[position];
if (linkedList != null && !linkedList.isEmpty()){
// 获取链表头部元素
let current = linkedList.getHead();
while (current != null){
// 遍历链表，找到与目标元素相同的数据
if (current.element.key === key){
// 将当前链表中的元素从链表中移除
linkedList.remove(current.element);
if (linkedList.isEmpty()){
// 链表为空，删除目标位置元素
delete this.tableLink[position];
}
return true;
}
current = current.next;
}
}
return false;
}
- 重写clear方法
clear() {
this.tableLink = {};
}
- 重写keyValues方法
keyValues(): ValuePair<K, V>[] {
const valuePairs = [];
// 获取tableLink中的所有key并转为int类型
const keys = Object.keys(this.tableLink).map(item=>parseInt(item));
for (let i = 0; i < keys.length; i ){
const linkedList = this.tableLink[keys[i]];
if (linkedList != null && !linkedList.isEmpty()){
// 遍历链表中的数据，将链表中的数据放进valuePairs中
let current = linkedList.getHead();
while (current != null){
valuePairs.push(current.element);
current = current.next;
}
}
}
return valuePairs;
}
完整代码请移步：HashMapSeparateChaining.ts
编写测试代码
我们测试下上述方法是否都能正常执行
代码语言：javascript复制const hashMapSC = new HashMapSeparateChaining();
hashMapSC.put("name","张三");
hashMapSC.put("id",11);
hashMapSC.put("age",22);
hashMapSC.put("phone","09871588");
hashMapSC.remove("id");
console.log(hashMapSC.get("name"));
console.log("判断hashMap中的数据是否为空", hashMapSC.isEmpty());
console.log(hashMapSC.toString());
console.log("使用forEach遍历hashMap中的数据");
hashMapSC.forEach((key,value)=>{
console.log(`${key} = ${value}`);
})
console.log("获取hashMap中存储的所有key",hashMapSC.keys());
console.log("获取hashMap中存储的所有value",hashMapSC.values());
console.log("判断id是否在hashMap中",hashMapSC.hasKey("id"));
console.log("清空HashMap中的数据");
hashMapSC.clear();
console.log("判断HashMap中的数据是否为空", hashMapSC.isEmpty());
console.log("冲突测试")
hashMapSC.put('Ygritte', 'ygritte@email.com');
hashMapSC.put('Jonathan', 'jonathan@email.com');
hashMapSC.put('Jamie', 'jamie@email.com');
hashMapSC.put('Jack', 'jack@email.com');
hashMapSC.put('Jasmine', 'jasmine@email.com');
hashMapSC.put('Jake', 'jake@email.com');
hashMapSC.put('Nathan', 'nathan@email.com');
hashMapSC.put('Athelstan', 'athelstan@email.com');
hashMapSC.put('Sue', 'sue@email.com');
hashMapSC.put('Aethelwulf', 'aethelwulf@email.com');
hashMapSC.put('Sargeras', 'sargeras@email.com');
console.log(hashMapSC.toString());
完整代码请移步：HashMapSeparateChainingTest.js
线性探查解决哈希冲突问题
- 新建HashMapLinearProbing.ts文件，添加HashMapLinearProbing类继承自HashMap
export default class HashMapLinearProbing<K,V> extends HashMap<K, V>{
}
- 构造器中初始化父类
constructor() {
super();
}
- 重写put方法
put(key: K, value: V): boolean {
if (key != null && value!= null){
const position = this.hashCode(key);
// 判断当前要插入的位置在表中是否被占据
if (this.table[position] == null){
// 当前位置没有被占据，将Key & value放进ValuePair中赋值给当前表中要插入位置的元素
this.table[position] = new ValuePair(key,value);
} else{
// 位置被占据，递增index直至找到没有被占据的位置
let index = position 1;
while (this.table[index] != null){
index ;
}
// 找到没有被占据的位置，将Key & value放进ValuePair中赋值给当前表中要插入位置的元素
this.table[index] = new ValuePair(key,value);
}
return true;
}
return false;
}
- 重写get方法
get(key: K): V | undefined {
const position = this.hashCode(key);
if(this.table[position] != null) {
// 如果当前位置元素的key等于目标元素的key直接返回当前位置元素的value
if (this.table[position].key === key){
return this.table[position].value;
}
// 位置递增直至找到我们要找的元素或者找到一个空位置
let index = position 1;
while (this.table[index] != null && this.table[index].key !== key){
index ;
}
// 递增结束后，判断当前表中index的key是否等于目标key
if (this.table[index] != null && this.table[index].key === key){
return this.table[index].value;
}
}
return undefined;
}
- 重写remove方法
remove(key: K): boolean {
const position = this.hashCode(key);
if (this.table[position] != null){
if (this.table[position].key === key){
delete this.table[position];
// 删除后，验证本次删除是否有副作用，调整元素位置
this.verifyRemoveSideEffect(key,position);
return true;
}
let index = position 1;
while (this.table[index] != null && this.table[index].key !== key){
index ;
}
if (this.table[index] != null && this.table[index].key === key){
delete this.table[index];
this.verifyRemoveSideEffect(key,index);
return true;
}
}
return false;
}
- 实现verifyRemoveSideEffect方法
// 验证删除操作是否有副作用
private verifyRemoveSideEffect(key: K,removedPosition: number){
// 计算被删除key的哈希值
const hash = this.hashCode(key);
// 从被删除元素位置的下一个开始遍历表直至找到一个空位置
// 当找到一个空位置后即表示元素在合适的位置上不需要移动
let index = removedPosition 1;
while (this.table[index] != null){
// 计算当前遍历到的元素key的hash值
const posHash = this.hashCode(this.table[index].key);
console.log(`当前遍历到的元素的hash= ${posHash} , 上一个被移除key的hash = ${removedPosition}`)
if (posHash <= hash || posHash <= removedPosition){
// 如果当前遍历到的元素的哈希值小于等于被删除元素的哈希值或者小于等于上一个被移除key的哈希值(removedPosition)
// 需要将当前元素移动至removedPosition位置
this.table[removedPosition] = this.table[index];
// 移动完成后，删除当前index位置的元素
delete this.table[index];
// 更新removedPosition的值为index
removedPosition = index;
}
index ;
}
}
完整代码请移步：HashMapLinearProbing.ts
编写测试代码
测试下上述方法是否都正常执行
代码语言：javascript复制const hashMapLP = new HashMapLinearProbing();
console.log("冲突元素删除测试");
hashMapLP.put('Ygritte', 'ygritte@email.com');
hashMapLP.put('Jonathan', 'jonathan@email.com');
hashMapLP.put('Jamie', 'jamie@email.com');
hashMapLP.put('Jack', 'jack@email.com');
hashMapLP.put('Jasmine', 'jasmine@email.com');
hashMapLP.put('Jake', 'jake@email.com');
hashMapLP.put('Nathan', 'nathan@email.com');
hashMapLP.put('Athelstan', 'athelstan@email.com');
hashMapLP.put('Sue', 'sue@email.com');
hashMapLP.put('Aethelwulf', 'aethelwulf@email.com');
hashMapLP.put('Sargeras', 'sargeras@email.com');
// hashMapLP.remove("Ygritte");
hashMapLP.remove("Jonathan");
console.log(hashMapLP.toString());
完整代码请移步：HashMapLinearProbing.ts
更好的散列函数
代码中我们使用的是loseloseHashCode来生成hash值，这种方法会生成比较多的重复元素，因此不建议使用此方法，因为处理冲突会消耗很多的性能。
我们在上述代码中实现了djb2HashCode方法，此方法产生重复的hash值的概率很小，因此我们应该使用此方法来生成，接下来我们将hashCode使用的方法改为djb2HashCode，测试下HashMap的执行结果。
代码语言：javascript复制 hashCode(key: K): number {
return this.djb2HashCode(key);
}
❝结果在我们的预料之内，它没有产生重复的hash值，所有的元素都保存进去了。
