HashMap、HashTable、ConcurrentHashMap 之间的区别

这篇具有很好参考价值的文章主要介绍了HashMap、HashTable、ConcurrentHashMap 之间的区别。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

HashMap、HashTable、ConcurrentHashMap 之间的区别

哈喽,大家好~我是保护小周ღ,本期为大家带来的是 HashMap、HashTable、ConcurrentHashMap 之间的区别,从数据结构到多线程安全~确定不来看看嘛~
更多精彩敬请期待:保护小周ღ *★,°*:.☆( ̄▽ ̄)/$:*.°★* ‘

HashMap、HashTable、ConcurrentHashMap 之间的区别


一、 直观上的区别

HashTable 和 HashMap都是用于存储键值对的数据结构

我们一般把搜索的数据称之为关键字 (key), 与关键字 key 对应的为值(value),这种模型统称为

“key -value 的键值对”。

Map 和 Table 采用的都是 key - Value 模型,例如:有一个字符串,统计其中每个字符出现的次数,

HashMap、HashTable、ConcurrentHashMap 之间的区别

 Java 中Map 中的数据结构:

HashMap、HashTable、ConcurrentHashMap 之间的区别

画了一个简单的图理解一下,如果详细的介绍的话恐怕就会脱离主题了。 

哈希算法是HashMap的底层实现原理里面很重要的一个组成部分,它来决定数据的位置及访问记录,哈希算法也叫散列算法(Map 的底层数据的存储规则就是使用该算法),把我们存在map中的key(任意长度的值)通过此算法变成固定长度的key(地址),通过这个地址访问数据。

1. HashMap 和 HashTable 的第一点不同,底层数据结构不同: jdk1.7底层都是数组+链表的结构,但jdk1.8 HashMap加入了红黑树,

在JDK1.8之后,HashMap中的链表在满足以下两个条件时,将会转化为红黑树(自平衡的排序二叉搜索树):

1. 数组 array[ i ] 处存放的链表长度大于等于8;
2. 数组长度大于等于64;

满足以上两个条件,数组 array[ i ] 处的链表将自动转化为红黑树,其他位置如 array[ i ]处的数组元素仍为链表。当链表的长度低于 8 的时候又会由红黑树变成链表。

Map 的扩容机制 ,使用了负载因子调节,荷载因子 = 填入表中的元素个数 / 散列表的长度

Java 中限制了荷载因子的大小为 0.75,在实际开发中荷载因子根据业务需要而定,当荷载因子大于 0.75 的时候,意味着 “数组”的长度就需要扩容了,扩容意味着链表中的元素需要重新哈希(使用哈希函数重新计算元素位置并添加),这个开销是非常大的。


2. 初始化容量不同:HashMap 的初始容量为:16,Hashtable 初始容量为:11,两者的负载因子默认都是:0.75。
3. HashMap:在不指定容量的情况下的默认容量为16; 当已用容量>总容量 * 负载因子时,要求一定为2的整数次幂,扩容时将容量变为原来的2倍
Hashtable 扩容规则为当前容量翻倍 +1。

4. Hashtable:key和value都不允许出现null值; HashMap:null能够作为键(key),这样的键只有一个。


二、多线程环境使用哈希表

HashMap 是线程不安全的,在多线程的环境中,还是会存在多个线程并发对同一个共享数据进行操作从而引发的线程安全。

在多线程的环境下可以使用的哈希表有:Hashtable  和 ConcurrentHashMap 

接下来就围绕这两种哈希表来展开:

2.1 Hashtable 

Hashtable 为了保证线程安全问题,将每个关键的方法都加上了 synchronized 关键字,这就相当于针对 hashtable 对象本身加锁,多线程并发执行,同一单位时间内,只能有一个线程能(获取到对象锁,并加锁,一个对象只有一把锁,线程只有拿到锁才能够继续执行)争对 hashtable 进行操作,其他的线程阻塞等待,加锁操作有时间消耗,包括释放锁之后唤醒其他线程来竞争锁都是一笔开销,所以 Hashtable 整体在单线程中效率是低于 hashMap 的,在多线程的环境下效率也是极低的。

HashMap、HashTable、ConcurrentHashMap 之间的区别

总结:

1. Hashtable保证线程的方式就是争对 Hashtable 对象本身加锁

2. 如果多线程访问同一个Hashtable 就会直接造成锁冲突。

3. 如果在多线程的环境下,一个线程在执行中触发了扩容机制,就会由该线程完成全部数据的重新哈希计算位置,涉及到大量的元素移动,在这个时间里,其他线程只能干等着,所以效率非常低。

HashMap、HashTable、ConcurrentHashMap 之间的区别


2.1 ConcurrentHashMap 

这个哈希表可以看作是 hashMap 线程安全的版本,在 JDK 1.7 的时候跟 hashMap 一样都是

数组 + 链表的结构。

在线程安全的角度也是在 hashtable 的基础上做了一系列改进和优化,hashtable 是针对整个对象加锁,在 JDK1 .7 的时候 ConcurrentHashMap 采用的分段加锁的机制,对每一个“段”来加锁。

ConcurrentHashMap由segment 数组结构和 hashEntry 数组结构构成的,即 ConcurrentHashMap 把哈希桶数组切分成小数组(Segment ),每个小数组有 n 个 HashEntry 组成。

每个segment配备一把锁,当一个线程访问其中一段数据时,就会尝试获取 segment 中的对象锁,这样在保证segment锁住的同时而不影响其他线程访问其他的segment, 在保证安全性的同时也提高了效率。

Segment数组的长度是不会被改变的,初始化如果不规定,那么就采用默认的 16,扩容只是针对segment数组内部的HashEnrty数组。

HashMap、HashTable、ConcurrentHashMap 之间的区别

JDK1.8下的ConcurrentHashMap

JDK 1.8以后 hashMap 和 ConcurrentHashMap 底层的结构都改为 数组 + 链表 + 红黑树的结构。

在线程安全方面又做出了进一步的提升

1. 对ConcurrentHashMap 的读操作没有加锁(get() ,根据key 返回 value 值这些只做查询的方法),而是使用了 volatile 关键字保证内存可见性(保证每次从内存中读取数据),只针对写操作加锁(put() 等方法),而且不是针对 map 对象加锁,也不是针对每一个段加锁,而是针对每个链表的头节点加锁(synchronized 关键字修饰)(每个对象都有一把锁,每个链表,都是一个list 对象,所以可以直接使用 list 的对象锁),这样就实现了更加细粒度的锁。

HashMap、HashTable、ConcurrentHashMap 之间的区别

HashMap、HashTable、ConcurrentHashMap 之间的区别

 写操作,只是针对链表的加锁。


2. ConcurrentHashMap 在保证线程安全的方面使用的是 CAS(可以看作是硬件支持的原子性操作的指令,适用于无锁编程,也可以保证线程安全问题) 和 synchronized 锁 ,在锁冲突不严重的场景下使用 CAS 自旋来更新数据,可以避免出现了重量级锁的情况。

3. 扩容机制:

  • 当某个线程对 ConcurrentHashMap 进行操作时如果触发了扩容机制,只需要创建一个新的 哈希表,将当前线程操作的链表的部分数据搬运过去,扩容期间,新、老哈希表都存在。
  • 后续每个来操作 ConcurrentHashMap 的线程,都会搬运部分元素,直到搬完老哈希表中最后一个元素,再将老哈希表删除。
  • 这个期间,插入元素只往新哈希表中添加,查找元素需要同时在新、老哈希表中查询。

ConcurrentHashMap 总结:

1. ConcurrentHashMap 的读操作不会加锁,目的是为了进一步降低锁冲突的概率,但是为了保证每次都能从内存中访问数据(防止其他线程对数据更新,当前线程还不知道)使用了 volatile 关键字保证内存可见性。

2. ConcurrentHashMap 的分段锁技术是 JDK 1.7 中采用的技术,就是把若干个哈希桶分成一个“段”(Segment),针对每个分段加锁。Segment数组的长度是不会被改变的,初始化如果不规定,那么就采用默认的 16,扩容只是针对segment数组内部的HashEnrty数组。数据结构结构采用 数组 + 链表的结构;

3. ConcurrentHashMap 在JDK 1.8 中取消了分段锁的安全机制,而是给每个哈希桶(每个链表)分配一个锁,在数据结构方面改进成数组 + 链表 + 红黑树的方式,当链表大于等于8 个元素就转换成红黑树


到这里,HashMap、HashTable、ConcurrentHashMap 之间的区别,博主已经分享完了,希望对大家有所帮助,如有不妥之处欢迎批评指正。

HashMap、HashTable、ConcurrentHashMap 之间的区别

本期收录于博主的专栏——JavaEE,适用于编程初学者,感兴趣的朋友们可以订阅,查看其它“JavaEE基础知识”。

感谢每一个观看本篇文章的朋友,更多精彩敬请期待:保护小周ღ *★,°*:.☆( ̄▽ ̄)/$:*.°★* 

遇见你,所有的星星都落在我的头上……文章来源地址https://www.toymoban.com/news/detail-416926.html

到了这里,关于HashMap、HashTable、ConcurrentHashMap 之间的区别的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • HashMap和HashTable的区别是什么?

    HashMap和HashTable都是常见的哈希表实现,用于存储键值对。它们在功能上类似,但在以下几个方面存在区别: 线程安全性:HashTable是线程安全的,它的所有操作都是同步的,即多线程同时访问HashTable时会自动进行同步处理,从而保证线程安全。而HashMap是非线程安全的,它的操

    2024年02月15日
    浏览(38)
  • 【多线程进阶】信号量,线程安全集合类,Hashtable与ConcurrentHashMap的区别,多线程常见的面试题

    前言: 大家好,我是 良辰丫 ,今天学习多线程最后一节内容,我们主要去了解信号量,线程安全集合类,Hashtable与ConcurrentHashMap的区别,多线程常见的面试题,我们需要重点去掌握,💞💞💞 🧑个人主页:良辰针不戳 📖所属专栏:javaEE初阶 🍎励志语句:生活也许会让我们遍体鳞伤,

    2023年04月27日
    浏览(53)
  • C#中的HashTable和Dictionary之间的区别

    HashTable和Dictionary都是用于存储数据的数据结构的类型。这两个数据结构都将存储的数据保存为键值对。

    2024年02月17日
    浏览(51)
  • 面试题:HashMap线程不安全 ConcurrentHashMap为什么线程安全

    面试的时候先会喊你说说集合,那些集合线程不安全?当你说了 HashMap 线程不安全,面试官可能会进一步询问你是否了解 ConcurrentHashMap ,以及它是如何实现线程安全的。 ArrayList、LinkedList、TreeSet、HashSet、 HashMap 、TreeMap等都是线程不安全的。 HashTable 是线程安全的。 来看个例

    2024年04月23日
    浏览(47)
  • 美团面试拷打:ConcurrentHashMap 为何不能插入 null?HashMap 为何可以?

    周末的时候,有一位小伙伴提了一些关于 ConcurrentHashMap 的问题,都是他最近面试遇到的。原提问如下(星球原贴地址:https://t.zsxq.com/11jcuezQs ): 整个提问看着非常复杂,其实归纳来说就是两个问题: ConcurrentHashMap 为什么 key 和 value 不能为 null? ConcurrentHashMap 能保证复合操

    2024年02月11日
    浏览(35)
  • ConcurrentHashMap 1.7与1.8的区别

    ConcurrentHashMap 与HashMap和Hashtable 最大的不同在于:put和 get 两次Hash到达指定的HashEntry,第一次hash到达Segment,第二次到达Segment里面的Entry,然后在遍历entry链表 从1.7到1.8版本,由于HashEntry从链表 变成了红黑树所以 concurrentHashMap的时间复杂度从O(n)到O(log(n)) HashEntry最小的容量为2 S

    2023年04月16日
    浏览(38)
  • unsigned int 与 int 间的区别

    unsigned int 是无符号整型,要求定义的整数一定是正整数。 当把一个负数赋值给无符号整型的变量的时候,会自动把最高位的符号位看成整数的一部分。 例如: 结果为 因为-10的在计算机中存储的补码为1111 1111 1111 1111 1111 1111 1111 0110 当计算不把最高位当作符号位,默认这是个

    2024年02月12日
    浏览(42)
  • 网络知识之交换机各层间的区别

    具体的工作流程如下:       (1) 当交换机从某个端口收到一个数据包,它先读取包头中的源MAC地址,这样它就知道源MAC地址的机器是连在哪个端口上的;       (2) 再去读取包头中的目的MAC地址,并在地址表中查找相应的端口;             (3) 如表中有与这

    2024年02月05日
    浏览(50)
  • 即时通讯:短轮询、长轮询、SSE 和 WebSocket 间的区别

    在现代 Web 开发中,即时通讯已经成为许多应用程序的重要组成部分。为了实现即时通讯,开发人员通常使用不同的技术和协议。本文将介绍四种常见的即时通讯实现方法:短轮询、长轮询、SSE(服务器发送事件)和 WebSocket,并探讨它们之间的区别。 短轮询是最简单的即时通

    2024年02月12日
    浏览(44)
  • Java----Hashmap,LinkedMap和TreeMap三者的区别

            其中map表示的意思为“映射”,HashMap,LinkedMap和TreeMap这三中类都是对Map接口的实现类,在数据插入方面,HashMap是无序插入,LinkedMap是有序插入,而TreeMap会根据键的值进行排序后再进行插入。在运行方面,前两个的运行速度较快,针对Map对象的存储会选择前两者,

    2024年02月13日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包