概述

1. collection接口（不含键值对）：有序的List接口、无序的Set接口、队列Queue接口

2. map接口（键值对): Hashmap、Hashtable、LinkedHashMap等实现类

3. HashTable 是线程安全的，所有的读写操作都是synchronized修饰的

4. LinkedHashMap继承自HashMap，内部有一个双向链表来存储插入的顺序，通过header来维护和操作这个链表

5. HashMap：loadfactor、与运算、resize、数组+单向链表（或者红黑树 JDK1.8)

6. HashMap的插入的过程（先check是否存在 再首位插入）：

• 根据key经过数学运算得到一个足够大足够随机的Hashcode
• HashCode和Size-1做 &运算，得到在数组中Index
• 如果Index为null，则直接插入，如果Index不为null，先遍历链表是否有重复的值，有就替换，没有再判断是否触发resize()
• 如果无需resize()就把新值插入到Index的首位，next Entry指向前一个Entry

7. ConcurrentHashMap：线程安全的HashMap

• 通过引入分段锁的技术，支持在不同分段的数据，可以并发写
• 通过引入volatile修饰HashEntry，保证线程安全的同时，在一个分段锁内部，读写可以同时进行，而不需要阻塞

8. ConcurrentHashMap插入的过程：计算分段、获取锁、插入、释放锁

• 通过key进行Hash运算，得到HashCode值
• 对HashCode和分段锁做& 运算，计算出位于哪个分段
• 通过tryLock()获取对应的分段锁
• 对HashCode和Index做做& 运算，计算出位于哪个Index，然后插入或者resize()后再插入
• 操作完成后释放锁，返回oldValue

9. ConcurrentHashMap的size需要每次动态统计的，先尝试遍历2次，值一样就返回，值不一样就加锁统计。

继承关系图

collection接口（不含键值对）：有序的List接口、无序的Set接口、队列Queue接口
map接口（键值对): Hashmap、Hashtable、LinkedHashMap等实现类

image image

ConcurrentHashMap 1.7

1. put方法，Segment加锁，操作完之后再释放锁，可能会触发rehash()，保证了线程安全
2. get方法，getObjectVolatile的方式尝试获取最新的值，其中table、HashEntry.value、HashEntry.next都是volatile修饰的
3. rehash方法，触发的时机是达到size*loadfactor，和HashMap不一样。只独立的发生在一个Segment里面，table的大小翻倍，然后遍历获取首节点，挨个放到新数组中，是从前面开始移到链表的末位
4. remove方法，加锁的方式，找到就删除
5. size方法：只要在一小段连续的时间内CHM未发生改动，该sum(count)值就是size值，如果变动很频繁，直接锁住，求size
6. containsValue方法遍历一次结果集，如果找到了就直接返回true，未找到则last=sum(modCount），再check遍历一次，如果2次sum一样，仍然未匹配到就返回false，超过次数后就加锁遍历。
7. isEmpty方法:sum(modcount)为0肯定为空，check一次sum(modcount)一样且count都为0就是空。最多遍历2次。
8. clear方法: 加锁把每个Segment的table的首位entry设置为null，把Segment的count归置为0，++modCount