- ArrayList的add方法，再添加元素前，会调用ensureCapacityInternal()更新最小需要容量minCapacity，然后调用ensureExplicitCapacity() 看是否需要扩容。
- 根据传入的最小需要容量minCapacity来和数组的容量长度对比，如果minCapacity大于或等于数组容量，则需要进行扩容。
- ArrayList在第一次插入元素add()时分配10（默认）个对象空间。之后扩容会按照1.5倍增长
- 每次扩容都是通过Arrays.copyOf(elementData, newCapacity) 这样的方式实现的。ArrayList的自动扩容机制底层借助于System实现System.arraycopy(0,oldsrc,0,newsrc,length);
add方法
public boolean add(E e) {
//添加元素之前，先调用ensureCapacityInternal方法
ensureCapacityInternal(size + 1); // Increments modCount!!
//这里看到ArrayList添加元素的实质就相当于为数组赋值
elementData[size++] = e;
return true;
}
ensureCapacityInternal方法
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 获取默认的容量和传入参数的较大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
ensureExplicitCapacity方法
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容，调用此方法代表已经开始扩容了
grow(minCapacity);
}
扩容方法：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// jdk1.7采用位运算比以前的计算方式更快
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//jdk1.7这里增加了对元素个数的最大个数判断，MAX_ARRAY_SIZE 为int最大值减去8。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 最重要的复制元素方法 Arrays.copyOf() newCapacity是扩充后的数组长度。
elementData = Arrays.copyOf(elementData, newCapacity);
}
说一说Hashmap插入键值对的过程 为什么链表的长度超过8要变成红黑树，长度是6又退回链表。
-
因为AVL树插入节点或者删除节点，整体的性能是不如红黑树的。AVL每个左右节点的高度是不能大于1的。所以维持这种结构比较消耗性能。主要还是左旋右旋改变与维护AVL高度问题，红黑树比他好的就是只需改变节点颜色就可以了。
-
二分查找树，他的左右节点不平衡，一开始就固定了root，那么极端的情况下会成为链表结构。
-
链表长度越长，那么他的插入和查询效率都很低。
-
而红黑树他的整体查找，增删节点的效率都是比较高的。
原文链接：https://blog.csdn.net/yakax/article/details/108422101
长度是6的时候退化成链表，是6不是8是为了缓冲，防止频繁在链表和红黑树之间转换。以下两种情况红黑树会退化成链表。
- 扩容 resize( ) 时，红黑树拆分成的 树的结点数小于等于临界值6个，则退化成链表。
- 移除元素 remove( ) 时，在removeTreeNode( ) 方法会检查红黑树是否满足退化条件，与结点数无关。如果红黑树根 root 为空，或者 root 的左子树/右子树为空，root.left.left 根的左子树的左子树为空，都会发生红黑树退化成链表。
原文链接：https://blog.csdn.net/qq_45369827/article/details/114930945
