热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

看完你就懂了!Java集合之Map接口详解

目录Java集合概览Java集合底层数据结构总结HashMap和Hashtable的区别HashMap和HashSet区别ConcurrentHashMap和Hashtable区别


目录



  • Java 集合概览

  • Java集合底层数据结构总结

  • HashMap 和 Hashtable 的区别

  • HashMap 和 HashSet 区别

  • ConcurrentHashMap 和 Hashtable 区别

  • 补充:Arraylist 与 LinkedList 区别


Java 集合概览


从下图可以看出,在 Java 中除了以 Map 结尾的类之外, 其他类都实现了 Collection 接口。并且,以 Map 结尾的类都实现了 Map 接口。



Java集合底层数据结构总结


1. List


存储的元素是有序的、可重复的。



  • ArraylistObject[] 数组

  • VectorObject[] 数组

  • LinkedList : 双向链表(JDK1.6 之前为循环链表,JDK1.7 取消了循环)


2. Set


存储的元素是无序的、不可重复的。



  • HashSet :无序,唯一,基于 HashMap 实现的,底层采用 HashMap 来保存元素

  • LinkedHashSetLinkedHashSetHashSet 的子类,并且其内部是通过 LinkedHashMap 来实现的。有点类似于 LinkedHashMap 其内部是基于 HashMap 实现一样

  • TreeSet :有序,唯一,红黑树


3. Map



  • HashMap :JDK1.8之前 HashMap 由数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突⽽存在的。JDK1.8以后在解决哈希冲突时有了变化, 当链表⻓度⼤于阈值(默认为8)时,将链表转化为红⿊树,以减少搜索时间

  • LinkedHashMapLinkedHashMap 继承⾃ HashMap ,所以它的底层仍然是基于数组和链表/红⿊树组成。另外, LinkedHashMap 在上面结构的基础上,增加了⼀条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。

  • Hashtable : 数组+链表组成的,数组是 Hashtable 的主体,链表则是主要为了解决哈希冲突而存在的

  • TreeMap : 红黑树


HashMap 和 Hashtable 的区别


1. 线程是否安全


HashMap 是非线程安全的。


HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过 synchronized 修饰。


2. 效率


因为线程安全的问题, HashMap 要比 HashTable 效率高一点。另外, HashTable 基本被淘汰,不要在代码中使用它。


3. 对 Null key 和 Null value 的支持


HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个。


HashTable 不允许有 null 键和 null 值,否则会抛出 NullPointerException


4. 初始容量大小


创建时如果不指定容量初始值


HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。


Hashtable 默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。


5. 每次扩充容量大小


创建时如果给定了容量初始值


HashMap 会将其扩充为 2 的幂次方大小


Hashtable 会直接使用你给定的大小


6. 底层数据结构


JDK1.8以后的 HashMap 在解决哈希冲突时有了变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。


补充为什么默认值是8:在8的时候,红黑树的平均查找长度是log(N)=3,而链表的平均查找长度为8/2=4。


Hashtable 则没有这样的机制。


HashMap 和 HashSet 区别


HashSet 底层就是基于 HashMap 实现的。 HashSet 的源码非常非常少,因为除了 clone()writeObject()readObject()HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。


HashMap


HashSet


实现了 Map 接口


实现 Set 接口


存储键值对


仅存储对象


调用 put()向 map 中添加元素


调用 add()方法向 Set 中添加元素


HashMap 使用键(Key)计算 hashcode


HashSet 使用成员对象来计算 hashcode 值,对于两个对象来说 hashcode 可能相同,所以 equals()方法用来判断对象的相等性


ConcurrentHashMap 和 Hashtable 区别


ConcurrentHashMapHashtable 的区别主要体现在实现线程安全的方式上不同。


1. 底层数据结构


JDK1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现,JDK1.8 采用的数据结构跟 HashMap 1.8 的结构一样,是数组+链表/红黑二叉树。


Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似,都是采用数组+链表的形式。


2. 实现线程安全的方式


JDK1.7 的 ConcurrentHashMap 通过分段锁实现线程安全,先对整个桶数组进行分割分段,每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据就不会存在锁竞争,提高并发访问率。



JDK1.8 的 ConcurrentHashMap 摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。 synchronized 只锁定当前链表或红黑树的首节点,整个看起来就像是优化过且线程安全的 HashMap
Hashtable 通过全表锁来实现线程安全,相当于给整个哈希表只加了一把锁, get / put 所有相关操作都是 synchronized 的。在多线程访问的时候,当一个线程访问或操作该对象,其他线程只能进入阻塞或轮询状态。比如某一线程使用 put 添加元素,那么其他线程不能使用 put 添加元素,也不能使用 get ,在并发场景中性能就会非常差。



补充:Arraylist 与 LinkedList 区别


1. 是否保证线程安全


ArrayListLinkedList 都是不同步的,也就是不保证线程安全;


但是 Vector 是线程安全的。


2. 底层数据结构


Arraylist 底层使用的是 Object 数组


LinkedList 底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环)。


3. 插入和删除是否受元素位置的影响


ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行 add(E e) 方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话( add(int index, E element) )时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。


LinkedList 采用链表存储,所以对于 add(E e) 方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话( (add(int index, E element) ) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。


4. 是否支持快速随机访问


ArrayList 支持快速随机访问。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) 方法)。


LinkedList 不支持高效的随机元素访问。


5. 内存空间占用


ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间


LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。




推荐阅读
  • 本文介绍了在 Java 编程中遇到的一个常见错误:对象无法转换为 long 类型,并提供了详细的解决方案。 ... [详细]
  • 在多线程并发环境中,普通变量的操作往往是线程不安全的。本文通过一个简单的例子,展示了如何使用 AtomicInteger 类及其核心的 CAS 无锁算法来保证线程安全。 ... [详细]
  • com.hazelcast.config.MapConfig.isStatisticsEnabled()方法的使用及代码示例 ... [详细]
  • JUC(三):深入解析AQS
    本文详细介绍了Java并发工具包中的核心类AQS(AbstractQueuedSynchronizer),包括其基本概念、数据结构、源码分析及核心方法的实现。 ... [详细]
  • 如何在Java中使用DButils类
    这期内容当中小编将会给大家带来有关如何在Java中使用DButils类,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。D ... [详细]
  • 本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用,包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]
  • 优化后的标题:深入探讨网关安全:将微服务升级为OAuth2资源服务器的最佳实践
    本文深入探讨了如何将微服务升级为OAuth2资源服务器,以订单服务为例,详细介绍了在POM文件中添加 `spring-cloud-starter-oauth2` 依赖,并配置Spring Security以实现对微服务的保护。通过这一过程,不仅增强了系统的安全性,还提高了资源访问的可控性和灵活性。文章还讨论了最佳实践,包括如何配置OAuth2客户端和资源服务器,以及如何处理常见的安全问题和错误。 ... [详细]
  • 深入解析CAS机制:全面替代传统锁的底层原理与应用
    本文深入探讨了CAS(Compare-and-Swap)机制,分析了其作为传统锁的替代方案在并发控制中的优势与原理。CAS通过原子操作确保数据的一致性,避免了传统锁带来的性能瓶颈和死锁问题。文章详细解析了CAS的工作机制,并结合实际应用场景,展示了其在高并发环境下的高效性和可靠性。 ... [详细]
  • 本文介绍了如何利用ObjectMapper实现JSON与JavaBean之间的高效转换。ObjectMapper是Jackson库的核心组件,能够便捷地将Java对象序列化为JSON格式,并支持从JSON、XML以及文件等多种数据源反序列化为Java对象。此外,还探讨了在实际应用中如何优化转换性能,以提升系统整体效率。 ... [详细]
  • 在Ubuntu上安装MySQL时解决缺少libaio.so.1错误及libaio在MySQL中的重要性分析
    在Ubuntu系统上安装MySQL时,遇到了缺少libaio.so.1的错误。本文详细介绍了如何解决这一问题,并深入探讨了libaio库在MySQL性能优化中的重要作用。对于初学者而言,理解这些依赖关系和配置步骤是成功安装和运行MySQL的关键。通过本文的指导,读者可以顺利解决相关问题,并更好地掌握MySQL在Linux环境下的部署与管理。 ... [详细]
  • 在Django中提交表单时遇到值错误问题如何解决?
    在Django项目中,当用户提交包含多个选择目标的表单时,可能会遇到值错误问题。本文将探讨如何通过优化表单处理逻辑和验证机制来有效解决这一问题,确保表单数据的准确性和完整性。 ... [详细]
  • 本文介绍了如何在 Spring 3.0.5 中使用 JdbcTemplate 插入数据并获取 MySQL 表中的自增主键。 ... [详细]
  • 原文网址:https:www.cnblogs.comysoceanp7476379.html目录1、AOP什么?2、需求3、解决办法1:使用静态代理4 ... [详细]
  • 本文深入解析了JDK 8中HashMap的源代码,重点探讨了put方法的工作机制及其内部参数的设定原理。HashMap允许键和值为null,但键为null的情况只能出现一次,因为null键在内部通过索引0进行存储。文章详细分析了capacity(容量)、size(大小)、loadFactor(加载因子)以及红黑树转换阈值的设定原则,帮助读者更好地理解HashMap的高效实现和性能优化策略。 ... [详细]
  • 深入剖析Java中SimpleDateFormat在多线程环境下的潜在风险与解决方案
    深入剖析Java中SimpleDateFormat在多线程环境下的潜在风险与解决方案 ... [详细]
author-avatar
低契一巴掌
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有