HashTable, HashMap, ConcurrentHashMap 之间的区别
目录
总体来看,HashTable, HashMap, ConcurrentHashMap都是Map接口的实现类,都是以key-value的形式来存储数据,下面我将对这三个分别进行阐述对比
1. HashMap
a)HashMap 的键值可以为null (当key为空时,哈希会被赋值为0)
b)HashMap 的默认初始容量是16, 最大容量是2^30;
c)HashMap 使用的数据结构是 数组 + 链表 + 红黑树
如果链表中结点个数 > 8时,链表 将转化为 红黑树
如果链表中结点个数 < 6时,红黑树 又转化为 链表
如果哈希桶中某条链表的个数 > 8时,并且桶的个数超过64时,才会将链表转换为红黑树。否则就直接扩容
d) HashMap 效率非常高,但线程不安全
2. HashTable
a)HashTable 的键值不能为null
b)HashTable 虽然线程安全,但只是简单得用 synchronized 给所有方法加锁,相当于是对this加锁,也就是对整个HashTable对象进行加锁(非常无脑)
一个HashTable对象只有一把锁,如果两个线程访问同一个对象时,就会发生锁冲突
c)HashTable效率非常低,因为无脑加锁原因,比如一些读操作不存在线程不安全问题,所以这样的加锁方式导致效率非常低
比如 某个线程触发了扩容机制,那就会由这个线程完成整个扩容过程,如果元素特别多的情况下,效率非常低,其他线程阻塞等待的时间会特别长
d)HashTable 使用的数据结构是 数组 + 链表
因为HashTable无脑加锁的原因,现在Java官方已经不推荐使用HashTable了
不涉及线程安全问题时使用HashMap,如果要保证线程安全就使用ConcurrentHashMap
3. ConcurrentHashMap
a)ConcurrentHashMap 的键值不可以为null
b)ConcurrentHashMap 使用的数据结构是 数组 + 链表 + 红黑树
c)ConcurrentHashMap 最重要的点要说 线程安全
ConcurrentHashMap 相比比较于HashTable 有很多的优化,
最核心的思路就是:降低锁冲突的概率
(1)锁粒度的控制
ConcurrentHashMap 不是锁整个对象,而是使用多把锁,对每个哈希桶(链表)都进行加锁,只有当两个线程同时访问同一个哈希桶时,才会产生锁冲突,这样也就降低了锁冲突的概率,性能也就提高了
(2)ConcurrentHashMap 只给写操作加锁,读操作没加锁
如果两个线程同时修改,才会有锁冲突
如果两个线程同时读,就不会有锁冲突
如果一个线程读,一个线程写,也是不会有锁冲突的
(这个操作也是可能会锁冲突的,因为有可能,读的结果是一个修改了一半的数据
不过ConcurrentHashMap在设计时,就考虑到这一点,就能够保证读出来的一定时一个“完整的数据”,要么是旧版本数据,要么是新版本数据,不会是读到改了一半的数据;而且读操作中也使用到了volatile保证读到的数据是最新的)
(3)充分利用到了CAS的特性
比如更新元素个数,都是通过CAS来实现的,而不是加锁
(4)ConcurrentHashMap 对于扩容操作,进行了特殊优化
HashTable的扩容是这样:当put元素的时候,发现当前的负载因子已经超过阀值了,就触发扩容。
扩容操作时这样:申请一个更大的数组,然后把这之前旧的数据给搬运到新的数组上
但这样的操作会存在这样的问题:如果元素个数特别多,那么搬运的操作就会开销很大
执行一个put操作,正常一个put会瞬间完成O(1)
但是触发扩容的这一下put,可能就会卡很久(正常情况下服务器都没问题,但也有极小概率会发生请求超时(put卡了,导致请求超时),虽然是极小概率,但是在大量数据下,就不是小问题了)
ConcurrentHashMap 在扩容时,就不再是直接一次性完成搬运了
而是搬运一点,具体是这样的
扩容过程中,旧的和新的会同时存在一段时间,每次进行哈希表的操作,都会把旧的内存上的元素搬运一部分到新的空间上,直到最终搬运完成,就释放旧的空间
在这个过程中如果要查询元素,旧的和新的一起查询;如果要插入元素,直接在新的上插入
;如果是要删除元素,那就直接删就可以了
相关文章
- HashMap和HashSet的区别
- const和readonly区别
- 最小二乘法和梯度下降的区别
- python requests的content和text方法的区别
- Cisco交换机堆叠与HSRP之间的区别
- jQuery中click(),bind(),live()的区别(转)
- window.onload与$(document).ready() 的区别
- java.util.Date和java.sql.Date 一点区别
- go面向对象编程:结构体struct详解、结构体实例的创建方式、结构体之间的转换(type取别名的使用)、方法的注意事项及与函数的区别
- [转] C#中out和ref之间的区别
- JavaScript常见几种循环遍历的使用及区别
- WCF 服务应用程序与 服务库之间的区别
- Angular 依赖注入 UseClass 和 UseExisting 的区别 - 一个实际的测试例子
- redis-py 模块的 hset 与 hmset 之间的区别
- 物联网与人工智能之间的区别与联系
- SpringAop与AspectJ的联系与区别____比较分析 Spring AOP 和 AspectJ 之间的差别
- python 进程、线程、协程之间的区别
- DQL、DML、DDL、DCL的概念与区别
- Statement,PreparedStatement和CallableStatement的联系和区别
- Shell重定向&>file、2>&1、1>&2的区别
- 加密算法中BASE64、MD5、SHA、HMAC等之间的区别
- Docker,Docker Compose,Docker Swarm,Kubernetes之间的区别
- mongod和mongos之间的确切区别是什么
- 【数据挖掘】 GBDT面试题:其中基分类器CART回归树,节点的分裂标准是什么?与RF的区别?与XGB的区别?
- VSCode中4个Settings(JSON)的区别与联系
- Go 参数传递:值、引用及指针之间的区别?
- 码农、黑客和2B程序员之间的区别