Java常用集合类分析
ArrayList
ArrayList就是动态数组，用MSDN中的说法，就是Array的复杂版本，它提供了动态的增加和减少元素，实现了Collection和List接口，灵活的设置数组的大小等好处。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
属性
// 序列化
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 空的elementDate数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认的初始化空的elementDate数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList中存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access
// ArrayList中包含的元素数
private int size;
刚开始，定睛一看，ArrayList中有三个Object数组，一下不好分别哪个存放元素。于是用反射验证自己的猜想：
public static void main(String[] args) {
ArrayList<String> strings = new ArrayList<>();
strings.add("HI");
strings.add("HE");
reflectArrayList("elementData",strings);
}
public static void reflectArrayList(String param , ArrayList<String> strings){
Class<? extends ArrayList> aClass = strings.getClass();
try {
Field elementData = aClass.getDeclaredField(param);
elementData.setAccessible(true);
for (Object o : (Object[]) elementData.get(strings)) {
System.out.println(o);
}
} catch (NoSuchFieldException | IllegalAccessException e) {
e.printStackTrace();
}
}
结果：
HI
HE
null
null
null
null
null
null
null
null
插入两个元素后，发现元素正存放在属性"elementData"中。
构造方法
ArrayList共有三个构造方法：
public ArrayList(){}
public ArrayList(int initialCapacity){}
public ArrayList(Collection<? extends E> c){}
无参构造方法将DEFAULTCAPACITY_EMPTY_ELEMENTDATA的值赋给elementData
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
int类型参数构造方法则是用于指定初始数组长度：
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
}
..
难点来了，第三个构造方法接收一个Collection集合：
测试代码：
ArrayList<String> strings = new ArrayList<>(Arrays.asList("1","2","3"));
进入构造方法
elementData = c.toArray();
..
这是构造方法的第一行代码，看着好像很简单的样子，不就是把Collection集合变成数组的形式赋给elementData。
跟进：
public Object[] toArray() {
return Arrays.copyOf(a, a.length, Object[].class);
}
这里为什么会进入Arrays的copyof方法？很简单，因为我图省事，上传构造方法传入的是Arrays.asList("1","2","3")，asList返回Arrays的内部类ArrayList，所以这里的调用Arrays.copyof。如果传入的是java.util.ArrayList，那么这里执行的应该是
public Object[] toArray() { return Arrays.copyOf(elementData, size); }
调用了Arrays.copyof，似乎是复制集合
继续：
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;
}
进入方法后先判断，传入的参数是否是Object数组，按情况将copy变为Object数组或者Array类型的变量，之后再调用System.arraycopy
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
这是个本地方法，用于进行数组复制，我试过了，是数组，当我传入ArrayList，则报错：
java.lang.ArrayStoreException: arraycopy: destination type java.util.ArrayList is not an array
而且，它会进行引用拷贝
ArrayCopyTest[] array = new ArrayCopyTest[]{new ArrayCopyTest(),new ArrayCopyTest()};
Arrays.stream(array).forEach(System.out::print);
System.out.println();
// 需要已分配空间
ArrayCopyTest[] res = new ArrayCopyTest[2];
System.arraycopy(array, 0, res, 0, 2);
Arrays.stream(res).forEach(System.out::print);
结果：
ArrayCopyTest@39ba5a14ArrayCopyTest@511baa65
ArrayCopyTest@39ba5a14ArrayCopyTest@511baa65
有意思的方法
add
加上重载方法一共由三个方法：
public void add(int index, E element) {}
public boolean add(E e) {}
private void add(E e, Object[] elementData, int s) {}
先看最简单的一个参数的重载：
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
这个modCount是ArrayList的父类AbstractList的一个属性：
protected transient int modCount = 0;
The number of times this list has been <i>structurally modified</i>. Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.
代表ArrayList集合的修改次数。
重新调用add方法：
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
这就简单啦，先判断elementData的长度够不够，不够调用grow方法增加长度，不过grow方法也没看着那么简单，
private Object[] grow() {
return grow(size + 1);
}
//又调用重载方法
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
Arrays.copyof之前说过，这里就不说了，简而言之，数组复制。
看看newCapacity方法：
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//把原来容量的基础上加0.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
一套操作下就是扩容。
再看最后一个带有index和element的add方法：
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
从参数就可以大致推断，这个方法可以将元素插入到指定位置上。
都和之前差不多，重点就在于传入System.arraycopy的参数，它让函数返回将index位置后的所有元素统一后移以为的数组。
iterator
一看就知道，用来迭代的
public Iterator<E> iterator() {
return new Itr();
}
返回一个迭代器.
这个ArrayList的内部类Itr
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
主要通过这两个属性进行迭代.
比如它的next方法
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
配合while以及hasNext方法使用,简直完美.
remove
加上重载方法一共俩.
public E remove(int index) {}//返回移除的元素
public boolean remove(Object o) {}
另外,居然看到了break-label
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
这个found的作用是为了找到符合条件的最后一个元素,之后调用fastRemove进行移除.
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
这个嘛,就是如果是最后一个元素要进行remove,则将其置为null,其他情况调用arraycopy
大家应该注意到了,modCount经常出现,但似乎没看见有啥用,要想有点了解,可以看看ArrayList中modCount的作用,这个变量可以帮助抛出并发异常,迭代器也可以凭此做到边循环边删除,可以康康【Java面试题】List如何一边遍历，一边删除？.
sort
二话不说,直接上源码:
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
modCount++;
}
可以看到,调用了Arrays.sort方法:
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}
进入TimeSort查看sort方法:
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
countRunAndMakeAscending函数是实现查找严格升序或者严格降序
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
}
最后返回的都是满足升序的个数.
这里最好看参考资料的两个关于sort的链接,我说的没他们好.
网友评论