文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

JavaScript实现哈希表的方法

2024-04-02 19:55

关注

本篇内容主要讲解“JavaScript实现哈希表的方法”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“JavaScript实现哈希表的方法”吧!

JavaScript实现哈希表的方法

哈希表通常是基于数组进行实现的,但是相对于数组,它有很多优势:

  1. 它可以提供非常快速的插入-删除-查找操作

  2. 无论多少数据,插入和删除需要接近常量的时间:即O(1)的时间级。实际上,只需要几个机器指令即可完成。

  3. 哈希表的速度比树还要快,基本可以瞬间查找到想要的元素

  4. 哈希表相对于树来说编码要容易很多

哈希表相对于数组的一些不足:

  1. 哈希表中的数据是没有顺序的,所以不能以一种固定的方式来遍历其中的元素

  2. 通常情况下,哈希表中的key是不允许重复的,不能放置相同的key,用于保存不同的元素

  3. 空间利用率不高,底层使用的是数组,并且某些单元格没有被利用

哈希表是什么?

哈希表的一些概念

仍然需要解决的问题

解决冲突的方法

解决冲突常见的两种方案:

如下图所示,我们将每一个数字都对10进行取余操作,则余数的范围0~9作为数组的下标值。并且,数组每一个下标值对应的位置存储的不再是一个数字了,而是存储由经过取余操作后得到相同余数的数字组成的数组链表

JavaScript实现哈希表的方法

总结:链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据,而是一条链条,这条链条常使用的数据结构为数组或链表,两种数据结构查找的效率相当(因为链条的元素一般不会太多)。

开放地址法的主要工作方式是寻找空白的单元格来放置冲突的数据项。

JavaScript实现哈希表的方法

据探测空白单元格位置方式的不同,可分为三种方法:

可以看到随着装填因子的增加,平均探测长度呈线性增长,较为平缓。在开发中使用链地址法较多,比如Java中的HashMap中使用的就是链地址法

优秀的哈希函数

哈希表的优势在于它的速度,所以哈希函数不能采用消耗性能较高的复杂算法。提高速度的一个方法是在哈希函数中尽量减少乘法和除法

性能高的哈希函数应具备以下两个优点:

快速计算

霍纳法则:在中国霍纳法则也叫做秦九韶算法,具体算法为:

JavaScript实现哈希表的方法

求多项式的值时,首先计算最内层括号内一次多项式的值,然后由内向外逐层计算一次多项式的值。这种算法把求n次多项式f(x)的值就转化为求n个一次多项式的值。

变换之前

变换之后:

如果使用大O表示时间复杂度的话,直接从变换前的O(N2)降到了O(N)

均匀分布

为了保证数据在哈希表中均匀分布,当我们需要使用常量的地方,尽量使用质数;比如:哈希表的长度、N次幂的底数等。

Java中的HashMap采用的是链地址法,哈希化采用的是公式为:index = HashCode(key)&(Length-1)

即将数据化为二进制进行运算,而不是取余运算。这样计算机直接运算二进制数据,效率更高。但是JavaScript在进行叫大数据的运算时会出现问题,所以以下使用JavaScript实现哈希化时还是采用取余运算。

                    function HashTable() {
                // 存放相关的元素
                this.storage = [];
                // 存了多少数据
                this.count = 0;
                // 用于标记数组中一共存放了多少个元素
                this.limit = 7;
                
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法(霍纳算法)
                    // 哈希表的长度、N次幂的底数等尽量选取质数
                    for (var i = 0; i < str.length; i++) {
                        // 34 43 43 都是常用的底数
                        hashCode = 37 * hashCode + str.charCodeAt(i);
                    }
                    return hashCode % size;
                };
                // 插入和修改方法
                HashTable.prototype.put = function (key, value) {
                    // 根据key获取对应的index
                    var index = this.hashFunction(key, this.limit);
                    // 根据index取出对应的bucket
                    var bucket = this.storage[index];
                    if (bucket == null) {
                        bucket = [];
                        this.storage[index] = bucket;
                    }
                    // 判断是否是修改数据
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            tuple[1] == value;
                            return;
                        }
                    }
                    // 不是修改数据就添加数据
                    bucket.push([key, value]);
                    this.count++;
                    // 扩容
                    if (this.count > this.limit * 0.75) {
                        var newLimit = this.limit * 2;
                        var prime = this.getPrime(newLimit);
                        this.resize(prime);
                    }
                };
                // 获取
                HashTable.prototype.get = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            value == tuple[1];
                            return value;
                        }
                    }
                    return null;
                };
                // 删除
                HashTable.prototype.remove = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key) {
                            // 从i开始删除一个
                            bucket.splice(i, 1);
                            this.count--;
                            // 缩容
                            if (this.limit > 7 && this.count < this.limit * 0.25) {
                                var newLimit = Math.floor(this.limit / 2);
                                var prime = this.getPrime(newLimit);
                                this.resize(prime);
                            }
                            return tuple[1];
                        }
                    }
                    return null;
                };
                // 扩容
                HashTable.prototype.resize = function (newLimit) {
                    var oldStorage = this.storage;
                    // 充值所有的属性
                    this.storage = [];
                    this.count = 0;
                    this.limit = newLimit;
                    for (var i = 0; i < this.limit; i++) {
                        var bucket = oldStorage[i];
                        if (bucket == null) {
                            continue;
                        }
                        for (var j = 0; j < bucket.length; j++) {
                            var tuple = bucket[j];
                            this.put(tuple[0], tuple[1]);
                        }
                    }
                };
                // 为空?
                HashTable.prototype.isEmpty = function () {
                    return this.count > 0 ? false : true;
                };
                // size
                HashTable.prototype.size = function () {
                    return this.count;
                };
                // toString
                HashTable.prototype.toString = function () {
                    var str = '';
                    for (var i = 0; i < this.limit; i++) {
                        var arr = this.storage[i];

                        if (arr != undefined) {
                            str += '[';
                            for (var j = 0; j < arr.length; j++) {
                                var bucket = arr[j];

                                str += '[' + bucket[0] + ',' + bucket[1] + ']';
                                if (j != arr.length - 1) {
                                    str += ',';
                                }
                            }
                            str += ']';
                            if (i != this.limit - 1) {
                                str += ',';
                            }
                        } else {
                            str += '[]';
                            if (i != this.limit - 1) {
                                str += ',';
                            }
                        }
                    }

                    return str;
                };
                HashTable.prototype.isPrime = function (num) {
                    if (num <= 1) {
                        return false;
                    }
                    //1.获取num的平方根:Math.sqrt(num)
                    //2.循环判断
                    for (var i = 2; i <= Math.sqrt(num); i++) {
                        if (num % i == 0) {
                            return false;
                        }
                    }
                    return true;
                };

                //获取质数的方法
                HashTable.prototype.getPrime = function (num) {
                    //7*2=14,+1=15,+1=16,+1=17(质数)
                    while (!this.isPrime(num)) {
                        num++;
                    }
                    console.log(num);
                    return num;
                };
            }
            var hashTable = new HashTable();
            hashTable.put('q', 1);
            hashTable.put('w', 1);
            hashTable.put('e', 1);
            hashTable.put('r', 1);
            hashTable.put('t', 1);
            hashTable.put('y', 1);
            hashTable.put('z', 1);
            hashTable.put('x', 1);
            hashTable.put('c', 1);
            hashTable.put('v', 1);
            hashTable.put('b', 1);
            hashTable.put('n', 1);
            hashTable.remove('q');
            console.log(hashTable.toString());//[[w,1]],[[x,1]],[[y,1]],[[z,1]],[],[],[],[],[[n,1]],[],[],[],[[r,1]],[[b,1]],[[t,1],[c,1]],[],[[e,1],[v,1]]

JavaScript实现哈希表的方法

到此,相信大家对“JavaScript实现哈希表的方法”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-前端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯