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

news/2024/7/10 23:59:57 标签: javascript, es6, 散列表

5. 哈希表(散列表/字典)

文章目录

    • 5. 哈希表(散列表/字典)
      • 5.1 概念
      • 5.2 哈希表的实现
      • 5.3 扩容

5.1 概念

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

5.2 哈希表的实现

  • 常见方法:

    • 存放元素
    • 获取元素
    • 删除元素
    • 哈希表扩容
  • 封装

    javascript">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)时进行扩容

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

    javascript">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方法中调用

    javascript">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和自己整除的数

    javascript">//如果一个数可以被大于其平方根的整数整除,那么一定也可以被小于其平方根的整数整除
    //添加方法判断
    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;
    }
    
  • 扩容为质数

    javascript">//添加方法获得质数
    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)
    

http://www.niftyadmin.cn/n/5284603.html

相关文章

C++ 比 C语言的新增的特性 1

1. C是C的增强 1.1 C是静态类型的语言&#xff0c;具有严格的数据类型检查 1.1.1 c 因为const修饰的变量不允许修改&#xff0c;但是只给了警告&#xff0c;不严谨 const int a10;a20; //报错int *p&a;*p20;//a的值&#xff1f; test1.c:6:9: warning: initialization dis…

【文本处理】正则表达式

一、简介 正则表达式&#xff0c;又称规则表达式,&#xff08;Regular Expression&#xff0c;在代码中常简写为regex、regexp或RE&#xff09;&#xff0c;是一种文本模式&#xff0c;包括普通字符&#xff08;例如&#xff0c;a 到 z 之间的字母&#xff09;和特殊字符&…

二、安全与风险管理—风险管理

目录 一、什么是风险及风险管理过程 二、威胁建模 三、主动攻击和被动攻击

uni-app之HelloWorld实现

锋哥原创的uni-app视频教程&#xff1a; 2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中...共计23条视频&#xff0c;包括&#xff1a;第1讲 uni…

机器学习之实验过程02

机器学习之实验过程-数据清理 from sklearn.model_selection import train_test_split from sklearn.metrics import mean_squared_errordata_path = /home/py/Work/机器学习/labs/data/Feedback.csv df = pd.read_csv(data_path) df.head() print (df.tail()) rename_pai…

Python 数据分析 Matplotlib篇 增加注释【plt.text() plt.annotate()】(第3讲)

Python 数据分析 Matplotlib篇 增加注释【plt.text() & plt.annotate()】(第3讲)         🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔…

VL53L4CX TOF开发(1)----驱动TOF进行测距

VL53L4CX TOF开发.1--驱动TOF进行测距 概述视频教学样品申请完整代码下载主要特点硬件准备技术规格系统框图应用示意图生成STM32CUBEMX选择MCU串口配置IIC配置 XSHUTX-CUBE-TOF1演示结果 概述 VL53L4CX 是一款先进的激光距离传感器&#xff0c;专为长距离和多目标测量设计&…

嵌入式开发——DMA外设到内存

学习目标 加强理解DMA数据传输过程加强掌握DMA的初始化流程掌握DMA数据表查询理解源和目标的配置理解数据传输特点能够动态配置源数据学习内容 需求 uint8_t data; 串口接收(&data);data有数据了 实现串口的数据接收,要求采用dma的方式。 数据交互流程 CPU配置好DMA外…