重新理解基础数据结构(动态数组,链表)

1 最近在准备面试发现 ArrayList 扩容机制总是死记硬背过段时间就忘。索性花几小时彻底啃一遍源码争取一次拿下、终身不忘。2 ArrayList 底层是动态数组。Java 原生数组一旦定义长度就不可变使用场景受限。ArrayList 就是对数组的一层优化封装让我们可以动态增删元素提高开发效率。3 ArrayList底层(这里是JDK1.8)3.1 在创建数组时,底层会创建一个新的Object[]的空数组只有当你添加元素时即add()方法时,先判断是不是原来的空数组,是的话会和10取最大值也就是说只有第一次添加元素才能进入上面的判断,这样capacity就是10了3.2 当数组的元素个数超过和等于10,就会触发扩容grow()后续每次扩容是将int newCapacity oldCapacity (oldCapacity 1) newCapacity 10 101 等于15,扩容成原来的1.5倍 这也是为什么是1.5倍,为什么这么设计是为了空间和性能上的考虑,1 因为能最大化复用之前的内存碎片,举个列子2倍的 [空闲10],[空闲20],[空闲40],[空闲80] 16010204080,就是前面释放的内存随便不够扩容之后使用,1.5倍10 → 15 → 22 → 33,10 15 22 47 ≥ 33,可以够扩容后新数组使用,这就是最大化复用之前释放的内存碎片.2 平衡内存占用和扩容次数,3 1.5 倍可以利用二进制位移高效计算3.3 扩容的长度的临界值判断,新的数组长度newCapacity和MAX_ARRAY_SIZE比较,MAX_ARRAY_SIZE是Integer.MAX_VALUE-8,这8个字节是用存储数组这个对象头的信息,如果newCapacity是负数,直接OOM说明扩容是超出了Integer.MAX_VALUE了,如果比Integer.MAX_VALUE大就返回给你Integer.MAX_VALUE,否则就返回Integer.MAX_VALUE-83.4 最后将原数组拷贝到新数组中赋值给原数组