在多线程环境下使用哈希表 迷南。 2024-03-27 15:44 43阅读 0赞 一.HashTable和HashMap HashTable是JDK1.0时创建的,其在创建时考虑到了多线程情况下存在的线程安全问题,但是其解决线程安全问题的思路也相对简单: ![5ac4c4b20b1753f0748c469cd094b4bc.png][] 在其众多实现方法上加上synchronized关键字(效率较低),保证其串行化执行。 但是随着业务场景的多样化,在单线程情况下不需要考虑线程安全问题,于是HashMap应运而生,同理,hashMap没有办法保证线程安全,后面随着多线程情况中的线程安全问题需求不断扩大,在多线程环境下使用哈希表有了新的解决方案。 二.JUC包下的ConcurrentHashMap 我们在这再详细说一下Hashtable存在的弊端:对整个hashtable对象加同一把锁,在多线程情况下,任意两个线程访问Hashtable中的任意数据都会产生锁竞争, size属性也是通过synchronized进行同步的,也是比较慢。同时,一旦触发扩容,该线程完成整个扩容,这个过程涉及到大量元素的拷贝,效率比较低。 ConcurrentHashMap针对这些方面进行了一系列的优化:在读时不加锁,这样大大提高了在hashmap中读取元素的效率,但是需要在元素上加volatile关键字,保证在其元素修改后能第一时间获取,只在写操作上加锁,而且它的加锁方式并不是对整个hashmap对象加锁,而是对‘桶’加锁:对hash表中的每个下标(链表头结点作为锁对象)(提高了锁密度),大大降低了锁冲突的概率。 图示就是由上面这种转化为下面这种 ![758d1d7508e782d7c5538fa817142409.png][] ![407b2dcafb420bd0c4f7b2208f7ed613.png][] 同时利用CAS的特性对size进行更新,效率提高 与此同时还优化了元素的更新策略:化整为零,在进行扩容时,将旧桶中的部分元素搬运到新桶中,在以后调用新桶的方法时再每次搬运部分元素,在这个过程中添加新的元素时直接往新桶中添加,在查找时在两个桶中都进行查找,直到搬运完最后一个元素,再将老桶删除掉(新桶和老桶会同时存在一段时间) 最后我们提出一个问题 concurrentHashMap和HashMap、HashTable之间的区别 ①HashMap是线程不安全的 ②HashTable线程安全,但是不推荐使用,因为所有的操作都加了synchronized关键字,对性能影响比较大 ③ConcurrentHashMap的锁粒度小,不是对整个hash表进行加锁,而是对每一个数据的下标进行加锁 ④ConcurrentHashMap对于put()加锁,对于读get()不加锁 ⑤对于大量共享变量运行了volatile关键字修饰 ⑥对ConcurrentHashMap对扩容进行了优化 ![9dd3c7aad18e5cb1d22ea75045680121.png][] [5ac4c4b20b1753f0748c469cd094b4bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/67d8f24699d743f6bc78ecddf81d09bf.png [758d1d7508e782d7c5538fa817142409.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/95249a32a3804f3a8c7894e5f7866b61.png [407b2dcafb420bd0c4f7b2208f7ed613.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8c2c2935a41c48e9aa4c0425a18298ae.png [9dd3c7aad18e5cb1d22ea75045680121.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/663a4c91df6146f789f140af606691aa.png
相关 线程安全的集合类(多线程环境下使用ArrayList、队列及哈希表) 目录: 多线程环境下使用ArrayList 多线程环境下使用队列 多线程环境下使用哈希表 -------------------- 多线程环境下使用 雨点打透心脏的1/2处/ 2024年03月30日 16:04/ 0 赞/ 28 阅读
相关 在多线程环境下使用哈希表 一.HashTable和HashMap HashTable是JDK1.0时创建的,其在创建时考虑到了多线程情况下存在的线程安全问题,但是其解决线程安全问题的思路也相对简单: 迷南。/ 2024年03月27日 15:44/ 0 赞/ 44 阅读
相关 哈希表 上一篇博客:[静态链表的介绍及实现][Link 1] > 写在前面:大家好!我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的 ╰半夏微凉°/ 2022年10月30日 07:24/ 0 赞/ 189 阅读
相关 哈希表 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速 系统管理员/ 2022年06月10日 01:26/ 0 赞/ 236 阅读
相关 哈希表 我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个数组,为每个可能的关键 快来打我*/ 2022年06月05日 02:20/ 0 赞/ 338 阅读
相关 哈希表 1. 什么是哈希表 我们先来做个题(leetCode上387题) ![70][] public class Solution_387 { 朱雀/ 2022年05月16日 10:11/ 0 赞/ 277 阅读
相关 哈希表 哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0 今天药忘吃喽~/ 2022年02月01日 14:36/ 0 赞/ 384 阅读
相关 【哈希表】 char FirstNotRepeatingChar(char pString) { // invalid input if(! r囧r小猫/ 2022年01月06日 11:33/ 0 赞/ 305 阅读
相关 哈希表 一、简介 如果所有的键都是小整数,那么我们可以用一个数组来实现无序的符号表,将键作为数组的索引i而数组中i(键)处储存的就是对应的值。 这样就可以快速地访问任意键的值, 旧城等待,/ 2021年12月22日 01:21/ 0 赞/ 380 阅读
相关 哈希表 【一】哈希表 > 他通过把关键码值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数就是散列函数。 ![watermark_type_ZmFuZ3poZW5na 傷城~/ 2021年08月11日 17:13/ 0 赞/ 534 阅读
还没有评论,来说两句吧...