什么是哈希冲突?如何解决哈希冲突?HashMap和TreeMap之间的区别?

2024-06-08 04:44

本文主要是介绍什么是哈希冲突?如何解决哈希冲突?HashMap和TreeMap之间的区别?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Map 和 Set 的概念

Map和Set是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关 。

为什么说它是一种专门用来进行搜索的数据结构呢?

我们应该都用过“遍历查找”、“二分查找”,这两种方式也都是用来对目标值进行搜索的,但是,这两种方式有些缺陷:

遍历查找需要一个一个的遍历,时间复杂度达到了O(N),比较消耗时间。

二分查找的时间复杂度是log(N),但是,二分查找的前提是,查找的元素必须是有序的。

例如在生活中,我们可能会通过学生的名字查找成绩,在通讯录中,通过名字查找电话号等场景,显然上述的查找方法就实现不了。

两种接口对应的模型

Map 和 Set 是两种不同的搜索模型,分别是 Key - Value 模型,纯 Key 模型

Key - Value 模型:一般要搜索的数据称为关键字(Key),和关键字相对应的称为值(Value)

例如:通过学生的名字查找对应的考试成绩,学生的名字就是Key,考试成绩就是Value。

纯 Key 模型:只含有 Key ,没有对应的 Value 值

例如:我想要快速的查找某个学生在这个班级中。

Map 的常用实现类:HashMap、TreeMap

Set 的常用实现类:HashSet、TreeSet

TreeMap 和 TreeSet 底层是搜索树

HashMap 和 HashSet 底层是哈希表

下面,来讲解一下 TreeMap 和 HashMap。

Map

Map是一个接口类,该类没有继承自Collection,该类中存储的是<K,V>结构的键值对,并且K一定是唯一的,不能重复。

Map 中的一些常用方法

方法解释
V get(Object key)返回 key 对应的 value
V getOrDefault(Object Key, V defaultValue)返回 key 对应的 value,如果 key 不存在,则返回默认值
V put(K key, V value)设置 key 对应的 value
V remove(Object key)删除 key 对应的映射关系
Set < K > keySet()返回所有 Key 的不重复集合
Collection< V > values()返回所有 value 的可重复集合
Set<Map.Entry<K,V>> entrySet()返回所有的 key-value 映射关系
boolean containsKey(Object key)判断是否包含 key
boolean containsValue(Object value)判断是否包含 value

Map.Entry<k, V>

**Map 是如何来存储 <K,V> 结构的键值对的呢?**Map 是通过 Map.Entry<K , V>进行存储的。

Map.Entry<K, V> 是 Map 内部定义了一个用来存放 <key, value> 键值对的内部接口,该接口种主要提供了 <key, value> 的获取,value 的设置以及key的比较方式。(这一点可以通过源码去查看)。

Map.Entry<K, V> 接口种的一些常用方法:

方法解释
K getKey()返回 Entry 中的key
V getValue()返回 Entry 中的 value
V setValue(V value)将键值对中的value替换成指定的value

TreeMap

TreeMap 是 Map 的一个实现类,底层结构是 “搜索树(红黑树)”,而搜**索树的性质是:左子树上的所有节点比根节点小,右子树上的所有节点都比根节点大,**所以,**每当向这个搜索树上添加一个元素时,都需要进行比较,**在上面也讲了,Map 是用 Map.Entry<K, V>,来存储键值对的,所以,搜索树上的每个元素都是一个 Map.Entry<K, V>,而在进行比较时,是根据 Map.Entry<K, V> 中的 key 进行比较的,这一点在源码中也可以看到。而且,在获取这个搜索树上的所有key时,还会对所有的key进行一个排序,如下代码:

        Map<String, Integer> map = new TreeMap<>();map.put("ggg", 3);map.put("ccc",2);map.put("aaa", 1);Set<Map.Entry<String, Integer>> entries = map.entrySet();for(Map.Entry e : entries) {//获取所有的KeySystem.out.println(e.getKey());}

在这里插入图片描述

总结:

  1. Map 是一个接口,不能直接实例化对象,只能实例化它的实现类 TreeMap 或者 HashMap 等
  2. Map 中存放键值对的key是唯一的,value 是可以重复的。
  3. 在 TreeMap 中插入键值对时,key 不能为空,否则就会抛 NullPointerException 异常,因为,它需要使用key进行比较,value 可以为空.
  4. Map 中的key可以全部分离出来,存储到Set中进行访问。
  5. Map中的value可以全部分离出来,存储到Collection的任意一个集合中。

HashMap

顺序结构以及平衡树中,元素关键码(key)与元素存储的位置之间没有对应的关系,意思就是:如果要找某一个key时,需要使用key进行多次比较来查找,而顺序结构的时间复杂度时O(n),平衡树的时间复杂度为树的高度O(logN),搜索效率取决于搜索过程中元素的比较次数。而哈希表就对搜索效率进行了优化。

哈希表:通过某种函数使元素的存储位置与它的关键码key之间能够建立一一映射的关系。

所以:

插入元素时:

根据待插入元素的关键码key,通过此函数计算出该元素的存储位置,然后进行存储。

搜索元素时:

根据待搜索元素的关键码key,按照同样的函数计算出元素的存储位置,然后就可以快速的查到该元素。

这种存储的方式就称为:哈希方法,哈希方法中使用的函数就是哈希函数,构造出来的结构就称为哈希表。

如下图:

在这里插入图片描述

哈希冲突

什么是哈希冲突?

哈希冲突:当多个不同的关键字key通过相同的哈希算法所计算出相同的哈希地址,称为哈希冲突。

如下图:

当通过相同的哈希算法计算44的哈希地址时,44的哈希地址就和4的哈希地址冲突了。

在这里插入图片描述

哈希冲突避免

当key值越来越多时,冲突的必然会发生的,就要想办法尽量去避免冲突,如以下两种方式:

哈希函数的设计

直接定制法,除留余数法,平方取中法等。

负载因子调节

散列表的载荷因子定义为:α = 填入表中的元素个数 / 散列表的长度

α 表示散列表装满程度的标志因子,由于散列表的长度是定值,α 与 填入表中的元素成正比,所以,α 越大,表示填入表中的元素越多,产生冲突的可能性就越大,反之,α越小,表示填入表中的元素就越少,产生冲突的可能性就越低,所以,Java限制了载荷因子为0.75,当 α 超过 0.75 时,散列表的长度就进行扩大。

哈希冲突的解决

解决哈希冲突的方法主要有两种:

  • 闭散列
  • 开散列

注意:哈希冲突是无法解决的,冲突是必然会发生的,这里说的解决冲突,意思是当冲突发生时,把当前发生的冲突现象给解决了,并不是说能够彻底性的解决冲突。

闭散列

闭散列:闭散列也叫开放地址法,当发生哈希冲突时,如果哈希表中还有空位置的话,就把当前 key 放在发生冲突位置的下一个位置上。那么如何寻找下一个位置呢???有两种方法:

  1. 线性探测

如下图:

当44和4发生冲突后,就会从4下标的位置向后寻找空位置,当找到空位置后,就进行存储。

在这里插入图片描述

但是,这种方式有一些缺陷:

  1. 发生冲突的元素堆积在了一块,因为发生冲突的元素会一直向后寻找空位置及进行存储。

  2. 当采用这种方式解决哈希冲突时,不能随便的物理删除哈希表中存在的元素,否则的话,就会影响其他元素的搜索,例如上图,如果删除了4,那么44查找起来就会收到影响。因此,线性探测采用的对要删除的元素进行标记的伪删除法。

  3. 二次探测

上述的线性探测容易造成冲突元素的堆积以及不能随便的物理删除哈希表中的元素,而二次探测就对这样的缺陷进行了改善,如下图:

在这里插入图片描述

研究表明:当表的长度为质数且表的负载因子α不超过0.5时,新的元素已经能够插入,而且任何一个位置都不会别探查两次,因此,只要表中有一半的空位置,就不会存在装满的问题,在搜索时可以不考虑装满的情况,但是在插入时,必须保证表的负载因子α不超过0.5,如果超过,就必须考虑增容。因此,闭散列最大的缺陷就是空间利用率低,这也是哈希的缺陷。

开散列(哈希桶)

开散列又称为链地址法,通过哈希函数对关键码计算出哈希地址,具有相同地址的关键码放在同一个集合中,这个集合就称为桶,再使用链表将桶中的元素给串联起来,链表的头节点存放在哈希表中,当查找某一个元素时,通过哈希地址再得到具体的位置,然后再对链表进行遍历查找,如下图:

在这里插入图片描述

HashMap 和 TreeMap 之间的区别

TreeMapHashMap
底层结构红黑树哈希桶
插入/删除/查找 时间复杂度O(logN)O(1)
是否有序关于Key有序无序
线程安全不安全不安全
插入/删除/查找 的区别需要通过元素比较通过哈希函数计算哈希地址
比较及重写必须能够进行比较,如果是自定义类型,必须重写equeals()方法自定义类型需要重写equals() 和 hashcode() 方法
应用场景需要key有序的情况下需要更高的查询效率场景下

这篇关于什么是哈希冲突?如何解决哈希冲突?HashMap和TreeMap之间的区别?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1041227

相关文章

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

SpringBoot整合Dubbo+ZK注册失败的坑及解决

《SpringBoot整合Dubbo+ZK注册失败的坑及解决》使用Dubbo框架时,需在公共pom添加依赖,启动类加@EnableDubbo,实现类用@DubboService替代@Service,配... 目录1.先看下公共的pom(maven创建的pom工程)2.启动类上加@EnableDubbo3.实

MySQL逻辑删除与唯一索引冲突解决方案

《MySQL逻辑删除与唯一索引冲突解决方案》本文探讨MySQL逻辑删除与唯一索引冲突问题,提出四种解决方案:复合索引+时间戳、修改唯一字段、历史表、业务层校验,推荐方案1和方案3,适用于不同场景,感兴... 目录问题背景问题复现解决方案解决方案1.复合唯一索引 + 时间戳删除字段解决方案2:删除后修改唯一字

JAVA覆盖和重写的区别及说明

《JAVA覆盖和重写的区别及说明》非静态方法的覆盖即重写,具有多态性;静态方法无法被覆盖,但可被重写(仅通过类名调用),二者区别在于绑定时机与引用类型关联性... 目录Java覆盖和重写的区别经常听到两种话认真读完上面两份代码JAVA覆盖和重写的区别经常听到两种话1.覆盖=重写。2.静态方法可andro

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

MyBatis中$与#的区别解析

《MyBatis中$与#的区别解析》文章浏览阅读314次,点赞4次,收藏6次。MyBatis使用#{}作为参数占位符时,会创建预处理语句(PreparedStatement),并将参数值作为预处理语句... 目录一、介绍二、sql注入风险实例一、介绍#(井号):MyBATis使用#{}作为参数占位符时,会