一、Map
1.1hash冲突解决
- 开放寻址
- 再散列
- 链地址法
1.2 ConcurrentHashMap
-
HashTable
使用sync
锁方法实现线程安全,效率低。 -
putIfAbsent()
比HashMap
多了一个方法,如果存在设置 -
ConcurrentHashMap
使用了分段存储的原理,分段锁
1.8
之前
- 会根据并发度将数据分成若干区域
Segment
- 每个区域都继承了可重入锁,即线程每次只会锁区域。
- 区域下是
table
,再下一级是HashEntry
。 -
get
和set
会先将hash
进行再散列 - 然后根据并发度取模,得出位于那个区域内。
-
get
方法没有加锁,因为数据是volatile
修饰的,有修改马上体现(链表不是,遍历时可能会不一致,弱一致性) - 扩容只会扩容当前区域的
map
-
size()
会尝试两次不加锁的获取,一致返回,不一致全部加锁获取。
1.8
后
- 取消了区域
segment
只维护一个数组,锁粒度更小 - 链表+红黑树(8个以内链表,之后用红黑树,查询效率高(O(logn)))
sizeCtl
-
负数,进行初始化或扩容,-1正则初始化,-N,有n+1个线程在扩容
-
正数,0没初始化,>0初始化或下次扩容的阈值
-
初始化时会检测
sizeCrl
的值,如果<0,表示有线程在初始化或扩容,让出运行权。 -
并发扩容,如果线程发现有线程在扩容,会帮助扩容然后再插入。
-
put
方法先再hash
保证分布均匀,其次判断是否扩容,最后CAS
插入 -
get
方法主要是定位,用hash
值根据当前table
大小取模
二、其他容器
2.1ConcurrentSkipListMap
-
SkipList
跳表,空间换时间,每次插入都会随机判断是否当作索引。
2.2ConcurrentLinkedQueue
2.3写时复制容器
CopyOnWriteArrayList
CopyOnWriteArraySet
- 每次写都会创建一个新的容器,创建完将引用转到新的容器
- 数据一致性不高
- 空间占用大
三、阻塞队列
- 队列满的时候,插入元素线程阻塞,直到队列不满
- 队列空的时候,获取元素线程阻塞,直到有数据
3.1 常用方法
方法效果 | 抛出异常 | 返回值 | 一直阻塞 | 超时退出 |
---|---|---|---|---|
插入方法 | add | offer | put | offer(time) |
移除方法 | remove | poll | take | poll(time) |
检查方法 | element | peek | - | - |
3.2 阻塞队列接口
-
BlockingQueue
阻塞队列接口
3.3常用实现类
-
ArryBlockingQuenue
一个数组结构组成的有界阻塞队列(先进先出,需要初始大小) -
LinkedBlockingQuenue
一个链表组成的有界阻塞队列(先进先出,默认初始Integer.Max_Value) -
PriorityBlockingQueue
支持优先级排序的无界阻塞队列(默认自然排序,优先级需要实现compareTo()
) -
DelayQueue
使用优先级队列实现的无界阻塞延时队列,到期才能取出(内部元素必须实现Delayed
,定义compareTo
根据等待时间排序,getDelay
获取剩余时间) -
SynchronousQueue
不存储元素的阻塞队列,每个put
都要对应一个take
,速度很快,生产者和消费者需要匹配。 -
LinkedTransferQueue
链表结构组成的无界队列(transfer()
消费者消费后,才返回。tryTransfer()
立刻消费了则返回true
否则返回false
) -
LinkedBlockingDeque
链表组成的双向阻塞队列(可以从头和尾插入和移除元素,fork/join
工作窃取的实现),方法名是addLast
、addFirst
这样的方式区分。
网友评论