您现在的位置是:群英 > 开发技术 > web开发
用JavaScript怎么实现哈希表,哈希表优缺点是什么
Admin发表于 2022-05-14 17:49:1049 次浏览
在实际案例的操作过程中,我们可能会遇到“用JavaScript怎么实现哈希表,哈希表优缺点是什么”这样的问题,那么我们该如何处理和解决这样的情况呢?这篇小编就给大家总结了一些方法,具有一定的借鉴价值,希望对大家有所帮助,接下来就让小编带领大家一起了解看看吧。


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

  1. 它可以提供非常快速的插入-删除-查找操作
  2. 无论多少数据,插入和删除需要接近常量的时间:即O(1)的时间级。实际上,只需要几个机器指令即可完成。
  3. 哈希表的速度比树还要快,基本可以瞬间查找到想要的元素
  4. 哈希表相对于树来说编码要容易很多

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

  1. 哈希表中的数据是没有顺序的,所以不能以一种固定的方式来遍历其中的元素
  2. 通常情况下,哈希表中的key是不允许重复的,不能放置相同的key,用于保存不同的元素
  3. 空间利用率不高,底层使用的是数组,并且某些单元格没有被利用

哈希表是什么?

  • 哈希表并不好理解,不像数组、链表和树等可通过图形的形式表示其结构和原理。
  • 哈希表的结构就是数组,但它神奇之处在于对下标值的一种变换,这种变换我们可以称之为哈希函数,通过哈希函数可以获取HashCode

哈希表的一些概念

  • 哈希化:大数字转化成数组范围内下标的过程,称之为哈希化
  • 哈希函数:我们通常会将单词转化成大数字,把大数字进行哈希化的代码实现放在一个函数中,该函数就称为哈希函数
  • 哈希表:对最终数据插入的数组进行整个结构的封装,得到的就是哈希表

仍然需要解决的问题

  • 哈希化过后的下标依然可能重复,如何解决这个问题呢?这种情况称为冲突,冲突是不可避免的,我们只能解决冲突

解决冲突的方法

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

  • 方案一:链地址法拉链法);

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

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

  • 方案二:开放地址法

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

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

  • 线性探测
  • 二次探测
  • 再哈希法

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

优秀的哈希函数

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

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

  • 快速的计算
  • 均匀的分布
快速计算

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

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

变换之前

  • 乘法次数:n(n+1)/2次;
  • 加法次数:n次;

变换之后:

  • 乘法次数:n次;
  • 加法次数: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;
                /*
           设计哈希函数
           ①将字符串转成比较大的数字
           ②将大的数字hashCode压缩到数组范围之内
            */
                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怎么实现哈希表,哈希表优缺点是什么”的相关知识,感谢各位的阅读,想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会,如果想了解更多相关内容的文章,欢迎关注群英网络,小编每天都会为大家更新不同的知识。

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。

标签: 哈希表
相关信息推荐
2022-01-12 18:08:59 
摘要:linux中无法识别php命令怎么办?有一些朋友遇到linux下php命令无法使用的问题,这是怎么回事呢?首先我们需要测试是否添加php环境变量,接下来我们再一步步分析解决。下文的解决方法有一定的参考价值,需要的朋友可以了解看看。
2021-12-14 18:02:00 
摘要:这篇文章给大家分享的是pandas的apply()函数的使用,对大家学习和理解pandas的函数有一定的帮助,因此分享给大家做个参考,文中示例操作介绍的非常详细,那么感兴趣的朋友接下来一起跟随小编了解看看吧。
2022-04-28 17:48:14 
摘要:给大家带来一篇关于JavaScript实现百度搜索框的过程的相关教程文章,内容涉及到js百度搜索框效果、js百度搜索、js百度搜索框、基于JavaScript实现百度搜索框效果等相关内容,更多关于基于JavaScript实现百度搜索框效果的内容希望能够帮助到大家。
推荐内容
热门关键词
热门信息
群英网络助力开启安全的云计算之旅
立即注册,领取新人大礼包
  • 联系我们
  • 24小时售后:4006784567
  • 24小时TEL :0668-2555666
  • 售前咨询TEL:400-678-4567

  • 官方微信

    官方微信
Copyright  ©  QY  Network  Company  Ltd. All  Rights  Reserved. 2003-2019  群英网络  版权所有   茂名市群英网络有限公司
增值电信经营许可证 : B1.B2-20140078   粤ICP备09006778号
免费拨打  400-678-4567
免费拨打  400-678-4567 免费拨打 400-678-4567 或 0668-2555555
微信公众号
返回顶部
返回顶部 返回顶部