不允许你还没有了解哈希表、哈希桶、哈希冲突的解决,如何避免冲突

✏️✏️✏️今天给各位带来的是哈希桶、哈希冲突方面的知识。

清风的CSDN博客

😛😛😛希望我的文章能对你有所帮助,有不足的地方还请各位看官多多指教,大家一起学习交流!

动动你们发财的小手,点点关注点点赞!在此谢过啦!哈哈哈!😛😛😛

目录

 一、哈希表

1.1 概念

1.2 冲突

1.2.1 冲突概念

1.2.2 冲突避免 

1.2.3 冲突避免-哈希函数设计 

1.2.4 负载因子调节 

1.2.5 冲突解决-闭散列

 1.2.6 冲突解决-开散列

 1.2.7 哈希桶K-V型实现

1.3 性能分析 


 一、哈希表

1.1 概念

顺序结构以及平衡树 中,元素关键码与其存储位置之间没有对应的关系,因此在 查找一个元素时,必须要经过关键 码的多次比较 顺序查找时间复杂度为 O(N), 平衡树中为树的高度,即 O(\log_{2}N ),搜索的效率取决于搜索过程中元素的比较次数。

  理想的搜索方法 :可以不经过任何比较,一次直接从表中得到要搜索的元素 。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。  

 当向该结构中:

  • 插入元素:根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
  • 搜索元素:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。
该方式即为  哈希(散列)  方法, 哈希方法中使用的转换函数称为哈希 ( 散列 ) 函数,构造出来的结构称为哈希表 (Hash Table)( 或者称散列表 )

例如:数据集合 {1 7 6 4 5 9}
哈希函数设置为: hash(key) = key % capacity ; capacity 为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快。 问题是:按照上述哈希方式,向集合中插入元素44 ,会出现什么问题?这就引出了哈希冲突的概念。

1.2 冲突

1.2.1 冲突概念

对于两个数据元素的关键字Ki和Kj  (i != j) ,有  Ki != Kj,但有:Hash( Ki) == Hash(Kj ),即:不同关键字通过相同哈 希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞 把具有不同关键码而具有相同哈希地址的数据元素称为 同义词  。

1.2.2 冲突避免 

首先,我们需要明确一点,由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一个问题, 冲突的发生是必然的 ,但我们能做的应该是尽量的 降低冲突率。

1.2.3 冲突避免-哈希函数设计 

引起哈希冲突的一个原因可能是: 哈希函数设计不够合理
哈希函数设计原则:
  • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单

常见哈希函数: 

直接定制法--(常用)
取关键字的某个线性函数为散列地址: Hash Key = A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况。
除留余数法--(常用)
设散列表中允许的 地址数为 m ,取一个不大于 m ,但最接近或者等于 m 的质数 p 作为除数,按照哈希函数: Hash(key) = key% p(p<=m), 将关键码转换成哈希地址。
平方取中法
假设关键字为 1234 ,对它平方就是 1522756 ,抽取中间的 3 227 作为哈希地址; 再比如关键字为 4321 ,对它平方就是18671041 ,抽取中间的 3 671( 710) 作为哈希地址 平方取中法比较适合:不知道关键字的分 布,而位数又不是很大的情况。 

折叠法 

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况  。 

随机数法
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 H(key) = random(key), 其中 random为随机数函数。通常应用于关键字长度不等时采用此法

数学分析法 

设有 n d 位数,每一位可能有 r 种不同的符号,这 r 种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。例如:

假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前 7 位都是 相同的,那么我们可以选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还可以对抽取出来的数字进行反转( 如1234改成 4321) 、右环位移 ( 1234 改成 4123) 、左环移位、前两数与后两数叠加 ( 1234 改成 12+34=46) 等方法。 数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突 。

1.2.4 负载因子调节 

 负载因子和冲突率的关系粗略演示:

 所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。

1.2.5 冲突解决-闭散列

 解决哈希冲突两种常见的方法是:开散列和闭散列。

闭散列: 

闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以 key 存放到冲突位置中的 下一个 空位置中去。 那如何寻找下一个空位置呢?

  •  线性探测:比如上面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。那么就从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他
元素的搜索。比如删除元素 4 ,如果直接删除掉, 44 查找起来可能会受影响。因此线性探测采用标
记的伪删除法来删除一个元素。

  • 二次探测  
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:
Hi= (H0+i^2)%m 或者:Hi= (H0-i^2)%m其中: i = 1,2,3… ,H0是通过散列函数Hash(x) 对元素的关键码 key 进行计算得到的位置,m是表的大小。 对于文章开头的表, 如果要插入 44 ,产生冲突,使用解决后的情况为:

研究表明:当表的长度为质数且表装载因子 a 不超过 0.5 时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a 不超过 0.5 ,如果超出必须考虑增容。

因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。

 1.2.6 冲突解决-开散列

开散列法又叫链地址法 ( 开链法 ) ,首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

 从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。 开散列,可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

那如果冲突严重,就意味着小集合的搜索性能其实也是不佳的,这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化,例如:
  •  每个桶的背后是另一个哈希表
  • 每个桶的背后是一棵搜索树

 1.2.7 哈希桶K-V型实现

类的基本定义:

public class Hash_Map<K,V> {

    static  class Node<K,V>{
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node<K,V>[] array;
    public int usedSize;//记录当前存放的元素个数
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子

    public Hash_Map(){
        array=(Node<K, V>[]) new Node[10];
    }
}

存放元素:

    public void put(K key, V val){
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K,V> cur = array[index];
        while (cur!=null){
            if(cur.key.equals(key)){
                cur.val=val;
                return;
            }
            cur = cur.next;
        }
        Node<K,V> node = new Node<>(key,val);
        node.next=array[index];
        array[index]=node;
        usedSize++;
        if(doLOAD_FACTOR()>DEFAULT_LOAD_FACTOR){
            resize();
        }
    }
    //计算当前负载因子
    private float doLOAD_FACTOR(){
        return usedSize*1.0f / array.length;
    }  
    //如果哈希桶已满,扩容后重新哈希
    private void resize(){
        Node<K,V>[] newArray = new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur = array[i];
            while (cur!=null){
                //先生成整数,调用hashCode
                Node<K,V> curNext = cur.next;
                int newHash = cur.key.hashCode();
                int newIndex = newHash % newArray.length;
                cur.next = newArray[newIndex];
                cur = curNext;
            }
        }
        array = newArray;
    }

获取key位置的val值:

    public V getValue(K key){
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K,V> cur = array[index];
        while (cur!=null){
            if(cur.key.equals(key)){//引用类型不可使用等号比较!!!!!!
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }

1.3 性能分析 

虽然哈希表一直在和冲突做斗争,但在实际使用过程中,我们认为哈希表的冲突率是不高的,冲突个数是可控的,也就是每个桶中的链表的长度是一个常数,所以,通常意义下,我们认为哈希表的插入 / 删除 / 查找时间复杂度是 O(1)

希望各位看官读完文章后,能够有所提升。

🎉好啦,今天的分享就到这里!!

创作不易,还希望各位大佬支持一下!

👍点赞,你的认可是我创作的动力!

⭐收藏,你的青睐是我努力的方向!

✏️评论:你的意见是我进步的财富!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/160583.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

实用篇-ES-DSL查询文档

数据的存储不是目的&#xff0c;我们希望从海量的酒店数据中检索出需要的信息&#xff0c;这就是ES的搜索功能 官方文档: https://elastic.co/guide/en/elasticsearch/reference/current/query-dsl.html#query-dsl。DSL是用来查询文档的 Elasticsearch提供了基于JSON的DSL来定…

vite vue3配置eslint和prettier以及sass

准备 教程 安装eslint 官网 vue-eslint ts-eslint 安装eslint yarn add eslint -D生成配置文件 npx eslint --init安装其他插件 yarn add -D eslint-plugin-import eslint-plugin-vue eslint-plugin-node eslint-plugin-prettier eslint-config-prettier eslint-plugin…

【数据结构】图的存储结构及实现(邻接表和十字链表)

一.邻接矩阵的空间复杂度 假设图G有n个顶点e条边&#xff0c;则存储该图需要O&#xff08;n^2) 不适用稀疏图的存储 二.邻接表 1.邻接表的存储思想&#xff1a; 对于图的每个顶点vi&#xff0c;将所有邻接于vi的顶点链成一个单链表&#xff0c;称为顶点vi的边表&#xff08…

C/C++ 运用VMI接口查询系统信息

Windows Management Instrumentation&#xff08;WMI&#xff09;是一种用于管理和监视Windows操作系统的框架。它为开发人员、系统管理员和自动化工具提供了一种标准的接口&#xff0c;通过这个接口&#xff0c;可以获取有关计算机系统硬件、操作系统和应用程序的信息&#xf…

PS学习笔记——新建文档/修改文档

文章目录 新建文档文档属性像素/分辨率颜色模式背景内容高级选项存储预设 修改文档 新建文档 方法一&#xff1a;ctrlN快捷键可直接打开新建文档界面 方法二&#xff1a;点击菜单栏中 文件->新建&#xff0c;即可打开新建文档界面 文档参数可按需调节(标题可以提前设定或者…

face_recognition:高准确率、简单易用的人脸识别库 | 开源日报 No.79

ageitgey/face_recognition Stars: 49.8k License: MIT 这个项目是一个使用 Python 编写的人脸识别库&#xff0c;可以从图片中识别和操作人脸。它基于 dlib 开发&#xff0c;并采用深度学习技术构建了最先进的人脸识别模型&#xff0c;在 Labeled Faces in the Wild 数据集上…

Redis(消息队列Stream)

Stream是一个轻量级的消息队列。 Redis中Stream的作用是提供一种高效的消息传递机制&#xff0c;允许多个消费者并行地消费消息&#xff0c;并且不会重复消费已经处理过的消息。它可以用于实现分布式任务队列、日志收集、实时数据处理等场景。Redis中的Stream支持多个消费者组…

Python数据分析实战① Python实现数据可视化

文章目录 一、数据可视化介绍二、matplotlib和pandas画图1.matplotlib简介和简单使用2.matplotlib常见作图类型3.使用pandas画图4.pandas中绘图与matplotlib结合使用 三、订单数据分析展示四、Titanic灾难数据分析显示 一、数据可视化介绍 数据可视化是指将数据放在可视环境中…

6.2 List和Set接口

1. List接口 List接口继承自Collection接口&#xff0c;List接口实例中允许存储重复的元素&#xff0c;所有的元素以线性方式进行存储。在程序中可以通过索引访问List接口实例中存储的元素。另外&#xff0c;List接口实例中存储的元素是有序的&#xff0c;即元素的存入顺序和取…

【Linux网络编程】高级I/O

目录 五种I/O模型 阻塞和非阻塞 非阻塞I/O I/O多路复用之Select、Poll、与Epoll 本文目的是深入浅出理解高级I/O相关的知识&#xff0c;结尾附上代码加深理解相关知识。 五种I/O模型 1.阻塞I/O&#xff1a;在内核将数据准备好之前&#xff0c;系统调用会一直等待。所有的套…

【踩坑笔记】国科GK7202V300芯片开发常见问题解决办法

国科Linux芯片开发常见问题&解决办法 0.读前须知 不管什么时候&#xff0c;下载程序还是啥&#xff0c;一定要检查路径&#xff01;&#xff01;&#xff01;别问我为什么&#xff0c;呜呜呜~ tips&#xff1a;该芯片是仿造海思的产品&#xff0c;所以&#xff0c;有些不…

cp: can‘t stat ‘/usr/share/zoneinfo/Asia/Shanghai‘: No such file or directory

目录 问题描述问题分析解决方案容器时区验证 问题描述 使用下面的 Dockerfile 为 youlai-boot 项目制作镜像设置容器时区报错。 # 基础镜像 FROM openjdk:17-jdk-alpine # 时区修改 RUN /bin/cp /usr/share/zoneinfo/Asia/Shanghai /etc/localtime \&& echo Asia/Sha…

【每周一测】Java阶段三阶段考试

目录 1、SpringBoot在整合RabbitMQ时需要导入的包是 2、下列关于RabbitMQ的confirm消息确认机制解释说明正确的是 3、关于SpringBoot的配置文件&#xff0c;以下说法正确的是&#xff08;&#xff09; 4、变量命名规范说法正确的是? 5、哪个关键字可以对对象加互斥锁&…

计算机视觉的应用18-一键抠图人像与更换背景的项目应用,可扩展批量抠图与背景替换

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下计算机视觉的应用18-一键抠图人像与更换背景的项目应用&#xff0c;可扩展批量抠图与背景替换。该项目能够让你轻松地处理和编辑图片。这个项目的核心功能是一键抠图和更换背景。这个项目能够自动识别图片中的主体&…

医院绩效考核系统源码 医院绩效考核系统方案

医院绩效考核系统源码 医院绩效考核系统是现代医院管理的重要方法和科学的管理工具。良好的绩效管理&#xff0c;有助于带动全院职工的工作积极性&#xff0c;有助于提高工作效率、提高医疗质量、改善服务水平、降低运营成本&#xff0c;全面提升医院的精细化管理水平。 医院绩…

Flask学习一:概述

搭建项目 安装框架 pip install Flask第一个程序 from flask import Flaskapp Flask(__name__)app.route(/) def hello_world():return "Hello World"if __name__ __main__:app.run()怎么说呢&#xff0c;感觉还不错的样子。 调试模式 if __name__ __main__:a…

后端老项目迁移方法

老项目迁移方法 需求&#xff1a; 因某个模块MySQL表结构、表关系 错乱复杂&#xff0c;而且其他模块的代码也在操作这个模块的数据库 耦合严重 导致Web工程代码紊乱、不易理解、性能低下&#xff0c; 故在 系统由A JavaWeb工程迁移至B工程 时&#xff0c;重构MySQL表结构、表…

VS中修改解决方案名称和项目名称

如何修改visual studio2019中的项目名 - 知乎 (zhihu.com) 查了很多&#xff0c;还是这个可行。虽然文中说不是最简单的&#xff0c;但在所查找资料中是可行且最简单的。 要点主要是&#xff1a; 1、比如我们复制一个解决方案&#xff0c;最好是带代码哈&#xff0c;也就是添…

ToolJet:开源低代码框架,轻松构建复杂可响应界面 | 开源日报 No.78

ToolJet/ToolJet Stars: 25.0k License: AGPL-3.0 ToolJet 是一个开源的低代码框架&#xff0c;可以通过最小化工程投入来构建和部署内部工具。ToolJet 的拖放式前端构建器允许您在几分钟内创建复杂、响应式的前端界面。此外&#xff0c;您还可以集成各种数据源&#xff0c;包…

java使用 TCP 的 Socket API 实现客户端服务器通信

一&#xff1a;什么是 Socket(套接字) Socket 套接字是由系统提供于网络通信的技术, 是基于 TCP/IP 协议的网络通信的基本操作&#xff0c;要进行网络通信, 需要有一个 socket 对象, 一个 socket 对象对应着一个 socket 文件, 这个文件在 网卡上而不是硬盘上, 所以有了 sokcet…