使用JavaScript实现哈希表

关于哈希表的原理详见我的上一篇文章简单易懂数据结构之哈希表

前言

JavaScript中是有哈希类型的数据结构的，比方说最简单的对象{ },就有key: value这种结构。ES6新出的数据结构Map是对对象这种类型的扩展，同样也是哈希表。即便如此，重复造轮子还是有意义的，对于我们对底层原理的实现和编程能力的提高都是有帮助的。接下来让我们用JavaScript中的数组模拟哈希表这种数据结构。
代码链接：
简单哈希表：HashTable
仿Map哈希表: HashMap

结构设计

class HashTable {  //   初始化哈希表  constructor(size) {  }    //  从哈希表中取值    get() {}    //  向哈希表中填值    set() {}    //  从哈希表中删除数据    delete() {}    //  判断哈希表中存不存在该值    has() {}    //  展现哈希表中所有数据    showAllData() {}}

代码实现

class HashMap {  constructor(size) {    this.table = new Array(size)    this.size = 0  }  //哈希函数，将value转化，计算出存储的key  hashConversion(value) {    let keyCode = 0    for(let item of value) {      keyCode += item.charCodeAt(0)    }    let key = keyCode % this.table.length    return key  }  set(value) {    let key = this.hashConversion(value)    this.size++    this.table[key] = value  }  get(value) {    let key = this.hashConversion(value)    return this.table[key]  }  delete(value) {    let key = this.hashConversion(value)    if(this.table[key] !== undefined) {      this.table[key] = undefined      this.size--      return true    } else {      return false    }      }  has(value) {    let key = this.hashConversion(value)    if(this.table[key] !== undefined) {      return true    } else {      return false    }  }  showAllData() {    let result = []    for (let item of this.table) {      if(item !== undefined) {        result.push(item)      }    }    return result  }}

调用展现

let hashTable = new HashMap(10)hashTable.set('1')hashTable.set('aa')hashTable.set('6a')hashTable.set('75')console.log('size:' + hashTable.size)console.log(hashTable.showAllData())

结果展现1.png

冲突处理

仔细看上方的代码，很显著没有做冲突的解决，当输入的值发生冲突时，我们就没有办法得到想要的结果，在这里扩展上方代码，用线性探测法进行冲突解决。

/* *使用数组模拟的JavaScript哈希表 *使用最简单的线性探测法处理冲突 */class HashTable {  constructor(size) {    this.table = new Array(size)    this.size = 0  }  //哈希函数  hashConversion(value) {    let keyCode = 0    for(let item of value) {      keyCode += item.charCodeAt(0)    }    let key = keyCode % this.table.length    return key  }  //set方法，用来向哈希表中填入数据  set(value) {    let key = this.hashConversion(value)    while(this.table[key] !== undefined && this.table[key] !== value) {      key++      if(key >= this.table.length) {        throw new Error('已经没有可用空间')      }    }      if (this.table[key] !== value) {        this.size++        this.table[key] = value      }  }  //get方法，用来从哈希表中取值  get(value) {    let key = this.hashConversion(value)    while(this.table[key] !== undefined && this.table[key] !== value) {      key++      if(key >= this.table.length) {        return undefined      }    }      return this.table[key]  }  //delete方法，用来删除哈希表的数据  delete(value) {    let key = this.hashConversion(value)    while(this.table[key] !== undefined && this.table[key] !== value) {      key ++      if(key >= this.table.length) {        return false      }    }    this.table[key] = undefined    this.size--    return true  }  //has方法，判断哈希表中有没有该值  has(value) {    let key = this.hashConversion(value)    while(this.table[key] !== undefined && this.table[key] !== value) {      key ++      if(key >= this.table.length) {        return false      }    }    if(this.table[key] !== undefined) {      return true    } else {      return false    }  }  //展现存储到哈希表中的所有数据  showAllData() {    let result = []    for (let item of this.table) {      if(item !== undefined) {        result.push(item)      }    }    return result  }}

扩展

上文的HashTable有一个缺点，不能自己定义key值，我们想要相似JavaScript中对象或者者说Map的功能，可以做到set(key,value), get(key) –>value这种功能。这就要对上文对数据结构进行更进一步的扩展。

/* *使用数组模拟的JavaScript仿Map哈希表 *使用最简单的线性探测法处理冲突 */class HashMap {  constructor(size) {    this.table = []    for(let i = 0; i < size; i++) {      this.table.push([undefined, 0])    }    this.size = 0  }  //哈希函数  hashConversion(index) {    let keyCode = 0    for(let item of index) {      keyCode += item.charCodeAt(0)    }    let key = keyCode % this.table.length    return key  }  //set方法，用来向哈希表中填入数据  set(index, value) {    let key = this.hashConversion(index)    while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {      key++      if(key >= this.table.length) {        throw new Error('已经没有可用空间')      }    }      if ((this.table[key])[0] !== index) {        this.size++        this.table[key][0] = index        this.table[key][1] = value      }  }  //get方法，用来从哈希表中取值  get(index) {    let key = this.hashConversion(index)    while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {      key++      if(key >= this.table.length) {        return undefined      }    }      return (this.table[key])[1]  }  //delete方法，用来删除哈希表的数据  delete(index) {    let key = this.hashConversion(index)    while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {      key ++      if(key >= this.table.length) {        return false      }    }    this.table[key] = new Array(2)    this.size--    return true  }  //has方法，判断哈希表中有没有该值  has(index) {    let key = this.hashConversion(index)    while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {      key ++      if(key >= this.table.length) {        return false      }    }    if((this.table[key])[0] !== undefined) {      return true    } else {      return false    }  }  //展现存储到哈希表中的所有数据  showAllData() {    let result = []    for (let item of this.table) {      if(item[0] !== undefined) {        result.push(item)      }    }    return result  }}

总结

尽管自己封装的哈希表远不如JavaScript中的Map，但是从自己实现该数据结构的过程中也收获了很多。