一、Map

1.1hash冲突解决

• 开放寻址
• 再散列
• 链地址法

1.2 ConcurrentHashMap

• HashTable使用sync锁方法实现线程安全，效率低。
• putIfAbsent() 比HashMap多了一个方法，如果存在设置
• ConcurrentHashMap使用了分段存储的原理，分段锁

1.8之前

1. 会根据并发度将数据分成若干区域Segment
2. 每个区域都继承了可重入锁，即线程每次只会锁区域。
3. 区域下是table,再下一级是HashEntry。
4. get和set会先将hash进行再散列
5. 然后根据并发度取模，得出位于那个区域内。
6. get方法没有加锁，因为数据是volatile修饰的，有修改马上体现（链表不是，遍历时可能会不一致，弱一致性）
7. 扩容只会扩容当前区域的map
8. size()会尝试两次不加锁的获取，一致返回，不一致全部加锁获取。

1.8后

1. 取消了区域segment只维护一个数组，锁粒度更小
2. 链表+红黑树(8个以内链表，之后用红黑树，查询效率高(O(logn)))

• sizeCtl

1. 负数，进行初始化或扩容，-1正则初始化，-N,有n+1个线程在扩容

2. 正数，0没初始化，>0初始化或下次扩容的阈值

3. 初始化时会检测sizeCrl的值，如果<0,表示有线程在初始化或扩容，让出运行权。

4. 并发扩容，如果线程发现有线程在扩容，会帮助扩容然后再插入。

5. put方法先再hash保证分布均匀，其次判断是否扩容，最后CAS插入

6. 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这样的方式区分。