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

发布时间:2023年12月24日

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 扩容

装填因子过大会降低操作效率,这时可以考虑扩容,扩容后所有数据项都需要修改,因为扩容后哈希函数计算的index会改变

常见情况是loadFactor>0.75(如java)时进行扩容

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

    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];
        }
    }
    
  • 判断数字是否为质数(素数)

    容量最好是质数,大于1的自然数中,只能被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)
    
文章来源:https://blog.csdn.net/bfbshs_ddd/article/details/135186182
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。