【Java】年轻人不讲武德，一起聊聊List集合（一）

前言

业精于勤荒于嬉，行成于思毁于随；

在码农的大道上，唯有自己强才是真正的强者，求人不如求己，静下心来，开始思考…

今天一起来聊一聊 List集合，看到这里，笔者懂，大家莫慌，先来宝图镇楼 ~

【Java】年轻人不讲武德，一起聊聊List集合（一）

我要打十个年轻人，敢偷袭我老同志，耗子尾汁..

咳咳.. 相信大家满脑子的ArrayList已被保国爷爷经典的画面以及台词冲淡了，那么，目的已达到，那我们言归正传，对于屏幕前帅气的猿友们来说，ArrayList，LinkedList，Vector，CopyOnWriteArrayList... 张口就来，闭眼能写，但是呢，我相信大部分的猿友们并没有刨根问底真正去看过其源码，此时，笔者帅气的脸庞似有似无洋溢起一抹微笑，毕竟是查看过源码的猿，就是那么的不讲武德，吃我一记闪电五连鞭，话不多说，来吧，展示..

一、List类图

【Java】年轻人不讲武德，一起聊聊List集合（一）

二、源码剖析


1. ArrayList（此篇详解）


  • 构造函数

    // 默认值-空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList底层为数组 transient关键字：当前数组不能被序列化
transient Object[] elementData;
/**
* 构造函数
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

从源码中可以看出，构造只为底层数组进行初始化，默认值为空数组；

  • add() - 添加元素方法

    // ArrayList元素个数
private int size;
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 记录对ArrayList操作次数
protected transient int modCount = 0;
// ArrayList最大元素个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 添加入口
*/
public boolean add(E e) {
// 对数组进行初始化以及扩容
ensureCapacityInternal(size + 1);
// 数组中添加元素
elementData[size++] = e;
return true;
}
// 1.对数组进行初始化以及扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 2.计算最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断数组是否为空，即为第一次添加元素
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// max方法：a >= b ? a : b
// eg: 10 >= 1 -> 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 3.判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
// modCount(记录修改次数) -> 在当前线程使用迭代器的过程中，如有其他线程修改了modCount(会判断是否修改操作有误(线程安全问题)) -> 抛出ConcurrentModificationException异常
//      Fail-Fast 机制，快速失败机制，modCount声明为volatile，保证线程之间修改的可见性
modCount++;
// 判断是否进行扩容
if (minCapacity - elementData.length > 0)
// 具体扩容方法
grow(minCapacity);
}
// 4.具体扩容
private void grow(int minCapacity) {
// 获取数据长度
int oldCapacity = elementData.length;
// 计算扩容后长度，第一次为例：0 + (0 >> 1) = 0 + 0 = 0
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判断如果扩容后长度-最小容量<0,扩容后的长度为最小容量，此判断作用于第一次添加元素时
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 计算扩容后长度最大值，最大值为Integer的最大值(2^31-1)
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
// 使用 Arrays.copyOf 对我们数组容量实现扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}

从源码中可以看出，添加元素时且会对数组进行初始化或者扩容；

知识点：
第一次扩容也就是第一次add时：数组长度length扩容为10，集合size为1；
第二次扩容也就是第十一次add时：数组长度length扩容为15，集合size为11；
之后每次扩容遵循以下规则，oldCapacity + (oldCapacity >> 1)；

结论：
每扩容后为之前数组长度的1.5倍，最大值：Integer最大值(2^31-1)，最小值：10；


  • get() - 获取元素方法

    /**
* 入口
*/
public E get(int index) {
// 校验是否越界
rangeCheck(index);
// so easy：通过下标获取元素
return elementData(index);
}
// 校验下标是否越界
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
}

从源码中可以看出，获取元素时就是获取数组元素，通过下标直接获取即可；

  • remove() - 删除元素方法

    /**
* 入口
*/
public E remove(int index) {
// 校验下标是否越界
rangeCheck(index);
// add()方法中已详情描述
modCount++;
// 获取要删除的元素
E oldValue = elementData(index);
/**
* public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
*  说明此方法参数作用：
*      src：源数组
*      srcPos：源数组复制的起始位置
*      dest：目的数组
*      destPos：目标数组放置的起始位置
*      length：数组元素被复制的数量
*/
// 对应参数中length
int numMoved = size - index - 1;
// 删除元素其实就是一个数组整体移动的过程，再将最后一个元素置空即可
if (numMoved > 0)
// 此每个参数都需各位猿友细品下，慢慢来，只是一个过程... 如此如此，这般这般，暖男的我在下方提供图，便于猿友们理解
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// 将最后一个元素置空，如只有一个元素，置空即可，便于GC工作
elementData[--size] = null; // clear to let GC do its work
// 返回删除的元素值
return oldValue;
}

从源码中可以看出，删除元素实则为数组移动覆盖的过程，已下图为例，便于大家理解：

  • 源数组：

【Java】年轻人不讲武德，一起聊聊List集合（一）

  • 目标数组(删除元素后的数组)：

【Java】年轻人不讲武德，一起聊聊List集合（一）

  • 删除下标为0的元素(不)

结合 arraycopy(Object src, int srcPos, Object dest, int destPos, int length)来讲，可得知：

  1. src：为上述源数组；

  2. srcPos：源数组要复制的起始位置为(index+1 = 0+1 = 1)

  3. dest：为上述目标数组

  4. destPos：目标数组放置的起始位置为(index=0)；

  5. length：复制的长度为(size-index-1 = 4-0-1 = 3)

  • 过程演示：

【Java】年轻人不讲武德，一起聊聊List集合（一）

  • ==划重点：==

相信之前没仔细研究过的猿友们，对ArrayList删除元素大概过程已有一些了解；

但对于有经验的开发猿来说，笔者大概能猜到两种，一种是一心追随本心道心坚固的猿友，另一种呢就是追求大道审视局势的猿友；

前者：看到这里，不论是从笔者的描述还是图文结合的理解，貌似有一定的道理，但当时的我看并不是如此，既然是arraycopy，那就不应该是移动覆盖，而是重新复制一个新数组。

后者：我当时查阅源码好像觉得也并不是这样的，记得也是复制一个新数组，而不是移动覆盖。但笔者描述确又很在理，难道...遗漏了什么？

邪魅一笑，嘴角微起，来吧，展示...
【Java】年轻人不讲武德，一起聊聊List集合（一）
其实嘛，大家说的都没错，实际上确实是复制新的数组，但ArrayList这里，源数组和目标数组是用一个呢.

哎...人生么，如此这般，细节决定成败。

  • ArrayList总结：


2. LinkedList

不讲武德，一起聊聊List集合之LinkedList

3. Vector

不讲武德，一起聊聊List集合之Vector

4. CopyOnWriteArrayList

不讲武德，一起聊聊List集合之CopyOnWriteArrayList

5. List集合对比分析-总结篇

不讲武德，一起聊聊List集合之总结篇

~~   码上福利


大家好，我是猿医生：

在码农的大道上，唯有自己强才是真正的强者，求人不如求己，静下心来，开始学习吧...

以上是 【Java】年轻人不讲武德，一起聊聊List集合（一） 的全部内容， 来源链接： utcz.com/a/94463.html

回到顶部