JavaScript(ES6)数据结构与算法之哈希表_Javascript

5. 哈希表（散列表/字典）

文章目录

- 5. 哈希表（散列表/字典）

5.1 概念

基于数组实现，存放键值对：结构是数组，对输入的键进行变换（哈希函数）得到hashcode
解决冲突（不同下标值hashcode相同）
- 链地址法（常用）：每个数组单元存储数组或链表，出现相同映射就链式延伸添加
- 开放地址法（少）：寻找空白单元格（线性探测、二次探测、再哈希法）来添加重复的数据，可能会扩容
优势：
- 非常快速的插入删除查找操作
- 速度比树快，编码比树容易
劣势：
- 数据没有顺序，不能按大小等遍历
- key不允许重复
装填因子：
- 装填因子=总数据项/哈希表长度
- 装填因子越大，探测长度越长，哈希表插入和搜索效率降低，链地址法随装填因子改变，效率改变更小，因此更常被采用
- 链地址法装填因子可以大于1，开放地址法装填因子最大为1
设计哈希函数
- 快速计算，多项式的优化：霍纳法则（秦九韶算法），降低时间复杂度从o(n^2)到o(n)
- 均匀分布：使用常量的地方，尽量使用质数

5.2 哈希表的实现

常见方法：
- 存放元素
- 获取元素
- 删除元素
- 哈希表扩容

封装

export class hashtable{
    constructor(){
        this.storage=[]//数组存储元素
        this.count=0;//当前存放了多少个元素
        this.limit=8;//容量
    }
    
    //哈希函数
    hashfunc(str,max){
        //1.定义hashcode
        let hashcode = 0;
        //2.霍纳算法
        for(let i=0;i<str.length;i++){
            hashcode = 31*hashcode + str.charcodeat(i);
        }
        hashcode = hashcode%max;
        
        return hashcode;
    }
    
    //存放元素方法
    put(key,value){
        //1.根据key映射到index
        const index = this.hashfunc(key,this.limit);
        
        //2.取出数组
        //storage的每个index都可以有一个bucket
        let bucket = this.storage[index];
        if(bucket === undefined){
            bucket = [];
            this.storage[index] = bucket;
        }
        //3.判断是插入还是修改操作
        let overwride = false;
        for(let i = 0;i<bucket.length;i++){
            let tuple = bucket[i];
            //bucket是二维数组，一个放key，一个放value
            if(tuple[0] === key){
                tuple[1]=value;
                overwride = true;
            }
        }
        //4.如果没有覆盖（没有该key），则新增
        if(!overwride){
            bucket.push([key,value]);
            this.count++;
        }
        
        
    }
    
    //获取元素方法
    get(key){
        //1.根据key获得index
        const index = this.hashfunc(key,this.limit);
        
        //2.获得bucket
        const bucket = this.storage[index];
        if(bucket === undefined){
            return null;
        }
        
        //3.遍历bucket,一个个查找
        for(let i = 0;i<bucket.length;i++){
            let tuple = bucket[i];
            if(tuple[0] === key){
                return tuple[1];
            }
        }
        //4.遍历完，没有找到则返回null
        return null；
    }
    
    //删除元素方法
    remove(key){
        //1.根据key获得index
        const index = rhis.hashfunc(key,this.limit);
        
        //2.获得bucket
        const bucket = this.storage[index];
        if(bucket === undefined){
            return null;
        }
        
        //3.遍历bucket，找到元素，并将删除的元素返回
        for(let i=0;i<bucket.length;i++){
            let tuple = bucket[i];
            if(tuple[0] === key){
                bucket.splice(i,1);
                this.count--;
                return tuple[1]
            }
        }
    }
    
    isempty(){
        return this.count===0;
    }
    
    size(){
        return this.count;
    }
    
}

5.3 扩容

哈希表的扩容(也可能缩小容量)

resize(newlimit){
    //1.保留原数组中的内容
    let oldstorage = this.storage;
    
    //2.重置属性
    this.limit = newlimit;
    this.storage = [];
    this.count = 0;
    
    //3.取出oldstorage所有的元素，重新放入到storage
    oldstorage.foreach((bucket)=>{
        if(bucket === null){
            return
        }
        for(let i = 0;i<bucket.length;i++){
            let tuple = bucket[i];
            //直接调用put方法，limit已经更新了
            this.put(tuple[0],tuple[1])
        }
    })
    
}

在put方法和remove方法中调用

const max_load_factor = 0.75;
const min_load_factor = 0.75;

put(key,value){
    //略
    if(!overwride){
        bucket.push([key,value]);
        this.count++;
        
        if(this.count>this.limit*max_load_factor){
            this.resize(this.limit*2);
        }
    }
    
}

remove(key){
    //略
    for(let i = 0;i<bucket.length;i++){
        let tuple = bucket[i];
        if(tuple[0] === key){
            bucket.splice(i,1);
            this.count--;
            
            
 //设置容量不小于8
            if(this.limit>8&&this.count<this.limit*min_load_factor){
                this.resize(math.floor(this.limit/2))
            }
        }
        return tuple[1];
    }
}

判断数字是否为质数（素数）

//如果一个数可以被大于其平方根的整数整除，那么一定也可以被小于其平方根的整数整除
//添加方法判断
isprime(num){
    //1.获取平方根，向上取整
    var temp = math.ceil(math.sqrt(num))
    for(let i=2;i<=temp;i++){
        if(num%i===0){
            return true;
        }    
    }
    return false;
}

扩容为质数

//添加方法获得质数
getprime(num){
    while(!isprime(num)){
        num++;
    }
    return num;
}

//修改put 
let newlimit = this.getprime(this.limit*2);
this.resize(newlimit)
//修改remove
let newlimit = this.getprime(math.floor(this.limit/2));
this.resize(newlimit)