集合

1.ConcurrentHashMap1.71.1 put方法1.2 get方法 2.ConcurrentHashMap1.8流程2.1 put方法2.2 get方法2.3 扩容2.3.1 触发扩容的3种情况2.3.2 扩容流程2.3.3 扩容时的访问 3.HashMap(1.8的方法)3.1怎么得到元素存放的下标3.2 put函数的流程3.3 get函数的流程3.4 HashMap1.8和1.7的区别3.5 HashMap和ConcurrentHashMap确定扩容后元素存放的下标3.6 HashMap初始化 4 ArrayList4.1 ArrayList的构造函数4.2 ArrayList的扩容函数4.3 ensureCapacity方法 5. 不常用的集合5.1 HashTable5.2 Vector5.3 Set5.4 Map

1.ConcurrentHashMap1.7

Java 7 中 ConcurrentHashMap 的存储结构如上图，ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

1.1 put方法

首先得到要存放的segment。tryLock() 获取锁，获取不到使用 scanAndLockForPut 方法继续获取。这个方法做的操作就是不断的自旋 tryLock() 获取锁。当自旋次数大于指定次数时，使用 lock() 阻塞获取锁.计算 put 的数据要放入的 index 位置，然后获取这个位置上的 HashEntry 。如果这个HashEntry为空，直接插入。否则判断链表上有没有元素的key跟这个元素一样，如果有那就替换，如果没有就头插法插入。

1.2 get方法

计算key应该放在哪个segment的哪个HashEntry元素中，然后在这个元素上执行查找操作

2.ConcurrentHashMap1.8流程

参考资料https://blog.csdn.net/ZOKEKAI/article/details/90051567 在ConcurrentHashMap中是以Node数组来保存map的键值对，同一个数组位置是用链表加红黑树来保存。但是这个数组只有在第一次增加元素的时候才会初始化。第一次增加元素的时候，默认初期长度是16. 当增加元素出现hash冲突的时候，优先以链表的形式存放。如果链表的长度已经超过了8，但是Node数组的长度小于64时，扩容数组；如果链表长度超过8，Node数组的长度也大于等于64，那就把链表转化为红黑树。

2.1 put方法

* 如果数组没有初始化那就初始化数组 * 通过计算hash值来确定放在数组的哪个位置, hash值直接就是用key的hashcode()跟n-1做逐位与，如果元素这个位置为空则直接cas添加，如果不为空的话，则取出这个节点来 * 如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制 * 最后一种情况就是，如果这个节点，不为空，也不在扩容，则用synchronized对这个节点加锁，进行添加操作 * 如果是链表的话，则遍历整个链表，直到取出来的节点的key来个要放的key进行比较，如果key相等，则覆盖掉value，否则的话则添加到链表的**末尾**，如果达到链表的元素有8个以上了的话，那么就转化为红黑树。 * 如果是树的话，则调用putTreeVal方法把这个元素添加到树中去 * 判断是否需要扩容

2.2 get方法

根据 hash 值计算位置。查找到指定位置，如果头节点就是要找的，直接返回它的 value.如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。如果是链表，遍历查找之。

2.3 扩容

2.3.1 触发扩容的3种情况

插入节点后发现当前集合元素个数达到扩容阈值扩容状态下，插入，修改，删除等操作遇到ForwardingNode节点会触发扩容。插入节点后发现链表的长度大于大于八，并且Node数组长度小于64.

2.3.2 扩容流程

查看新数组是否已经被创建，没有创建的话，那就创建。否则不用管。从Node序号比较大的桶开始复制，每一个线程都被分配至少16个桶的复制任务。如果桶是空的，那么在数组中空桶的位置放一个ForwardingNode对象，它的hash值为-1，它的nextTable属性指向扩容后的数组。如果这个桶已经放置了ForwardingNode对象，说明这个桶已经被复制完毕了。如果这个桶还没有被复制，那么就把这个桶的存放的对象拿出来，用synchronized锁住，对桶存放的链表或红黑树复制到两个链表中，在用volatile的方式把链表放到新Node数组的相应的位置中。复制完成之后，用volatile的方式把fwd对象设置到旧Node数组对应的位置，表明已经迁移完毕。

2.3.3 扩容时的访问

还没对这个桶扩容的时候，可以正常地增删改查。正在扩容时Node数组对象会被synchronized锁住，因为进行增删改操作会先获得Node数组的对象的synchronized锁，所以会被阻塞。但是查操作在查的时候不需要获得锁，所以不会被阻塞，依然能够顺利访问。扩容完毕后，Node数组上对应位置的对象被设置为Fordwarding对象，put操作首先读取到Fwd对象，读取到其hash值是-1，因此判断正在扩容，因此当前线程也加入扩容操作。而get操作读取到fwd对象后，访问请求转发到扩容后的数组中了。

3.HashMap(1.8的方法)

3.1怎么得到元素存放的下标

在get和put的过程中，计算下标时，首先得到元素的hashCode，然后把hashcode右移16位跟原来的hashcode逐位异或，最后跟n-1逐位与，得到下标。如下图所示：

3.2 put函数的流程

根据key的hashcode计算得到hash下标。如果没有碰撞就放到数组里面。如果碰撞了，就用拉链法解决hash冲突，放到链表里面，插入的是尾部（1.7是头插法）。如果链表大于等于8，就转化为红黑树。如果链表小于6，就变成链表。如果所有元素超过capacity*装载因子，那么就要resize。

3.3 get函数的流程

根据key的hashcode得到下标。看看key是否跟数组中的元素相等，相等就命中。否则遍历树或链表进行查找。

3.4 HashMap1.8和1.7的区别

来自https://blog.csdn.net/h1458280799/article/details/85265135 #1.8版本HashMap和1.8版本ConcurrentHashMap公共内容

3.5 HashMap和ConcurrentHashMap确定扩容后元素存放的下标

通过扩容的方式把数组的节点分散开来，然后将这些元素复制到扩容后的新数组中。因为长度是扩展为原来的2倍，所以元素的位置要么在原来的位置，要么在原位置加上原来数组长度的位置。扩容后，hash值也得重新计算，新的hash值比旧的hash值增加了一位。所以判断位置的时候只需看新的hash值新增的数据位是1还是0.如果是1的话，那就放到原位置加上数组长度的位置，否则就是原位置。

3.6 HashMap初始化

创建时如果不指定容量初始值，HashMap的默认初始化大小是16.之后每次扩充都变成原来的2倍。创建时如果制定了容量初始值，那么HashMap通过计算，得到第一个比他大的2的幂并返回，将这个新得到的值作为真正的初始容量。

4 ArrayList

4.1 ArrayList的构造函数

以无参构造方法创建ArrayList时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素的时候，才真正分配容量。当向数组添加第一个元素的时候，数组容量扩围10.

4.2 ArrayList的扩容函数

扩容的核心方法是grow方法，这个方法的参数是minCapacity，表示新的数组需要存放元素的个数。首先计算出新的容量为旧容量的1.5倍，如果新容量比minCapacity要小，那么新的容量就为minCapacity。如果新容量大于Integer.MAX_VALUE-8，如果minCapacity>Integer.MAX_VALUE-8,那么新容量为Integer.MAX_VALUE,如果minCapacity<Integer.MAX_VALUE-8,那么新容量就是Integer.MAX_VALUE-8.

/** * 要分配的最大数组大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * ArrayList扩容的核心方法。 */ private void grow(int minCapacity) { // oldCapacity为旧容量，newCapacity为新容量 int oldCapacity = elementData.length; //将oldCapacity 右移一位，其效果相当于oldCapacity /2， //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍， int newCapacity = oldCapacity + (oldCapacity >> 1); //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量， if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE， //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //对minCapacity和MAX_ARRAY_SIZE进行比较 //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小 //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小 //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

4.3 ensureCapacity方法

通过list.ensureCapacity(Num)来调用，将ArrayList底层的数组的最小长度设置为大于Num(通过grow函数来扩容)，以减少候选存放数据时扩容的次数。

5. 不常用的集合

5.1 HashTable

HashMap 是⾮线程安全的， HashTable 是线程安全的； HashTable 内部的⽅法 基本都经过 synchronized 修饰HashTable 基本被淘汰，不要在代码中使⽤它；对Null key 和Null value的⽀持： HashMap 中， null 可以作为键，这样的键只有⼀个，可以有⼀个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有⼀个 null，直接抛出 NullPointerException。

5.2 Vector

Vector类的所有方法都是同步的。可以由两个线程安全地访问同一个Vector对象，但是一个线程访问Vector的话要在同步操作上耗费大量的时间。 ArrayList不是同步的，所以不需要保证线程安全的时候建议使用ArrayList。

5.3 Set

HashSet：无序，唯一。基于HashMap实现，底层使用HashMap来保存元素LinkedHashSet:继承与HashSet，内部使用LinkedHashMap实现。TreeSet：有序，唯一。底层数据结构是红黑树。能够按照添加元素的顺序进行遍历。

5.4 Map

LinkedHashMap: 继承自HashMap，它的底层仍然是数组+链表/红黑树。但是在上面的结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。TreeMap：底层使用了红黑树，有序的。