thumbnail
Java集合,针对于ArrayList源码解析

集合类存放于 Java.util 包中,主要有 3 种:set(集)、list(列表包含 Queue)和 map(映射)

  • Collection:Collection 是集合 List、Set、Queue 的最基本的接口
  • Map:是映射表的基础接口

在这里插入图片描述


一、Collection

List 是有序的 Collection。List 一共三个实现类:ArrayListVectorLinkedList


1.1 ArrayList

最常用的 List 实现类,内部通过 数组 实现的,允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此它 适合随机查找和遍历,不适合插入和删除

在这里插入图片描述


1.1.1 构造

无参构造(常用)

/**
 * Constructs an empty list with an initial capacity of ten.
 * 这里说了会初始化一个容量为10的空列表,但是代码中却没有
 * 那么下一步我们一般都是添加元素,所以真正初始化是在add方法中
 */
public ArrayList() {
	// 这里elementData就是储存的数据,是个数组类型,刚开始会赋值一个缺省{}
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

有参构造(初始化容量)

/**
 * Constructs an empty list with the specified initial capacity.
 * 这里会将你传入的值作为容量大小
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

有参构造(传入Collection)

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 构造一个包含指定 collection 的元素的列表,并且按照集合的迭代器返回它们的顺序
 */
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

1.1.2 常用方法


添加

add(E): boolean

这里主要说下其中的 ensureCapacityInternal 确定内部容量方法,开始看源码

// 这里参数为你列表添加下一个元素所需的长度,就是size + 1
private void ensureCapacityInternal(int minCapacity) {
   ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

其实一层套一层,又调用了3个方法

calculateCapacity:计算容量

// 如果为目前elementData为空,将替换掉你传入的minCapacity为DEFAULT_CAPACITY ,也就是会返回10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

ensureExplicitCapacity:判断容量是否够用

private void ensureExplicitCapacity(int minCapacity) {
   modCount++;
   // overflow-conscious code
   // 第一次add时,minCapacity 会被改为10,length依然是0,
   if (minCapacity - elementData.length > 0)
       grow(minCapacity);
 }

grow:这里算是ArrayList决定容量以及扩容的关键所在了

private void grow(int minCapacity) {
    // overflow-conscious code
    // 记录原数组长度
   int oldCapacity = elementData.length;
   // 位运算,新长度为原来的1.5倍
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   // 如果是首次,那么newCapacity为0,minCapacity为10,这里也就是首次赋容量值
   if (newCapacity - minCapacity < 0)
       newCapacity = minCapacity;
   // 如果超出最大容量限制,则会调用hugeCapacity获取扩容后的最大值
   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);
}

hugeCapacity:这里需要对最大值MAX_ARRAY_SIZE做个讨论

/**
 * Integer.MAX_VALUE = 2^31-1 = 2147483647, 这里定义的是减去8,原因如下
 * 1.存储 Headerwords   
 * 2.避免一些机器内存溢出,减少出错几率
 * 其实如果header长度信息大于8,就算再减去8也还是会OutOfMemoryError的,所以这里只是尽可能避免
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 在这里可以看出ArrayList真实的最大长度,其实还是Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

add(int, E):void

在指定位置插入数据,如果这个位置有数据那么统统后移,可以看下 System.arraycopy 方法

public void add(int index, E element) {
	// 检查索引越界
    rangeCheckForAdd(index);
	// 确定容量
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    /**
     * 将原数组复制到新的数组中
     * 参数1:原数组
     * 参数2:原数组起始位置
     * 参数3:目标数组
     * 参数4:目标数组的起始位置
     * 参数5:复制的长度
     */
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

addAll(Collection<? extends E> c):boolean

给定集合中的所有元素添加到 arraylist 中

addAll(int index, Collection<? extends E> c):boolean

给定集合中的所有元素添加到 指定位置arraylist 中


修改

set(int index, E element):E

用于 替换 动态数组中指定索引的元素,索引位置元素不存在则会报错

replaceAll(UnaryOperator operator):void

给定的操作内容替换掉数组中每一个元素

// 将所有元素更改为大写
words.replaceAll(e -> e.toUpperCase());

// 所有元素乘以 2
numbers.replaceAll(e -> e * 2);

删除

remove(int index):E

删除指定位置上的元素

remove(Object o):boolean

删除指定元素,可以存放null,传入null,删除null,调用了fastRemove

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
    	// 主要是移动下数组就差不都算OK了
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

removeAll(Collection<?> c):boolean

private boolean batchRemove(Collection<?> c, boolean complement) {
	// 这里可以是相当于声明了一个新的数组,将会使用w变量来作为新数组的索引长度
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
        	// complement 值为false是removeAll调用的,值为true则是retainAll求交集用的
            if (c.contains(elementData[r]) == complement)
            	// 删除操作时,这里存的是被保留下来的数据,0至w就是删除完成后数组的所有索引值
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // 在try代码中出现异常的情况下才有可能r != size,把原数组剩余的元素赋值给新数组
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        // 判断新数组长度是否等于原数组长度,如果不相同,就把w开始向后所有的元素都赋值为null,然后等待GC回收掉
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

removeIf(Predicate<? super E> filter):boolean

删除所有满足特定条件的数组元素

// 删除所有偶数元素
array01.removeIf(e -> (e % 2) == 0);
// 删除名称中带有 -bak 的元素
names.removeIf(e -> e.contains("-bak"));

removeRange(int fromIndex, int toIndex):void

删除索引范围内的元素

clear():void

将elementData中每个元素都赋值为null,等待GC回收


查找

get(int index):E

无需多言

indexOf(Object o):int

返回动态数组中o这个元素的第一次出现的索引值,不存在则返回-1

lastIndexOf(Object o):int

返回o这个元素在动态数组中最后一次出现的位置,不存在则返回-1

contains(Object o):boolean

判断元素是否在动态数组中,其实就是 indexOf(o) >= 0

forEach(Consumer<? super E> action):void

Java8中新增的方法

// 输出元素
list.forEach((sss)-> System.out.println(sss));
list.forEach(System.out::println);

// 可写入逻辑处理
list.forEach((sss)-> {});

其他操作

size():int

isEmpty():boolean

ensureCapacity(int minCapacity):void

设置指定容量大小

trimToSize():void

将动态数组中的容量调整为数组中的元素个数

toArray():Object[]

将 ArrayLsit 转为 Object型 数组

toArray(T[] a):T[]

转为T泛型数组,长度不足形参数组长度则自动补充null

retainAll(Collection<?> c):boolean

判断是否有交集,也调用了batchRemove方法,第二个参数为true

clone():Object

浅拷贝一份动态数组,不复制对象本身,新旧对象还是共享同一块内存

sort(Comparator<? super E> c):void

根据指定的顺序对动态数组中的元素进行排序

// 字符串字母元素进行升序排列
words.sort(Comparator.naturalOrder());

// 比较实体类中Integer字段
list.sort(new Comparator<Student>(){
   @Override
   public int compare(Student arg0, Student arg1) {
	   // 剔除排序字段的null值
	   if (arg0.getAge() == null || arg1.getAge() == null) return 0;
	   // 这是顺序
	   return arg0.getAge().compareTo(arg1.getAge());
   }
});

subList(int fromIndex, int toIndex):List

截取并返回动态数组中的一部分,包头不包尾

spliterator():Spliterator<E>

可分割并行遍历元素迭代器


1.2 Vector

通过 数组 实现的,支持 线程的同步,某一时刻只有一个线程能够写 Vector,避免多线程同时写而引起的不一致性,实现同步需要很高的花费,因此它比访问 ArrayList 慢


1.3 LinkedList

用链表结构存储数据,适合数据的动态插入和删除,随机访问和遍历速度比较慢。还提供了 List 接口中没有定义的方法,专门用于操作表头和表尾元素,可当作堆栈、队列和双向队列使用


二、工具类

2.1 Arrays

void Array.sort(Object[] array)

对数组按照升序排序

void Arrays.sort(Object[] array, int from, int to)

对数组元素指定范围进行排序(从下标为from,到下标to-1的元素排序)

void Arrays.fill(Object[] array,Object object)

为数组元素填充相同的值

String Arrays.deepToString(Object[][] arrays)

返回多维数组的字符串形式

boolean Arrays.equals(Object[] array, Object[] array2)

数组判断,deepEquals用于多维数组

Object[] Arrays.copyOf(Object[] array, int count)

复制自定义长度的数组

Object[] Arrays.copyOfRange(Object[] array, int from, int to)

复制自定义范围的数组

List Arrays.asList(Object[] array)

将数组转为List,原始数据类型int数组调用之后得到的List只有一个元素,这个元素就是元素类型的数组。封装类Integer调用asList是把数组中每个元素加到了List中



总结

未完待续…

上一篇
下一篇