Java集合篇

实现类： ArrayList，linkedList，Stack

1.ArrayList

底层数据结构：数组

初始容量：默认初始容量为10。

初始化操作：如果初始化时不指定ArrayList集合的容量，那么ArrayList集合会被初始化成一个容量为0的集合。

扩容：

ArrayList集合的扩容操作分为两种情况：在进行扩容操作前，ArrayList集合的容量值为0和不为0的情况。

在进行扩容前，ArrayList集合容量值不为0：一般会按照原始容量默认的50%增量值进行扩容，既扩大为原来容量的1.5倍。

在进行扩容前，ArrayList集合的值为0:扩大为容量为10的数组。

扩容方式采用把旧数组中的值复制到新数组的方式扩容。

添加：添加元素前判断扩不扩容。

2.linkedList

底层数据结构：带头尾节点的双向链表，双向链表的元素个数通过size属性记录，可以O(1)时间复杂度获取。

一个属性modCount的作用：防止链表在迭代器中迭代时，发生修改。

对链表进行遍历时，使用get方法时间复杂度为O(n^2)，使用加强for循环时间复杂度为O(n)。

实现类：ArrayDeque、PriorityQueue、linkeList

1.ArrayDeque实现了Deque

底层数据结构：带头尾指针的循环数组，线程不安全的

初始容量：默认初始容量为16 + 1

2.PriorityQueue

底层数据结构：数组存储的二叉堆，默认是小顶堆

初始容量：11

扩容：若原始容量值小于64，那么进行双倍扩容。若原始容量大于64，那么进行50%扩容，既扩大为原来的1.5倍。

添加：添加元素前判断扩不扩容。添加完后进行堆调整。

实现类：HashMap，TreeMap

1.HashMap

底层数据结构：数组+链表+红黑树

初始容量：16

默认负载因子：0.75 （数组元素个数/数组容量）

扩容：扩大为原来的2倍，且扩容时链表采用尾插法转移（保持原来链表的顺序）

链表转化成红黑树的条件：某一桶内链表长度为8 && 数组容量为64。

红黑树转化为链表：该桶内红黑树节点个数为6时，树退化为链表。

为什么扩容时扩大为原来的2倍？

因为hashmap在计算散列的索引时，采用的是 (n-1)&hash。 与运算。当n为2的幂次方时，n-1化为二进制为全1，一个二进制数与全1二进制数进行与操作时会得到它本身，故可以使散列相对均匀。而且在扩容时，一个节点要么在（原索引）位置，要么（原索引+原数组长度）位置上。

添加：添加元素前判断扩不扩容。

jdk1.7底层数据结构：数组+链表。扩容时链表采用头插法转移（颠倒原链表的顺序）。此种方法在并发场景下会出现循环链表的情况。

// 链表节点
Node(int hash, K key, V value, Node next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
}
// 红黑树节点
static final class TreeNode extends linkedHashMap.Entry {
     TreeNode parent;  // red-black tree links
     TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
}

2.TreeMap

底层数据结构：红黑树。红黑树并不是平衡二叉树，二者最大的区别是红黑树放弃了绝对的子树平衡，转而追求一种大致平衡，这保证了在与平衡二叉树的时间复杂度相差不大的情况下，在红黑树中新增的节点最多进行三次旋转操作，就能重新满足红黑树结构的要求。

红黑树的特性：“红不相邻”“黑平衡”

1. 红黑树根节点必须为黑色;

2.红黑树每个叶子节点都要是黑色的空节点，也就是说，叶子节点不存储数据;

3.在红黑树中任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的;

4.红黑树中每个节点，从该节点到达其可达叶子节点的所有路径，都要包含相同数目的黑色节点;

实现类：HashSet，linkedHashSet，TreeSet

1.HashSet

hashset基于hashmap实现。set里面的值即为hashmap中的key，当key重复时，不加入集合中。

2.linkedHashSet

3.TreeSet

treeset基于treemap实现。set里面的值即为treemap中的key，当key重复时，不加入集合中。

实现类：CopyOnWriteArrayList

1.CopyOnWriterArrayList

适用于读操作远远多于写操作，并且在使用时需要保证集合读操作性能的多线程场景。

底层数据结构：数组，读不加锁，更新加锁

初始容量：0

扩容（add方法）：add前扩大1个容量，通过复制操作将原数组元素转移到新数组。

set方法：修改某个索引的值，通过复制操作将原数组元素转移到新数组。

add与set都是加锁操作，且是ReentrantLock可重入锁。

get方法：不加锁获取某个索引元素。

remove：操作与add相反，操作时也加锁。

CopyOnWriterArrayList没有保证数据的强一致性，而是弱一致性。

实现类：ConcurrentHashMap

1.ConcurrentHashMap

底层数据结构：数组+链表+红黑树

加锁方式：CAS+Synchronized

初始容量、负载因子、扩容、链树转化等与hashmap规则一致。

put操作：首先用CAS判断数组某桶有无元素，无元素时直接通过CAS添加。若有元素则用Synchronized锁住该桶并添加。若在添加时发现数组正在扩容，则当前线程会参与协助扩容。

扩容操作：使用CAS技术避免同一次扩容操作被重复执行多次，采用数据标记的方式（sizeCtl）在各个参与操作的线程间同步集合状态，同样通过数据标记的方式（transferIndex）指导各个参与线程协作完成集合扩容操作和数据对象迁移操作，使用计数盒子（counterCells）解决计数器操作竞争的问题。