java中的常用集合是对数据进行存储以及相关操作的api。常用的有ArrayList、LinkedList、Vector、HashSet、TreeSet、TreeMap、HashMap
ArrayList
数据结构
ArrayList的本质是一个数组 ，那么它就具有数组的所有特性 可以根据下标快速查找值
ArrayList是如何实现动态扩容的
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class accesspublic ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}ArrayList的初始化就是一个空数组
第一次添加时
public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}ensureCapacityInternal这个方法就是实现容量扩充的
/*** Default initial capacity.*/private static final int DEFAULT_CAPACITY = 10; private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}可以看到 calculateCapacity该方法中初始将容量默认为10.那么是如何扩容的呢?我们知道这个方法ensureExplicitCapacity(calculateCapacity(elementData, minCapacity))的入参是10了 接下来点进去看
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)// minCapacity 为10 length此时为0grow(minCapacity);} private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// oldCapacity 此时为0 二进制右移 然后加原值int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0) // newCapacity 就是10newCapacity = minCapacity;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);}由代码中的备注可以看出来 第一次添加oldCapacity 为0 所以最后newCapacity 为初始默认值10，也就是说 第一次添加后 数组的 容量变为10 ，长度为1。在不超过数组长度添加值时，数组不再进行扩容，那么当第十一次添加呢? oldCapacity 为数组length为10 10的二进制为1010 右移两位为0101 相加得1111 为15。当第16次添加时，为22 因此 ArrayList就是以原值得近似1.5倍扩容得
LinkedList
LinkedList的本质是一个双向链表，那么它具有双向链表的所有特性
LinkedList的添加方法
public boolean add(E e) {linkLast(e);return true;} void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}第一次添加时，l为null，那么该节点就是first节点，第二次添加，last首先为第一次添加的节点Node的pre指向第一个节点。l.next指向新添加的节点，双向链表就构建完成了。
Vector为什么不推荐使用了?
Vector也是一个动态扩容的数组，跟ArrayList很类似，我们来看一个添加的方法。
public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}与ArrayList几乎一摸一样，唯一不同的就是Vector的每个方法上都加了synchronized 关键字，每个方法都是同步的，这就导致了Vector的执行效率是很低的。但是如果有数据安全的问题，也可以考虑使用 List<String> strings = Collections.synchronizedList(Arrays.asList("1", "2")); 将LIst转换成线程安全的list
public HashSet() {map = new HashMap<>();}HashSet的本质就是一个HashMap
public TreeSet() {this(new TreeMap<E,Object>());}TreeSet的本质就是可以看到new了一个TreeMap
TreeMap是如何实现的?
TreeMap的本质就是一颗红黑树，提供一个红黑数在线网站，可以进行节点的添加删除等在线操作Red/Black Tree Visualization (usfca.edu)
treeMap首先定义了几个属性 左节点 右节点 父节点以及颜色 黑色。红黑树的根节点必须为黑色，接下来看一下TreeMap的添加操作
// 新增节点首先颜色初始化为红色
x.color = RED;
// 新增节点非根节点 并且父节点为红色时while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} else {Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}root.color = BLACK;
TreeMap的添加操作可以总结为上图 的几种情况，TreeMap底层就是对该红黑树的一个实现
Hashmap
HashMap的底层结合了链表 红黑树 和hash的技术
HashMap是如何扩容的?
1.hashMap有两个构造参数，如果采用有参构造，给定了initialCapacity容量值，则会根据下面的代码取该给定值的 向上最接近2的幂的值
2. 如果没有给定值，则会取默认的初始值16
上述有参和无参的构造方法还会设置阈值，默认设置为0.75。如果当hashMap的entry数组长度大于阈值的时候，就会触发扩容，扩容是两倍的resize
HashMap是如何解决hash冲突的?
1.去拿hash值的时候，我们可以看到，利用了扰动函数会降低hash冲突
2。如果冲突了，hashMap首先会通过链式地址法解决冲突(也就是hash冲突的数值，放到已有数值的next链表后面)，为图中的红色部分，直接挂在该节点后面。
那么黄色部分是干嘛得呢?TREEIFY_THRESHOLD默认值定义为7，也就是当该链表下面挂得数值大于等于7时，将该链表转换为红黑树
图中红色部分，将该链表转换为红黑树，会先判断该Map的size是否小于64，如果小于64，会执行resize方法进行扩容。否则，就将链表转为红黑树。
在resize方法中有这么一个方法，就是如果扩容后，数组下标的数的节点小于6了，会将红黑树重新转为链表，提高操作性能。
总结
ArrayList的本质就是一个1.5倍动态扩容的数组；LinkedList的本质就是一个双向链表的实现;Vector的本质就是每个方法都加了synchronized关键字的ArrayList. 两个Set TreeSet的本质就是TreeMap;HashSet的本质就是HashMap; TreeMap的本质就是一颗红黑树的实现;HashMap的是根据固定阈值进行两倍扩容。利用链式地址、红黑树的相互转换解决hash冲突的。
