本文共 9222 字,大约阅读时间需要 30 分钟。
ArrayList
实现于 List
、RandomAccess
接口。可以插入空数据null
,也支持随机访问。
List
接口中的特有的增删改查:
add( int index , Object element )
删:remove( int index )
//注意是下标而不是元素 改:set( int index , Object newElement )
查:get(int index)
ArrayList
相当于动态数据,其中最重要的两个属性分别是:
elementData
数组,以及 size
大小。 在调用 add()
方法的时候:
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
如果是调用 add(index,e)
在指定位置添加的话:
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++; }
其实扩容最终调用的代码:
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); }
也是一个数组复制的过程。
删除指定下标index的元素:
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; }
void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
删除指定元素:可以删除null(因为可以存入null)
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; }
int java.util.AbstractList.modCount 来自AbstractList
The number of times this list has been structurally modified. 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.
This field is used by the iterator and list iterator implementation returned by the iterator and listIterator methods. If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a ConcurrentModificationException in response to the next, remove, previous, set or add operations.
This provides fail-fast behavior
, rather than non-deterministic behavior in the face of concurrent modification during iteration.
Use of this field by subclasses is
optional.
If a subclass wishes to provide fail-fast iterators (and list iterators), then it merely has to increment this field in its add(int, E) and remove(int) methods (and any other methods that it overrides that result in structural modifications to the list). A single call to add(int, E) or remove(int) must add no more than one to this field, or the iterators (and list iterators) will throw bogus ConcurrentModificationExceptions. If an implementation does not wish to provide fail-fast iterators, this field may be ignored.
Fail Fast Iterator | Fail Safe Iterator | |
---|---|---|
Throw ConcurrentModification Exception(抛异常?) | Yes | No |
Clone object(克隆被操作对象?) | No | Yes |
Memory Overhead(内存开销) | No | Yes |
Examples(栗子) | HashMap,Vector,ArrayList,HashSet | CopyOnWriteArrayList,ConcurrentHashMap |
查询方法源码: 可见底层是使用数组的访问方式
E elementData(int index) { return (E) elementData[index]; } public E get(int index) { rangeCheck(index); return elementData(index); }
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
由此可见 ArrayList
的主要消耗是数组扩容以及在指定位置添加数据,在日常使用时最好是指定大小,尽量减少扩容。更要减少在指定位置插入数据的操作。
由于 ArrayList 是基于动态数组实现的,所以并不是所有的空间都被使用。因此使用了 transient
修饰,可以防止被自动序列化。
transient Object[] elementData;
因此 ArrayList 自定义了序列化与反序列化:
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; i0) { // 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
当对象中自定义了 writeObject 和 readObject 方法时,JVM 会调用这两个自定义方法来实现序列化与反序列化。
从实现中可以看出 ArrayList 只序列化了被使用的数据。
RandomAccess 是一个空接口,实现它有什么用处呢?
public interface RandomAccess { }
在接口的注释中指明:
Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.
The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.
It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:
for (int i=0, n=list.size(); i < n; i++) list.get(i); runs faster than this loop: for (Iterator i=list.iterator(); i.hasNext(); ) i.next();
Vector
内部有两个重要的参数,一个是elementCount代表当前元素个数,一个是capacityIncrement,代表当列表元素满了之后增加的容量。如果不设置capacityIncrement,那么Vector容量扩展时默认将扩展两倍,在ArrayList源码分析中,我们知道ArrayList在扩容时默认将扩展1.5倍,所是ArrayList与Vector的一个区别。
Vector
也是实现于 List
接口,底层数据结构和 ArrayList
类似,也是一个动态数组存放数据。不过是在 add()
方法的时候使用 synchronized
进行同步写数据,但是开销较大,所以 Vector
是一个同步容器并不是一个并发容器。
以下是 add()
方法:
public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }
private void ensureCapacityHelper(int minCapacity) { // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
扩容算法:
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //如果没有设置capacityIncrement ,那么扩展为原来的两倍 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
以及指定位置插入数据:
public void add(int index, E element) { insertElementAt(element, index); } public synchronized void insertElementAt(E obj, int index) { modCount++; if (index > elementCount) { throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } ensureCapacityHelper(elementCount + 1); System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); elementData[index] = obj; elementCount++; }
Stack 是Vector的子类;class Stack extends Vector
Stack方法:
方法 | 修饰符 | 描述 |
---|---|---|
push(E item) | 无 | 使用Vector的addElement(item)方法返回item |
pop | synchronized | 弹出栈顶元素(移除) |
peek() | synchronized | 返回栈顶元素(删除) |
empty | 无 | 是否为空 |
search(Object o) | synchronized | 查找是否有对象o |
Stack内部一共五个方法,其中三个方法都加了synchronized关键字,是线程安全的,而push和empty方法调用了Vector的方法,由于Vector中的addElement()和size()方法都是线程安全的,所以Stack的每个方法也都是线程安全的,所以它和Vector一样,都是线程安全的。
参考:
转载地址:http://olwji.baihongyu.com/