哈希表——js实现哈希表
发布时间
阅读量：
阅读量
哈希表：基于数组，不能重复且无序
将名称及单词与下标或数字对应起来
1.将字母或单词转换成下标或数字（hashCode）——过程讲解：
方案一：数字相加——数组下标太小
方案二：幂的连乘——数组下标太多
方案改进：哈希化，例如取余操作
冲突：哈希化后依然有数组下标会重复
解决冲突的两种方案：1.链地址法（拉链法）2.开放地址法
一：链地址法
采用处理发生通常较少出现的冲突项的方式，在一个链表（或数组）中存放这些项，并将其存入对应索引位置
二：开放地址法
识别空单元格并以某种形式填充重复数据（通常情况下,这种存储策略会导致存储空间消耗达到实际所需数据量的两倍）
解决冲突的方法：1. 线性探查法 2. 二次探查策略（调整探查步长） 3. 通过再哈希生成的哈希函数 : stepSize=constant-(key%constant)
解决冲突的方法：1. 线性探查法 2. 二次探查策略（调整探查步长） 3. 通过再哈希生成的哈希函数 : stepSize=constant-(key%constant)
快速计算：霍纳法则
put插入数据函数的封装
get方法图解思路
删除数据
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<script>
function HashTable(){
this.storage = []
this.count = 0
this.limit = 7
HashTable.prototype.hashFunc = function(str, size){
//1.定义hashCode变量
var hashCode = 0
//2.根据霍纳算法,计算hashCode的值
//借助Unicode编码计算
for(var i=0; i< str.length; i++){
hashCode = 37 * hashCode + str.charCodeAt(i)
}
//3.取余操作 5%4=1
var index = hashCode % size
return index
}
HashTable.prototype.put = function(key, value){
//1.根据key获取对应的index
var index = this.hashFunc(key,this.limit)
//2.根据index取得对应的bucket(bucket是key的hashCode对应下表位置，)
var bucket = this.storage[index]
//3.判断当前bucket是否为空
if(bucket == null){
bucket = []
this.storage[index] = bucket
}
//4.判断是否修改数据
for(var i= 0; i< bucket.length; i++){
var tuple = bucket[i]
if(tuple[0]==key){
tuple[1] = value
return
}
}
//5.当前bucket(链表)中没有该数据,就直接添加该数据
bucket.push([key, value])
this.count +=1
}
//get获取元素
HashTable.prototype.get = function(key){
/** *1.根据key,获得index;
* 2.根据index,获得bucket;
* 3.判断bucket是否为null,为null就直接返回null
* 4.bucket不为null，则遍历找到对应的key
* 5.遍历完后，没有找到对应的key，就返回null
**/
var index = this.hashFunc(key,this.limit)
var bucket = this.storage[index]
if(bucket == null){
return null
}
for(var i=0;i< bucket.length;i++){
var tuple = bucket[i]
if(tuple[0]== key){
return tuple[1]
}
}
//在index对应的bucket（不为null）中没有找到对应的key
return null
}
//remove方法
HashTable.prototype.remove = function(key){
var index = this.hashFunc(key,this.limit)
var bucket = this.storage[index]
if(bucket == null){
return null
}
for(var i=0; i<bucket.length;i++){
var tuple = bucket[i]
if(tuple[0] == key){
bucket.splice(i,1)//删除当前位置的元素https://wangdoc.com/javascript/stdlib/array.html#splice
this.count--
return tuple[1]
}
}
return null
}
HashTable.prototype.isEmpty = function(){
return this.count==0
}
HashTable.prototype.size = function(){
return this.count
}
}
var ht = new HashTable()
ht.put('abc','123')
ht.put('abd','456')
ht.put('cbd','789')
ht.put('aee','235')
alert(ht.get('abc'))
ht.put('abc','111')
alert(ht.get('abc'))
ht.remove('abc')
alert(ht.get('abc'))
</script>
</body>
</html>
代码解释实现容量恒为质数
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<script>
function HashTable(){
this.storage = []
this.count = 0
this.limit = 7
HashTable.prototype.hashFunc = function(str, size){
//1.定义hashCode变量
var hashCode = 0
//2.根据霍纳算法,计算hashCode的值
//借助Unicode编码计算
for(var i=0; i< str.length; i++){
hashCode = 37 * hashCode + str.charCodeAt(i)
}
//3.取余操作 5%4=1
var index = hashCode % size
return index
}
HashTable.prototype.put = function(key, value){
//1.根据key获取对应的index
var index = this.hashFunc(key,this.limit)
//2.根据index取得对应的bucket(bucket是key的hashCode对应下表位置，)
var bucket = this.storage[index]
//3.判断当前bucket是否为空
if(bucket == null){
bucket = []
this.storage[index] = bucket
}
//4.判断是否修改数据
for(var i= 0; i< bucket.length; i++){
var tuple = bucket[i]
if(tuple[0]==key){
tuple[1] = value
return
}
}
//5.当前bucket(链表)中没有该数据,就直接添加该数据
bucket.push([key, value])
this.count +=1
//数组扩容
if(this.count > this.limit * 0.75 ){
var newSize = this.limit
var newPrime = this.getPrime(newSize)
this.resize(newPrime)
}
}
//get获取元素
HashTable.prototype.get = function(key){
/** *1.根据key,获得index;
* 2.根据index,获得bucket;
* 3.判断bucket是否为null,为null就直接返回null
* 4.bucket不为null，则遍历找到对应的key
* 5.遍历完后，没有找到对应的key，就返回null
**/
var index = this.hashFunc(key,this.limit)
var bucket = this.storage[index]
if(bucket == null){
return null
}
for(var i=0;i< bucket.length;i++){
var tuple = bucket[i]
if(tuple[0]== key){
return tuple[1]
}
}
//在index对应的bucket（不为null）中没有找到对应的key
return null
}
//remove方法
HashTable.prototype.remove = function(key){
var index = this.hashFunc(key,this.limit)
var bucket = this.storage[index]
if(bucket == null){
return null
}
for(var i=0; i<bucket.length;i++){
var tuple = bucket[i]
if(tuple[0] == key){
bucket.splice(i,1)//删除当前位置的元素https://wangdoc.com/javascript/stdlib/array.html#splice
this.count--
return tuple[1]
//缩小容量
if(this.limit>7 && this.count < this.limit * 0.25){
var newSize = Math.floor(this.limit / 2)
var newPrime = this.getPrime(newSize)
this.resize(newPrime)
}
}
}
return null
}
HashTable.prototype.isEmpty = function(){
return this.count==0
}
HashTable.prototype.size = function(){
return this.count
}
//哈希表的扩容
HashTable.prototype.resize = function(newLimit){
var oldStorage = this.storage
this.storage = []
this.count =0
this.limit = newLimit
var bucket = []
for(var i=0;i<this.count;i++){
bucket = oldStorage[i]
if(bucket == null){
continue
}
for(var j=0; j<bucket.length;j++){
var tuple =bucket[i]
this.put(tuple[0],tuple[1])
}
}
}
//判断数字是否是质数
HashTable.prototype.isPrime = function (num){
//1.获得num的平方根
var temp = parseInt(Math.sqrt(num))
for(var i =2; i< temp; i++){
if(num % i == 0){
return false
}
}
return true
}
//获取质数的方法
HashTable.prototype.getPrime = function(num){
while(!this.isPrime(num)){
num++
}
return num
}
}
var ht = new HashTable()
ht.put('abc','123')
ht.put('abd','456')
ht.put('cbd','789')
ht.put('aee','235')
alert(ht.get('abc'))
ht.put('abc','111')
alert(ht.get('abc'))
ht.remove('abc')
alert(ht.get('abc'))
</script>
</body>
</html>
代码解释全部评论 (0)
还没有任何评论哟~