Java ArrayList
之前曾经参考 数据结构与算法这本书写过ArrayList的demo，本来以为实现起来都差不多，今天抽空看了下jdk中的ArrayList的实现，差距还是很大啊
首先看一下ArrayList的类图
ArrayList实现了Serializable Cloneable RandomAccess List这几个接口，可序列化，可克隆，可以随机访问
构造方法:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
之前手写ArrayList的时候，都会用一个默认容量来 new 一个数组，在jdk中实现是默认一个空数组，因为有的时候ArrayList创建后并不会添加元素
当然，这两个都是静态私有域
值得注意的是 this.elementData
是一个Object的数组 transient表示这个属性不用被序列化，通过注释可以得知，element在第一次添加的时候会被扩容到默认容量(默认为10)
add 方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add 方法中调用了 ensureCapacityInternal相当于确保容量最少是size+1，size就是当前ArrayList元素个数，然后在elementData末尾加入元素
接下来看一下是如何确保容量的
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
ensureCapacityInternal首先会调用calculateCapacity，这里主要是为了计算第一次初始化的时候，因为我们在默认初始化的时候，默认容量是10，但是为什么确保阔容是Math.max(DEFAULT_CAPACITY, minCapacity);，这里主要是因为如果我们添加一个集合的话，要确保至少大小是集合中元素的大小，否则可能会多一次扩容
然后调用ensureExplicitCapacity
ensureExplicitCapacity:先设置一下当前容器已经被更改，然后判断当前最少需要容量是不是大于数组长度，如果大于，那就扩容
private void grow(int minCapacity) {
// overflow-conscious code
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
首先获取旧数组的长度然后用旧数组长度进行扩容为1.5倍，然后判断和最小需求容量对比，如果小于最小容量，那么就扩容到最小容量那么长，然后判断是不是大于一个阈值，如果大于这个最大阈值，那么就扩容到Integer.MAX_VALUE(正整数最大值，2^31-1)
至于为什么要判断minCapacity<0，那是因为假设当前已经扩容到最大值，要是还不够，那么再扩容就是int溢出
最后把源数组copy到新的容量大小赋值给elementData,Array.copyOf底层是native方法(System.arraycopy)
之前自己写的
ArrayList都是通过oldcaptain = oldcaptain<<1+1;来进行扩容的(+1是避免旧数组长度为0的情况)，jdk对于不同的情况有不同的扩容标准，而且以前自己的Copy都是用数组遍历Copy的很笨重，这里学到了
再来看一下 add(int index,T ele)
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
这个也很好理解，就是先检查index是否在范围内(0~size)如果不在就抛出一个越界异常
然后准备扩容，接下来就是数组拷贝
System.arraycopy也是一个native方法
看一下注释就是把src从srcPos开始拷贝到dest从destPos开始的位置一共copy length这么长
如果src==dst那么这个函数表现就像先拷贝到一个临时数组，再覆盖dst对应位置
不会像
*dst++=*src++把后面的元素覆盖然后后面元素都是一个值
这样就是把elementData从index开始到最后一个元素，拷贝到src+1的位置
最后执行elementData[index] = element;把元素覆盖
然后我们看remove :
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
remove方法跟add基本同理，但是不需要扩容而且最后覆盖元素的时候是使用null填充最后一个元素
之前实现的时候没考虑到用null覆盖，这样会导致在
GC的时候，本来需要删除的元素还可以通过ArrayList找到，然后就无法GC，这里学到了
remove一个对象
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
找对应元素的话基本都是大同小异，主要是fastRemove跟自己实现的不太一样
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
fastRemove里面跟remove基本相同，少了一个index判断也没有返回值
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方法之前一直以为是直接把size设为0，但是jdk里面实现是遍历一下设null，但是这里我总觉得应该再多提供一个fastclear什么的比较好吧
设为null会让对象索引不到，可以被垃圾回收，但是如果频繁add clear的话总觉得不值得啊
再看一下一些跟集合的操作
通过一个集合初始化：
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
这里首先调用集合的toArray()方法，不过要确保elementData真的是一个Object[]数组
Java 中对象数组子类数组引用也可以转换为超类的引用
比方说 Manager 继承了 Employee
Manager[]managers = new Manager[10];
那么我们可以
Employee[]employees = managers;//完全没问题
但是如果我们在使用employees的时候在里面存放了一个new Employees，那么就会发生一个异常
这个
jdk的bug可以查一下
Java集合中toArray一般情况下都是Object[]数组，不过手动实现一个集合，有可能出问题，所以jdk采用这种方式避免了不必要的麻烦
就是避免这种情况:
ArrayList<Integer> integers = new ArrayList<>(0);
integers.add(1);
System.out.println(integers.toArray().getClass());
Integer[]integers_array = new Integer[2];
integers_array[0]=1;
integers_array[1]=2;
Class c = Arrays.asList(integers_array).toArray().getClass();
System.out.println(c);
Array.asList就是包装一个视图，里面使用add remove什么的都会抛一个异常