Collection集合
1、概述
集合类中也是使用了JDK8中的一些新的特性,在源码中可以体现。
迭代器接口:
public interface Iterable<T> {
// 返回一个泛型的迭代器
Iterator<T> iterator();
// jdk8中的默认实现,默认遍历方式
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
// 可以看到调用的是函数式编程中的accept方法。如何消费自己指定
for (T t : this) {
action.accept(t);
}
}
// 分离,基本上不怎么常用
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
再看下Collection接口:
public interface Collection<E> extends Iterable<E> {
// 集合中的个数
int size();
// 集合是否为空
boolean isEmpty();
// 集合中是否包含了某个元素
boolean contains(Object o);
// 返回迭代器
Iterator<E> iterator();
// 将集合中的元素转换成Object类型的数组
Object[] toArray();
// 泛型方法。将集合转换成数组
<T> T[] toArray(T[] a);
// 向集合中添加元素
boolean add(E e);
// 移除某个元素
boolean remove(Object o);
// 如果存在,进行移除。可以看到操作的是从迭代器中来操作的
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
// 将集合进行清空操作
void clear();
// equals和hashCode方法
boolean equals(Object o);
int hashCode();
// 转换成流方法的使用
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
可以看到的主要是针对集合的操作。那么怎么操作决定了子类实现类中对数据结构的实现来决定的。
对于常见的集合实现来说,常用的有List和Set集合
那么先看下List常见的实现类:
可以看到List接口中的方法和Collection中是类似的
2、ArrayList源码分析
先看下ArrayList的源码:
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.List集合的初始化值大小是10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances
* 共享空数组实例数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
* 共享空数组对于默认的list集合。当第一次添加元素的时候,会用EMPTY_ELEMENTDATA
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
* 数组缓冲区用来存储数组中的元素的,ArrayList的容量就是这个缓冲区的容量。
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
* 数组中元素的个数
* @serial
*/
private int size;
/**
* Constructs an empty list with the specified initial capacity.
* 构造出来一个指定容量的空list,可以指定容量。如果不指定,默认是10
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
* 上面如果没有指定,那么就使用这个来进行指定
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
}
上面主要是介绍了ArrayList的介绍,在共享数组中是没有元素的空数组;如果指定了容量,那么将会直接创建出来指定容量的数组,如果没有指定,那么将会在创建的时候先使用一个空的数组;如果没有指定容量,那么将会在第一次添加的时候再次进行初始化,而我们通常使用的就是第一种。
那么来看一下add方法的操作:
/**
* Appends the specified element to the end of this list.
* 在list集合的尾部来进行追加元素
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 确定内部容量是否足够。这里的size是初始值,默认是0
ensureCapacityInternal(size + 1); // Increments modCount!!
// 这里分为两步操作。elementData[size] = e; size++;
elementData[size++] = e;
return true;
}
那么接下来看一下,如何确保容量实现的:
private void ensureCapacityInternal(int minCapacity) {
// 确保显示容量
// ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
// 将上面的进行拆分,划分如下。计算容量
int result = calculateCapacity(elementData, minCapacity);
// 确定容量
ensureExplicitCapacity(result);
}
从计算容量开始,开始开辟存储数据的空间:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 可以从空参构造那里看到,初始化的时候是这个空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 取出来最大值,因为size初始值是0,这里的minCapacity是1,那么取出来最大值就是1。最终的最大值就是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 如果已经指定了容量,那么就直接走这一步
return minCapacity;
}
可以确定,这里是将数组中的长度进行确定好了。那么再次进入到下一步:
private void ensureExplicitCapacity(int minCapacity) {
// modCount+1
modCount++;
// 考虑溢出的代码
// 将上面传入进来的容量作为参数来进行校验,确定最小容量是否大于数组长度。如果大于,那么将进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 扩充到原来的1.5倍是从这里来的
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新的数组容量仍然小于旧的,俺么就使用旧的容量。
if (newCapacity - minCapacity < 0)
newCapacity = 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);
}
这里就是指定了原来的数组和新的容量大小:
@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
// 这一步将Object类型的数组转换成T[]的
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 最终会调用这个数组来进行操作
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
也就是说这种操作会将数组中的元素一直在后面追加,从0下标开始进行拷贝,直到指定的大小。
所以在添加元素中,首先判断的是数组是否是空的,如果是空的,首先进行初始化,指定容量;如果不是空的,那么考虑是否应该进行扩容;最终将元素放入进去。
那么追踪下:什么时候开始进行扩容?
public boolean add(E e) {
// 确定内部容量是否足够。这里的size是初始值,默认是0
ensureCapacityInternal(size + 1); // Increments modCount!!
// 这里分为两步操作。elementData[size] = e; size++;
elementData[size++] = e;
return true;
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 可以从空参构造那里看到,初始化的时候是这个空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 取出来最大值,因为size初始值是0,这里的minCapacity是1,那么取出来最大值就是1。最终的最大值就是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 如果已经指定了容量,那么就直接走这一步
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 将上面传入进来的容量作为参数来进行校验,确定最小容量是否大于数组长度。如果大于,那么将进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
第一次添加的时候,size为0,size+1为1,添加第一个元素,这个时候走到了ensureExplicitCapacity方法中的判断中的时候,不会来进行扩容。
但是当第9次添加的时候,size+1为10,但是依然不会大于elementData.length,因为默认初始化就是10;
那么当是第10次添加的时候,size+1位11,这个时候,大于了,就会走扩容阶段的方法。默认是10,也就是说扩容的时间发生在数组中元素满了的时候,先进行尝试添加,然后添加进去的时候判断空间是否足够,不足够再进行扩容。
3、重要方法
其实有很多,但是唯一一个值得一提的是clear方法
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
可以看到这里的clear是依次循环将立面的元素置为null。所以我们在使用的时候,通常也不会来进行使用。