字典(Map)与散列表(HashMap)是一种采用[键(key),值(value)]对的形式来存储数据的数据结构。
本文将详细讲解字典与散列表的实现思路并使用TypeScript将其实现,欢迎各位感兴趣的前端开发者阅读本文。
字典与散列表存储数据的方式是键值对的形式来存储,因此我们可以使用JavaScript中的对象来实现。
字典通过键值对的形式来存储数据,它的键是字符串类型,调用者传的key是什么,它的键就是什么。
一个完整的字典类需要具备:判断一个键是否在字典中、向字典中添加元素、根据key移除字典中存的元素、根据key查找字典中的元素、获取字典中存储的所有元素等方法,接下来我们来分析下这些方法的实现思路。
散列表又叫哈希表,它是字典的另一种实现,它与字典的不同之处在于其key值的存储。
字典存储元素时会将key转为字符串后再存储元素。
散列表存储元素时会将key进行hash计算,得到hash值后再存储元素。
在查找元素时,字典需要去迭代整个数据结构来查找目标元素,而散列表是通过hash值来存储的,我们只需要对目标元素进行hash值计算,就可以快速找到目标元素的位置。因此,散列表的效率要比字典的效率高。
由于散列表相比哈希表有着许多相同的地方,但是他们存储数据的key不一样,因此我们需要把其用到的方法写到一个接口里,分别根据各自的特点来实现这个接口,接下来我们来分析下哈希表中与字典中不同的地方其方法的实现。
我们在使用HashMap时,如果调用的是loseloseHashCode方法来计算的哈希值,那么其冲突率会很高,此处介绍两种比较常用的处理哈希冲突问题的方法。
分离链接法,会为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突最简单的方法,但是它会占用额外的存储空间。
由于分离链接的方法只是改变了HashMap的存储结构,因此我们可以继承HashMap重写与HashMap不同的方法即可。
另一种解决冲突的方法是线性探查,之所以成为线性,是因为它处理冲突的方法是将元素直接存到表中,而不是在单独的数据结构中。
当想向表中某个位置添加一个新元素的时候,如果索引为position的位置已经被占据了,就尝试position + 1的位置,如果position + 1的位置也被占据了,就尝试position + 2的位置,以此类推,直到在哈希表中找到一个空闲的位置。
接下来,我们就来看下用线性探查解决冲突,需要重写哪些方法
经过分析后我们得到了实现思路,接下来我们就将上述思路转换为代码。
我们知道字典和散列表有着很多共有方法,因此我们需要将共有方法分离成接口,然后根据不同的需求来实现不同的接口即可。
// 生成一个对象
export class ValuePair<K,V>{
constructor(public key: K,public value: V) {}
toString(){
return `[#${this.key}: ${this.value}]`;
}
}
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;
}
export default class Dictionary<K, V> implements Map<K, V> {
}
private table: { [key: string]: ValuePair<K, V> };
// toStrFn用于将一个值转为字符串,可以自己来实现这部分逻辑,实例化时传进来
constructor(private toStrFn: (key: K) => string = defaultToString) {
this.table = {};
}
// 向字典中添加元素
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(key: K) {
return this.table[this.toStrFn(key)] != null;
}
get(key: K) {
const valuePair = this.table[this.toStrFn(key)];
return valuePair == null ? undefined : valuePair.value;
}
remove(key: K) {
if (this.hasKey(key)) {
delete this.table[this.toStrFn(key)];
return true;
}
return false;
}
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() {
// 可以直接使用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() {
const values = [];
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i++) {
values.push(valuePairs[i].value);
}
return values;
}
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() {
return this.keyValues().length;
}
isEmpty() {
return this.size() === 0;
}
clear() {
this.table = {};
}
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
上面我们实现了字典类,接下来我们来测试下上述代码是否都执行正常
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
export class HashMap<K,V> implements Map<K, V>{
}
protected table:{ [key:number]: ValuePair<K, V> };
constructor(protected toStrFn: (key: K) => string = defaultToString) {
this.table = {};
}
// 生成哈希码
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(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(key: K): V|undefined {
const valuePair = this.table[this.hashCode(key)];
return valuePair == null ? undefined : valuePair.value;
}
hasKey(key: K): boolean {
return this.table[this.hashCode(key)] != null;
}
remove(key: K): boolean {
if(this.hasKey(key)){
delete this.table[this.hashCode(key)];
return true;
}
return false;
}
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(): boolean {
return this.values().length === 0;
}
size(): number {
return this.keyValues().length;
}
clear(): void {
this.table= {};
}
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(): 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
我们测试下上述代码是否都正常执行
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
执行上述测试代码后我们发现,有一些值冲突了,被替换掉了,产生了数据丢失问题。
我们来看看如何结合链表如何解决冲突问题。
export default class HashMapSeparateChaining<K,V> extends HashMap<K, V> {
}
private tableLink:{ [key: number]: LinkedList<ValuePair<K, V>> };
constructor(protected toStrFn: (key: K) => string = defaultToString) {
super(toStrFn);
this.tableLink = {};
}
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(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(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() {
this.tableLink = {};
}
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
我们测试下上述方法是否都能正常执行
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
export default class HashMapLinearProbing<K,V> extends HashMap<K, V>{
}
constructor() {
super();
}
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(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(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;
}
// 验证删除操作是否有副作用
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
测试下上述方法是否都正常执行
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的执行结果。
hashCode(key: K): number {
return this.djb2HashCode(key);
}
❝结果在我们的预料之内,它没有产生重复的hash值,所有的元素都保存进去了。