学习Java的集合类

(1)成员变量以及初始化

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;

 默认的大小为10。

EMPTY_ELEMENTDATA是用于无参初始化,即一个等于null的对象数组。

elemenData则用于有参初始化的变量,也是我们下面操作的主体对象。

下面看看有参初始化的源码:

public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}

此处初始化一个大小为initialCapacity的对象数组

由初始化的过程可以看出:ArrayList是基于动态数组实现的。

(2)常用操作

// Collection中定义的API
boolean add(E object)
boolean addAll(Collection<? extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection<?> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
boolean removeAll(Collection<?> collection)
boolean retainAll(Collection<?> collection)
int size()
<T> T[] toArray(T[] array)
Object[] toArray()
// AbstractCollection中定义的API
void add(int location, E object)
boolean addAll(int location, Collection<? extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
ListIterator<E> listIterator()
E remove(int location)
E set(int location, E object)
List<E> subList(int start, int end)
// ArrayList新增的API
Object clone()
void ensureCapacity(int minimumCapacity)
void trimToSize()
void removeRange(int fromIndex, int toIndex)

Add方法用于添加一个元素到当前列表的末尾
AddRange方法用于添加一批元素到当前列表的末尾
Remove方法用于删除一个元素,通过元素本身的引用来删除
RemoveAt方法用于删除一个元素,通过索引值来删除
RemoveRange用于删除一批元素,通过指定开始的索引和删除的数量来删除
Insert用于添加一个元素到指定位置,列表后面的元素依次往后移动
InsertRange用于从指定位置开始添加一批元素,列表后面的元素依次往后移动

Clear方法用于清除现有所有的元素
Contains方法用来查找某个对象在不在列表之中

TrimSize用于将ArrayList固定到实际元素的大小,当动态数组元素确定不在添加的时候,可以调用这个方法来释放空余的内存。
ToArray方法把ArrayList的元素Copy到一个新的数组中。

此处我们特殊需要看一下indexof的源码:

public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

此处可以看出,indexof是通过for循环实现的,也就是说要遍历一遍对象数组,类似的contains方法也是通过for循环来判断元素是否包含在内。

所以这类方法的效率是极其低下的,不必自己写for循环来得快,如果需要频繁使用此类快速键值查找的功能,建议使用HashMap.

(3)大小的动态调整

从add()方法看起:

public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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++;
}

add(int index, E element)

ensureCapacityInternal()函数会调用ensureExplicitCapacity()函数,检测后如果确定需要扩容,则调用grow()函数

/*
最大的容量。
一些虚拟机可能会在一个数组的头部有几位保留信息,所以是Integer.MAX_VALUE - 8
如果想创造大小超过这个极限值的ArrayList会报错:OutOfMemoryError
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/*
增长容量以保证可以容纳当前所有元素的最小长度要求。
@param minCapacity 当前的最小容量需求。
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

分析最关键的grow()函数可知:

关键:newCapacity = oldCapacity + (oldCapacity >> 1);

即newCapacity是oldCapacity的3倍

接下检查此时的大小是否合理,是否小于最小界,大于最大界(最大界定义处有一个减8的操作,是用来适应不同的虚拟机规范,有的虚拟机在数组的头部留出几位来存储一些相关信息)

调整大小后通过复制操作来重造一个数组返回给elementData

 (4)遍历方式

第一,随机访问,通过索引获取元素。ArrayList实现了RandomAccess接口。下面是get()方法源码

public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}

第二,for循环,以Integer元素为例

Integer value = null;
for (Integer integ:list) {
value = integ;
}

第三,通过迭代器(Iterator)去遍历,以Integer元素为例

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}

这三种方法中,随机访问的访问最快,迭代器的方法最慢

(5)序列化

ArrayList实现了java.io.Serializable接口,可以进行序列化,源码如下

/**
* Save the state of the <tt>ArrayList</tt> instance to a stream (that
* is, serialize it).
*
* @serialData The length of the array backing the <tt>ArrayList</tt>
* instance is emitted (int), followed by all of its elements
* (each an <tt>Object</tt>) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size); // Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
} if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
} /**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff
s.defaultReadObject(); // Read in capacity
s.readInt(); // ignored if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size); Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
05-02 14:56