JavaScript实现数据结构与算法(三）哈希表

发布时间：2023-10-10 12:30

JavaScript实现数据结构与算法(三）哈希表

    • （三）哈希表
      • 1. 集合
        • 1.1 集合的特点
        • 1.2 JavaScript的封装方法
        • 1.3 集合常见操作
        • 1.4 集合的封装常见操作的代码实现
        • 1.5 集合间的操作
          • 1.5.1 并集
          • 1.5.2 交集
          • 1.5.3 差集
          • 1.5.4 子集
      • 2. 字典
        • 2.1 字典的特点
        • 2.2 字典和其他数据结构的关系
          • 2.2.1 字典与映射
          • 2.2.2 字典与数组
          • 2.2.2 字典与对象
      • 3. 哈希表
        • 3.1 优势
          • 3.1.1 数组的劣势
          • 3.1.2 哈希表的优势
          • 3.1.3哈希表的不足
        • 3.2 相关概念
          • 3.2.1 哈希化
          • 3.2.2 哈希函数
          • 3.2.3 哈希表
        • 3.3 解决哈希冲突的方法
          • 3.3.1 链地址法
          • 3.3.2 开放地址法
            • 3.3.2.1 线性探测法
            • 3.3.2.2 二次探测法
            • 3.3.2.3 再哈希法
        • 3.4 哈希化的效率
          • 3.4.1 装填因子
          • 3.4.2 装填因子与探测序列之间的关系
        • 3.5 优秀的哈希函数
          • 3.5.1 特点
          • 3.5.2 优化方法
        • 3.6 代码实现
          • 3.6.1 哈希函数的实现
          • 3.6.2 创建哈希表
          • 3.6.3 哈希表的操作
          • 3.6.4 哈希表的扩容

（三）哈希表

学习笔记：coderwhy的JavaScript实现数据结构与算法的课程
其他章节笔记链接
1. 重要性
2. 线性结构
3. 哈希表【本文】
4. 树结构
5. 图结构
6. 排序和搜索

1. 集合

1.1 集合的特点

\"在这里插入图片描述\"
\"在这里插入图片描述\"

1.2 JavaScript的封装方法

\"JavaScript实现数据结构与算法(三）哈希表_第1张图片\"

1.3 集合常见操作

\"JavaScript实现数据结构与算法(三）哈希表_第2张图片\"
\"JavaScript实现数据结构与算法(三）哈希表_第3张图片\"

1.4 集合的封装常见操作的代码实现

<!DOCTYPE html>
<html lang=\"en\">
<head>
    <meta charset=\"UTF-8\">
    <title>封装集合</title>
</head>
<body>
<script>
    // 封装集合类
    function Set() {
        // 属性
        this.items = {}  // 使用了js的object对象
        // 方法
        // add 方法
        Set.prototype.add = function (value) {
            // 判断集合中是否已经包含了该元素
            if(this.has(value)){
                return false; // 添加失败
            }else {
                // 将元素添加到集合中
                this.items[value] = value; // 这里是把属性和属性值都设置为要添加的元素
                return true;
            }
        } ;
        // has方法
        Set.prototype.has = function (value) {
            return this.items.hasOwnProperty(value);
        };
        // remove方法
        Set.prototype.remove = function (value) {
            // 1. 该集合中是否包含该元素
            if(!this.has(value)){
                return false;
            }else{
                // 2. 将元素从属性中删除
                delete this.items[value];
                return true;
            };

        };
        // clear 方法
        Set.prototype.clear = function () {
            this.items = {}
        };

        // size方法
        Set.prototype.size = function () {
            return Object.keys(this.items).length;
        };

        // 获取集合中所有的值
        Set.prototype.values = function () {
            return Object.keys(this.items);  // 获取object中的所有key
        }
    };

    // 测试Set类

    // 1. 创建Set类对象
    var set = new Set();

    // 2. 添加元素
    alert(set.add(\'abc\'));
    alert(set.add(\'abc\'));
    alert(set.add(\'cba\'));
    alert(set.add(\'nba\'));
    alert(set.add(\'mba\'));
    alert(set.values());

    // 3. 删除元素
    alert(set.remove(\'mba\'));
    alert(set.remove(\'mba\'));
    alert(set.values());

    // 4. has方法
    alert(set.has(\'abc\'));
    alert(set.has(\'aaabc\'));

    // 5. 获取元素的个数
    alert(set.size());

    // 6. clear 方法
    set.clear();
    alert(set.size());
</script>
</body>
</html>

1.5 集合间的操作

\"JavaScript实现数据结构与算法(三）哈希表_第4张图片\"

1.5.1 并集

（1） 定义
\"JavaScript实现数据结构与算法(三）哈希表_第5张图片\"
（2）代码解析
\"JavaScript实现数据结构与算法(三）哈希表_第6张图片\"
（3）代码实现

// 并集
        Set.prototype.union = function (otherSet) {
            // this:集合对象A
            // otherSet: 集合对象B
            // 1. 创建新的集合
            var unionSet = new Set();

            // 2.  将A集合中的所有元素添加到新集合中
            var values = this.values();
            for (var i = 0; i < values.length; i++){
                unionSet.add(values[i]);
            };

            // 3. 取出B集合中的元素，判断是否需要加到新集合
            values = otherSet.values();
            for (var i = 0; i < values.length; i++){
                unionSet.add(values[i]);
            };
            return unionSet;
        };
1.5.2 交集

（1） 定义
\"JavaScript实现数据结构与算法(三）哈希表_第7张图片\"（2）代码解析
\"JavaScript实现数据结构与算法(三）哈希表_第8张图片\"
（3）代码实现

 // 交集
        Set.prototype.intersection = function (otherSet) {
            // this:集合对象A
            // otherSet: 集合对象B
            // 1. 创建新的集合
            var interSet = new Set();

            // 2， 从A中取出一个个元素，判断是否同时存在于集合B中，存在放入新集合中
            var values = this.values();
            for (var i = 0; i < values.length; i++){
               var item = values[i];
               if (otherSet.has(item)){
                   interSet.add(item);
               }
            };

            return interSet;

        };
1.5.3 差集

（1） 定义
\"JavaScript实现数据结构与算法(三）哈希表_第9张图片\"
（2）代码解析
\"JavaScript实现数据结构与算法(三）哈希表_第10张图片\"

（3）代码实现

// 差集
        Set.prototype.difference = function (otherSet) {
            // this:集合对象A
            // otherSet: 集合对象B
            // 1. 创建新的集合
            var differSet = new Set();

            // 2， 从A中取出一个个元素，判断是否不存在于集合B中，存在放入新集合中
            var values = this.values();
            for (var i = 0; i < values.length; i++){
                var item = values[i];
                if (!otherSet.has(item)){
                    differSet.add(item);
                }
            };

            return differSet;
        }
1.5.4 子集

（1） 定义
\"JavaScript实现数据结构与算法(三）哈希表_第11张图片\"
（2）代码解析
\"JavaScript实现数据结构与算法(三）哈希表_第12张图片\"

（3）代码实现

// 子集
        Set.prototype.subset = function (otherSet) {
            // this:集合对象A
            // otherSet: 集合对象B
            // 判断集合A是不是集合B的子集
            // 遍历集合A中所有的元素，如果发现，集合A中的元素，在集合B中不存在，那么false
            // 如果遍历完成整个集合，依然没有返回false,那么返回true即可
            var values = this.values();
            for (var i = 0; i < values.length; i++){
                var item = values[i];
                if (!otherSet.has(item)){
                    return false;
                }
            };
            return true;
        };

2. 字典

2.1 字典的特点

存储的是键值对
\"JavaScript实现数据结构与算法(三）哈希表_第13张图片\"

2.2 字典和其他数据结构的关系

2.2.1 字典与映射

\"在这里插入图片描述\"

2.2.2 字典与数组

\"在这里插入图片描述\"

2.2.2 字典与对象

\"在这里插入图片描述\"

3. 哈希表

是基于数组实现的，但是比起数组又有自己的优势

3.1 优势

3.1.1 数组的劣势

（1）数组进行插入操作时，效率比较低
（2）数组进行查找操作的效率
1）若是基于索引进行查找效率非常高
2）若是基于内存去查找(比如name=‘why’)，效率非常低
（3）数组进行删除操作，效率也不高。

3.1.2 哈希表的优势

\"JavaScript实现数据结构与算法(三）哈希表_第14张图片\"

3.1.3哈希表的不足

\"在这里插入图片描述\"

3.2 相关概念

3.2.1 哈希化

将大数字转化成数组范围内的下标的过程。

3.2.2 哈希函数

将单词转化成大数字,大数字在进行哈希化的代码实现放在一个函数中，这个函数称之为哈希函数。

3.2.3 哈希表

最终将数据插入到的这个数组，对整个结构的封装, 称之为一个哈希表。

3.3 解决哈希冲突的方法

3.3.1 链地址法

\"JavaScript实现数据结构与算法(三）哈希表_第15张图片\"
\"JavaScript实现数据结构与算法(三）哈希表_第16张图片\"

3.3.2 开放地址法

\"JavaScript实现数据结构与算法(三）哈希表_第17张图片\"

3.3.2.1 线性探测法

\"JavaScript实现数据结构与算法(三）哈希表_第18张图片\"\"JavaScript实现数据结构与算法(三）哈希表_第19张图片\"

3.3.2.2 二次探测法

\"JavaScript实现数据结构与算法(三）哈希表_第20张图片\"

3.3.2.3 再哈希法

\"JavaScript实现数据结构与算法(三）哈希表_第21张图片\"

3.4 哈希化的效率

3.4.1 装填因子

\"JavaScript实现数据结构与算法(三）哈希表_第22张图片\"

3.4.2 装填因子与探测序列之间的关系

（1）线性探测法
\"JavaScript实现数据结构与算法(三）哈希表_第23张图片\"
（2）二次探测和再哈希法\"JavaScript实现数据结构与算法(三）哈希表_第24张图片\"
（3）链地址法\"JavaScript实现数据结构与算法(三）哈希表_第25张图片\"

3.5 优秀的哈希函数

3.5.1 特点

\"JavaScript实现数据结构与算法(三）哈希表_第26张图片\"

3.5.2 优化方法

（1） 霍纳法则
\"JavaScript实现数据结构与算法(三）哈希表_第27张图片\"
（2）均匀分布
\"JavaScript实现数据结构与算法(三）哈希表_第28张图片\"
\"JavaScript实现数据结构与算法(三）哈希表_第29张图片\"

3.6 代码实现

3.6.1 哈希函数的实现
// 设计哈希函数
    // 1. 将字符串转换成比较大的数字：hasCode
    // 2. 将大的数字hasCode压缩到数组范围之内
    function hashFunc(str,size){
        // 1. 定义hasCode变量
        var hasCode = 0;

        // 2. 霍纳算法,来计算hasCode的值
        // cats -> Unicode编码
        for (var i = 0; i < str.length; i++){
            hasCode = 37 * hasCode + str.charCodeAt(i);
        };

        // 3. 取余操作
        var index = hasCode % size;

        return index;
    }
    // 测试哈希函数
    alert(hashFunc(\'abc\',7)); // 4
    alert(hashFunc(\'cba\',7)); // 3
    alert(hashFunc(\'nba\',7)); // 5
    alert(hashFunc(\'mba\',7)); // 1
3.6.2 创建哈希表

（1）实现方法：链地址法
\"在这里插入图片描述\"
（2）代码解析：
\"JavaScript实现数据结构与算法(三）哈希表_第30张图片\"

3.6.3 哈希表的操作

（1）插入和修改数据
\"JavaScript实现数据结构与算法(三）哈希表_第31张图片\"
（2）完整代码实现

<!DOCTYPE html>
<html lang=\"en\">
<head>
    <meta charset=\"UTF-8\">
    <title>哈希表实现</title>
</head>
<body>
<script>
    // 封装哈希表类
    function HashTable() {
        // 属性
        this.storage = []; // 所有元素的都是放到这个数组中
        this.count = 0; // 记录哈希表当前存放的数字个数，用来计算装载因子(loadFactor)
        // loadFactor > 0.75 需要对数组进行扩容
        // loadFactor < 0.25 需要对数组进行缩小
        this.limit = 0 ; // 用于记录数组的长度

        // 方法
        // 哈希函数
        HashTable.prototype.hashFunc = function(str,size){
            // 1. 定义hasCode变量
            var hasCode = 0;

            // 2. 霍纳算法,来计算hasCode的值
            // cats -> Unicode编码
            for (var i = 0; i < str.length; i++){
                hasCode = 37 * hasCode + str.charCodeAt(i);
            };

            // 3. 取余操作
            var index = hasCode % size;

            return index;
        };

        // 插入&修改操作
        HashTable.prototype.put = function (key,value) {
            // 1. 根据key获取对应的index
            var index = this.hashFunc(key,this.limit);

            // 2. 根据index取出对应的bucket
            var bucket = this.storage[index];

            // 3. 判断该bucket还是否为null
            if (bucket == null){
                bucket = [];
                this.storage[index] = bucket;
            };

            // 4. 判断是否是修改数据
            for (var i = 0; i < bucket.length; i++){
              var tuple = bucket[i];
              if(tuple[0] == key){
                  tuple[1] = value;
                  return
              };
            };
            // 5. 进行添加操作
            bucket.push([key,value]);
            this.count += 1;

        };

        // 获取操作
        HashTable.prototype.get = function (key) {
            // 1. 根据key获取对应的index
            var index = this.hashFunc(key,this.limit);

            // 2. 根据index取出对应的bucket
            var bucket = this.storage[index];

            // 3. 判断该bucket还是否为null
            if (bucket == null){
                return null;
            };

            // 4. 有bucket，那么就进行线性查找
            for (var i = 0; i < bucket.length; i++){
                var tuple = bucket[i];
                if(tuple[0] == key){
                    return tuple[1];
                };
            };

            // 5. 依然没有找到, 那么返回null
            return null;
        };

        //  删除操作
        HashTable.prototype.remove = function (key) {
            // 1. 根据key获取对应的index
            var index = this.hashFunc(key,this.limit);

            // 2. 根据index取出对应的bucket
            var bucket = this.storage[index];

            // 3. 判断该bucket还是否为null
            if (bucket == null){
                return null;
            };

            // 4. 有bucket，那么就进行线性查找,并且删除
            for (var i = 0; i < bucket.length; i++){
                var tuple = bucket[i];
                if(tuple[0] == key){
                    bucket.splice(i,1);
                    this.count--;
                    return tuple[1];
                };
            };

            // 5. 依然没有找到, 那么返回null
            return null;
        };

        // 其他方法
        // 判断哈希表是否为空
        HashTable.prototype.isEmpty = function (){
            return this.count == 0;
        };

        // 获取哈希表中元素的个数
        HashTable.prototype.size = function (){
            return this.count ;
        };

    }

    // 测试哈希表

    // 1. 创建哈希表
    var ht = new HashTable();

   // 2. 插入数据
    ht.put(\'abc\',\'123\');
    ht.put(\'cba\',\'321\');
    ht.put(\'nba\',\'521\');
    ht.put(\'mba\',\'520\');

    // 3. 获取数据
    alert(ht.get(\'abc\'));

    // 4. 修改方法
    ht.put(\'abc\',\'111\');
    alert(ht.get(\'abc\'));

    // 5. 删除方法
    ht.remove(\'abc\');
    alert(ht.get(\'abc\'));
    


</script>
</body>
</html>
3.6.4 哈希表的扩容

（1） 扩容的原因
\"JavaScript实现数据结构与算法(三）哈希表_第32张图片\"

（2） 扩容的方法
\"JavaScript实现数据结构与算法(三）哈希表_第33张图片\"
（3） 什么情况下进行扩容
\"在这里插入图片描述\"
（4）代码实现

// 哈希表的扩容/缩容
        HashTable.prototype.resize = function (newLimit) {
            // 1. 保存旧的数组内容
            var oldStorage = this.storage;

            // 2. 重置所有的属性
            this.storage = [];
            this.count = 0;
            this.limit = newLimit;

            // 3. 遍历oldStorage中所有的bucket
            for (var i = 0; i < oldStorage.length; i++){
                // 3.1 取出对应的
                var bucket = oldStorage[i];

                // 3.2 判断bucket是否为null
                if (bucket == null){
                    continue;
                }

                // 3.3 bucket中有数据，那么取出数据，重新插入
                for (var j = 0 ;j <bucket.length; j++){
                    var tuple = bucket[j];
                    this.put(tuple[0],tuple[1]);

                }
            };

        }

—————————————————————————————————————————
如果我的文章能帮你节约20秒，就请你为我的文章点个赞吧！

相关推荐

轻量级 Web 组件编译器 — Stencil

基于eBPF的云原生可观测性开源项目Kindling之eBPF基础设施库技术选型

基于.Net C# 通信开发-串口调试助手

C语言中的表达式求值

微信小程序配置-------页面配置, 详细配置 全局配置 局部配置

阿里云ACE适合什么人群？考试价格怎么样？

Python常用编码的区别介绍

奥比中光成功登陆科创板，董事长黄源浩致辞：打造最好的3D“慧眼”，看懂世界，照亮未来

OpenSea合约深度解析——atomicMatch_ 篇

FPGA学习笔记（FPGA基础知识）

TCP/IP协议常见漏洞类型

#nginx学习(5)#nginx的七层负载均衡和四层负载均衡配置

redis 发布和订阅 持久化 事务 缓存问题

什么是Docker? Docker能做什么 ？

超详细教程，一文入门Istio架构原理及实战应用

kafka笔记3--快速部署KRaft版本的kafka3.1.1

从零开始完整开发基于websocket的在线对弈游戏【五子棋】，只用几十行代码完成全部逻辑。

细粒度分析--WS-DAN

【毕业设计】python opencv 深度学习 指纹识别算法实现

java获取IP归属地全网显示开源库使用

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网，如有侵权请联系：561261067@qq.com

桂ICP备16001015号