什么是哈希冲突?如何解决哈希冲突?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

相关文章

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结