java集合类源码分析

特点：

源码逻辑概括：

特点：

源码概括：

特点：

源码逻辑概括：

特点：

源码逻辑概括：

特点：

源码逻辑概括：

底层使用的是TreeMap

jdk1.7底层使用数组+链表的方式实现，每次插入使用的是头插法

jdk1.8底层使用数组+链表+红黑树的方式实现，每次插入使用的是尾插法

无序

HashMap是线程不安全的

为了程序方便遍历，会创建EntrySet集合，这个集合里面存放的元素类型是Entry，而一个Entry对象就有k，v。既：(transient Set<Map.Entry<K,V>> entrySet)

Node内部类实现了Map.Entry接口，Map.Entry接口主要提供一些方法，如K  getKey()，V  getVaule() 

执行put() 方法添加一个key-val时，先得到key的hash值（计算hash值的算法为：hashCode（算法为h= key.hashCode()^（h>>>16）），使用按位异或和算术右移操作的是为了减少hash碰撞概率），然后用hash值和table长度做&运行得到索引值

然后判断存储数据的table中该索引处是否有元素，如果没有则直接添加，如果有则先判断该元素的key和准备加入的key是否相等，如果相等则直接替换原有val

如果不相等则判断是树结构还是链表结构，作出响应的处理

如果判断存储是链表则用for循环依次和该链表的每一个元素比较，如果链表中有相同的则直接不添加，如果没有则添加到链表的尾部，添加到链表尾部后，会立即判断当前链表长度是否达到8，如果达到8则调用treeifyBin（）方法，这是会判断table的长度是否>64，如果>64则进行树化操作，如果<64就会先扩容调用resize（）方法，因为调用resize（）会对HashMap中的元素进行重新散列hash

如果是红黑树，则判断红黑树中是否有该元素，如果没有则添加到树中，如果有则不添加

jdk1.8中，如果一条链表的长度到达了8且table的大小>=64,链表就会进行树化（由链表转换为红黑树）

在添加完最后会判断数组元素是否>扩容临界值/阈值（负载因子*数组大小），如果大于则会进行扩容，扩容大小是原来的两倍

调用remove（）方法删除元素时，当数组中元素是红黑树时，红黑树元素个数等于6时，会进行树的退化，由红黑树退化成链表

为什么初始化容量都是2等n次幂？

HashTable中的健值都不可为null，否则会抛出空指针异常

HashTable是线程安全的（操作方法上加了Synchronized关键字）

底层有数组HashTable$Entry[] 初始化大小为11

调用put（）方法会内部执行addEntry（hash，hash，value，index）；添加K-V封装到Entry中

扩容机制是，当HashTable中元素个数>阈值时，就进行扩容

扩容按照int newCapacity = (oldCapacity <<1)+1;的大小扩容（也就是原来容量的2倍+1）

底层使用红黑树数据结构

可以传一个Comparator匿名内部类

如果没有传Compartor匿名内部类则会默认按照ASCII自然排序

如果传了Compartor匿名内部类则会调用compare方法进行循环遍历比较

如果循环遍历比较过程中，发现准备添加的key和当前key相等，就覆盖值

默认初始化元素的长度为32，由Segment[]数组默认长度（16）* HashEntry[]数组默认长度（2）可得32

Segment对象实现了ReentrantLock对象（这也就是所谓的分段锁，每个Segment对象都有自己的锁）

不允许空值空键

底层使用Segment锁对象（分段锁）+红黑树+链表实现

1，调用put（）方法，会使用key计算hash值，然后使用key的hash值取高位计算Segment[]的索引

2，然后判断Segment[]中，当前索引位置是否为null，如果为空则创建HashEntry[]放在当前索引位置，然后返回当前Segment对象，如果不为null，则直接返回Segment对象

3，然后调用当前Segment对象中的put（）方法，此时会调用tryLock（）方法尝试获取当前Segment对象的锁，如果获取锁成功就继续往下执行，如果获取锁失败则调用scanAndLockForPut（）方法自旋获取锁，最大自旋次数是64，然后调用lock（）方法加阻塞锁，在自旋的同时会创建好HashEntry对象

4，当获取到锁后，会先拿到Segment对象中的HashEntry[] 数组，同时使用key的hash值和HashEntry[]数组的大小进行&运行（int index= （tab.length-1）&hash），获取当前需要存储的值在HashEntry[]数组中的索引下标

5，获取到HashEntry[]数组下标后，会判断该下标处是否为null，如果为null则直接创建一个HashEntry对象，然后元素个数+1，然后在判断是否需要扩容，如果不需要扩容则直接添加值

6，如果获取到HashEntry[]数组下标后，判断该下标处不为null，则会判断当前当前HashEntry链表中是否有相同key，有则替换，没有则添加

7，在添加前会判断元素大小是否>阈值，如果大于则需要扩容

8，扩容后的HashEntry[]数组大小为原来的2倍，然后比那里原来的元素，重新按新HashEntry[]的长度进行&操作

9，调用size（）方法获取集合长度，会遍历拿到每个Segment对象中的元素个数累加，然后到最后一个Segment对象时会遍历给所有Segment对象加lock锁，然后统计出元素的总个数，之后会记录最后一次统计元素个数的值，然后在进行第二次元素个数的统计，如果与第一次统计值相等则判断证明没有进行新的增删改操作，返回sum，如果不相等则继续统计，最多统计4次，最少统计两次，也就是说，这个for循环最少会执行两次，然后统计成功后释放锁

线程安全的

扩容有多线程协助扩容

不允许空值空键

底层使用CAS+synchronize锁+红黑树+链表实现

ConcurrentHashMap与HashMap一样，new的时候不会初始化数组大小，只有调用put（）方法往里面添加元素时才会初始化大小，默认初始化大小为16

sizeCtl含义：

ConcurrentHashMap中有一个volatile 修饰的sizeCtr成员变量，如果sizeCtl是-1，表示正在初始化，如果是正数表示当前数组要扩容时候的阈值，如果是0则是未初始化

1，调用put（）方法，会调用putVal（）方法，然后计算使用key计算hash值，然后判断数组是否初始化，如果没有初始化就会先初始化，默认初始化大小是16

2，如果已经初始化了，则通过hash计算得到桶位是否有元素，如果没有则利用cas添加元素

3，如果计算桶未知元素的hash为MOVED，则证明此时正在扩容，此时就会先去协助扩容

4，如果计算桶位置元素不是空，且当前没有处于扩容阶段，就进行元素的添加

5，在给对应桶位置添加元素时，会使用synchronized代码(锁对象是索引位置当前节点对象)块给当前桶位置节点上锁，保证线程的安全

6，然后会判断提添加节点的hash是否>=0,如果是则判断是普通链表节点，然后循环遍历链表中是否有和要添加的key相等的元素，如果有则替换值，如果没有则直接在尾结点添加该元素

7，如果判断hash不满足>=0的条件，此时桶内节点为红黑树节点，此时会往红黑树中添加元素

8，添加完元素后会判断binCount（binCount在链表添加节点时会累加）是否>8,也就是判断是满足将链表转换成红黑树的，然后会调用treeifyBin（）方法进行树化操作，进入treeifyBin（）方法后，还会判断数组大小是否>64,如果不满足条件，则进行扩容，如果满足条件则进行树化

9，最后会调用addCount（）方法去维护元素个数

10，统计元素个数时，先会使用baseCount属性去进行CAS操作，如果加成功，则统计完成

11，如果使用baseCount属性进行CAS操作失败，则会调用fullAddCount（）方法，初始化出一个CounterCell[]数组，然后通过计算给这个数组中的一个元素进累加，累加成功则最后进行计算元素个数，如果计算在整个数组中的所有元素都没有累加成功，会进行CounterCell[]数组扩容，扩容后继续重新计算数组元素进行累加

12统计完元素个数后，会判断当前数组元素个数是否满足扩容条件，如果满足则会触发扩容机制

13，如果一个线程正在扩容，此时有线程也进入了此代码块，则会判断当前sizeCtl是否<0,如果小于0，则会去协助扩容

14，协助扩容的线程会去领取自己负责迁移数据的任务，此时会判断当前cpu核心数，如果是多核心cpu，那么每个线程会划分任务，最小任务是16个桶位置，任务的划分是从后往前开始划分的

15，当线程领取到了任务后，会从后往前进行帮助数据迁移，如果前完一个桶位置元素，则会将该迁移完的桶元素位置赋值为ForWardingNode节点对象（这个FowardingNode节点对象的hash值为1）