JavaScript中散列表(哈希表)的具体介绍（代码示例）-百分百源码网

JavaScript中散列表(哈希表)的具体介绍（代码示例）

发布时间：09/01 来源：未知浏览：关键词：

本篇文章给大家带来的内容是关于JavaScript中散列表(哈希表)的具体介绍（代码示例），有必然的参照价值，有需要的伴侣可以参照一下，但愿对你有所帮忙。

散列表

散列表（Hash table，也叫哈希表），是按照键（Key）而直接拜访在内存储备位置的数据构造。也就是说，它通过运算一个关于键值的函数，将所需查询的数据映射到表中一个位置来拜访记载，这加快了查寻速度。这个映射函数称做散列函数，存置记载的数组称做散列表。

我们从上图开端剖析

有一个汇合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 （也就是我们上面所举的例子）

处置字符串：

    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;    
    }

总结

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