JavaScript中散列表(哈希表)的详细介绍(代码示例)

雨婷吖_4630

雨婷吖_4630

2019-01-02

4753人浏览

转载

本篇文章给大家带来的内容是关于javascript中散列表(哈希表)的详细介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

散列表

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

2472848212-5c2afb47f10ad_articlex.png

我们从上图开始分析

  • 有一个集合U,里面分别是1000,10,152,9733,1555,997,1168

  • 右侧是一个10个插槽的列表(散列表),我们需要把集合U中的整数存放到这个列表中

  • 怎么存放,分别存在哪个槽里?这个问题就是需要通过一个散列函数来解决了。我的存放方式是取10的余数,我们对应这图来看

    • 1000%10=0,10%10=0 那么1000和10这两个整数就会被存储到编号为0的这个槽中

    • 152%10=2那么就存放到2的槽中

    • 9733%10=3 存放在编号为3的槽中

通过上面简单的例子,应该会有一下几点一个大致的理解

  • 集合U,就是可能会出现在散列表中的键

  • 散列函数,就是你自己设计的一种如何将集合U中的键值通过某种计算存放到散列表中,如例子中的取余数

  • 散列表,存放着通过计算后的键

那么我们在接着看一般我们会怎么去取值呢?

比如我们存储一个key为1000,value为'张三' ---> {key:1000,value:'张三'}
从我们上述的解释,它是不是应该存放在1000%10的这个插槽里。
当我们通过key想要找到value张三,是不是到key%10这个插槽里找就可以了呢?到了这里你可以停下来思考一下。

散列的一些术语(可以简单的看一下)

  • 散列表中所有可能出现的键称作全集U

  • 用M表示槽的数量

  • 给定一个键,由散列函数计算它应该出现在哪个槽中,上面例子的散列函数h=k%M,散列函数h就是键k到槽的一个映射。

  • 1000和10都被存到了编号0的这个槽中,这种情况称之为碰撞。

看到这里不知道你是否大致理解了散列函数是什么了没。通过例子,再通过你的思考,你可以回头在读一遍文章头部关于散列表的定义。如果你能读懂了,那么我估计你应该是懂了。

常用的散列函数

处理整数 h=>k%M (也就是我们上面所举的例子)

处理字符串:

使用 Husky 在 JavaScript 仓库中强制执行本地 Git 钩子检查
使用 Husky 在 JavaScript 仓库中强制执行本地 Git 钩子检查

使用 Husky 将 pre-commit、pre-push 和 commit-msg 检查集成到仓库中,以便代理和开发人员在更改离开工作站之前运行相同的本地防护措施。

下载
    function h_str(str,M){
        return [...str].reduce((hash,c)=>{
            hash = (31*hash + c.charCodeAt(0)) % M
        },0)
    }

hash算法不是这里的重点,我也没有很深入的去研究,这里主要还是去理解散列表是个怎样的数据结构,它有哪些优点,它具体做了怎样一件事。
而hash函数它只是通过某种算法把key映射到列表中。

构建散列表

通过上面的解释,我们这里做一个简单的散列表

散列表的组成

  • M个槽

  • 有个hash函数

  • 有一个add方法去把键值添加到散列表中

  • 有一个delete方法去做删除

  • 有一个search方法,根据key去找到对应的值

初始化

- 初始化散列表有多少个槽
- 用一个数组来创建M个槽

    class HashTable {
        constructor(num=1000){
            this.M = num;
            this.slots = new Array(num);
        }
    }

散列函数

处理字符串的散列函数,这里使用字符串是因为,数值也可以传换成字符串比较通用一些

先将传递过来的key值转为字符串,为了能够严谨一些

将字符串转换为数组, 例如'abc' => [...'abc'] => ['a','b','c']

分别对每个字符的charCodeAt进行计算,取M余数是为了刚好对应插槽的数量,你总共就10个槽,你的数值%10 肯定会落到 0-9的槽里

    h(str){
        str = str + '';
        return [...str].reduce((hash,c)=>{
            hash = (331 * hash + c.charCodeAt()) % this.M;
            return hash;
        },0)
    }

添加

调用hash函数得到对应的存储地址(就是我们之间类比的槽)

因为一个槽中可能会存多个值,所以需要用一个二维数组去表示,比如我们计算得来的槽的编号是0,也就是slot[0],那么我们应该往slot[0] [0]里存,后面进来的同样是编号为0的槽的话就接着往slot[0] [1]里存

    add(key,value) {
        const h = this.h(key);
        // 判断这个槽是否是一个二维数组, 不是则创建二维数组
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 将值添加到对应的槽中
        this.slots[h].push(value);
    }

删除

通过hash算法,找到所在的槽

通过过滤来删除

    delete(key){
        const h = this.h(key);
        this.slots[h] = this.slots[h].filter(item=>item.key!==key);
    }

查找

通过hash算法找到对应的槽

用find函数去找同一个key的值

返回对应的值

    search(key){
        const h = this.h(key);
        const list = this.slots[h];
        const data = list.find(x=> x.key === key);
        return data ? data.value : null;    
    }

总结

讲到这里,散列表的数据结构已经讲完了,其实我们每学一种数据结构或算法的时候,不是去照搬实现的代码,我们要学到的是思想,比如说散列表它究竟做了什么,它是一种存储方式,可以快速的通过键去查找到对应的值。那么我们会思考,如果我们设计的槽少了,在同一个槽里存放了大量的数据,那么这个散列表它的搜索速度肯定是会大打折扣的,这种情况又应该用什么方式去解决,又或者是否用其他的数据结构的代替它。

补充一个小知识点

v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储,而arr = [] , arr[100000] = 10 这样的操作它是使用的散列,因为这种操作如果连续开辟100万个空间去存储一个值,那么显然是在浪费空间。


Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南

相关文章

java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

node.js javascript

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

0

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

0

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

2026.11.20

0

8

PHP8.6升级迁移教程
PHP8.6升级迁移教程

本专题汇总PHP8.6升级迁移与弃用接口改造教程,涵盖反射调用、对象属性赋值、标识符更名、构造函数与__debugInfo调整,以及插件类名检查、常量导出、ArrayIterator排序、SPL和DTO查询参数转换,帮助梳理弃用提示并完成代码兼容改造。

2026.11.20

0

10

PHP8.6安装配置与FPM运维教程
PHP8.6安装配置与FPM运维教程

本专题汇总PHP8.6正式版安装部署与FPM运维教程,涵盖Linux并存安装、独立ini配置、扩展重新编译、Nginx切换与回滚、FPM状态监控和慢日志排查,以及环境变量、请求超时、OPcache刷新和预加载配置。

2026.11.20

0

10

Nginx CVE-2026-123007排查与防护指南
Nginx CVE-2026-123007排查与防护指南

Nginx HTTP/2漏洞该怎么修复?本专题围绕CVE-2026-123007,介绍安全版本升级、模块兼容检查和配置恢复方法,以及日志排查、权限设置等后续加固操作,方便你按实际部署情况查找对应教程。

2026.11.20

20

8

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

60

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

80

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
LLVM Programmer’s Manual
LLVM Programmer’s Manual

共0课时 | 0人学习

MongoDB 教程
MongoDB 教程

共17课时 | 6.6万人学习