根据实现的接口可以将java容器分为Collection和Map两部分,其中还可以按照是否线程安全来继续划分,大部分线程安全的实现在JDK1.5之后新增的concurrent包中。
本文先讨论Collection中比较基础的两个List实现ArrayList
和LinkedList
,前者通过数组,后者通过链表。数组的好处在于有位置索引,可以按下标任意访问,并且由于数组在内存上的连续性,因此访问会更快,但前提是元素必须排列紧凑, 这样在进行插入删除时就免不了要进行移动,而且由于数组长度不可变,在添加元素时可能需要扩容和复制处理。链表可以弥补数组在插入删除上的缺陷,但代价是牺牲查询的效率,尤其是按位置索引访问时,它只能选择从头或者从尾开始依次遍历。
在讨论之前先整体看下Collection的体系结构,可以看到其实有很多的实现类,它们分别用来应付各种不同的场景
另外,在看容器类的实现之前,最好先对[java 泛型 ]有个比较好的理解,因为容器类是促成java泛型最主要的原因之一
1. ArrayList ArrayList相当于对数组做了一层代理,它在插入删除时做了两件事: 1、负责对数组进行扩容处理,在插入元素时可能造成数组越界,而ArrayList会提前检查并进行扩容; 2、负责对数组元素进行移动,以保证元素在位置上的连续性,在指定位置插入或删除元素时可能要对前后的元素进行移动;
1.1. 属性 :java.util.ArrayList 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class ArrayList <E> extends AbstractList <E> implements List <E>, RandomAccess, Cloneable, java.io.Serializable { private static final int DEFAULT_CAPACITY = 10 ; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 ; private static final Object[] EMPTY_ELEMENTDATA = {}; transient Object[] elementData; private int size; ... }
1.2. 接口实现 主要看一下add
和remove
以及迭代器的实现,其他操作基本都可以在此基础上实现
1.2.1. add :java.util.ArrayList mark:20-39 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public boolean add (E e) { ensureCapacityInternal(size + 1 ); elementData[size++] = e; return true ; } private void ensureCapacityInternal (int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity (int minCapacity) { modCount++; if (minCapacity - elementData.length > 0 ) grow(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); } private static int hugeCapacity (int minCapacity) { if (minCapacity < 0 ) throw new OutOfMemoryError (); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
看add实现主要就是看下ArrayList是如何对数组进行扩容的,这里真正体现了什么是简单即复杂 (要想写出更简单的代码则要付出更多的思考与努力),上面的代码逻辑很少,却涵盖了所有的场景,可以梳理一下作者的思路:
记原数组长度为oldCapacity,记其1.5倍为newCapacity,并记增加元素最低所需长度为minCapacity
首先比较minCapacity与defaultCapacity,取较大者并记为minCapacity(确保首次扩容后至少为defaultCapacity)
再比较newCapacity与minCapacity,取较大者并记为newCapacity(如果newCapacity < minCapacity,则有三种可能情形:1.5倍之后长度小于10;1.5倍之后溢出;addAll接口,1.5倍之后不足以放下新做的元素;)
最后,如果newCapacity <= MAX_ARRAY_SIZE,则扩容完成,否则newCapacity超过了MAX_ARRAY_SIZE(包括溢出),那么再看minCapacity: 如果 minCapacity 没有达到 MAX_ARRAY_SIZE,那么先扩为 MAX_ARRAY_SIZE; 如果 minCapacity 超过了 MAX_ARRAY_SIZE,但是没溢出(小于 Integer.MAX_VALUE)则扩为 Integer.MAX_VALUE; 如果 minCapacity 溢出,那么异常退出;
其实扩容实现能这么简洁干净,有两个判断比较关键:newCapacity - MAX_ARRAY_SIZE > 0
:表示 newCapacity 超过了 MAX_ARRAY_SIZE,包括溢出的可能minCapacity > MAX_ARRAY_SIZE
:表示 minCapacity 超过了 MAX_ARRAY_SIZE,但是没有溢出
可以通过画图来描述得更清晰些(假设这里 minCapacity 每次只比需比 oldCapacity 大 1):
如果 oldCapacity 在 A-B 之间,则 newCapacity 扩到 B 点; 如果 oldCapacity 在 B-C 之间,则 newCapacity 扩为 1.5 倍,要是 1.5 倍之后落在 D-E 之间,那么先改成扩到 D 点; 如果 oldCapacity 在 C-D 之间,则 newCapacity 扩到 D 点; 如果 oldCapacity 在 D-E 之间,则 newCapacity 扩到 E 点;
1.2.2. remove :java.util.ArrayList 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 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 ; } 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 ; }
remove的思路很简单,就是将目标元素之后的元素整体前移一位,然后再删除末尾的元素,不过要注意remove(Object o)
的含义只是删除第一个equals成立的元素。
1.2.3. iterator :java.util.ArrayList 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 public Iterator<E> iterator () { return new Itr (); } private class Itr implements Iterator <E> { int cursor; int lastRet = -1 ; int expectedModCount = modCount; public boolean hasNext () { return cursor != size; } 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]; } public void remove () { if (lastRet < 0 ) throw new IllegalStateException (); checkForComodification(); try { ArrayList.this .remove(lastRet); cursor = lastRet; lastRet = -1 ; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException (); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining (Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this .size; int i = cursor; if (i >= size) { return ; } final Object[] elementData = ArrayList.this .elementData; if (i >= elementData.length) { throw new ConcurrentModificationException (); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } cursor = i; lastRet = i - 1 ; checkForComodification(); } final void checkForComodification () { if (modCount != expectedModCount) throw new ConcurrentModificationException (); } }
ArrayList
的iterator
返回的是一个迭代器的私有实现 ,后面其它容器对于迭代也都是类似的处理,这种实现方式的好处是统一了容器对于迭代的实现。另外,将接口实现为内部类可以很容易的在实现中访问当前类的内部状态,而不受访问权限的限制,并且这样可以使代码更加简洁,不至于定义太多public类而显得过于臃肿 。
2. LinkedList LinkedList通过前后引用将元素串在一起形成一个链表,然后只需要记住两端的节点(称为哨兵节点),即first
和last
,便可以访问链表上任意位置的元素。
另外,LinkedList除了实现了List
,还实现了双端队列Deque
,因此在非线程安全环境下,它完全可以当作队列或者栈来使用,对应的java也提供了数组实现ArrayDeque
,只是很少用到,因为一般用到队列的场景都涉及到线程安全的考虑。
2.1. 属性 :java.util.LinkedList 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class LinkedList <E> extends AbstractSequentialList <E> implements List <E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0 ; transient Node<E> first; transient Node<E> last; private static class Node <E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this .item = element; this .next = next; this .prev = prev; } } ... }
2.2. 接口实现 还是看一下添加和删除的实现
2.2.1. add 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 public void add (int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } void linkLast (E e) { final Node<E> l = last; final Node<E> newNode = new Node <>(l, e, null ); last = newNode; if (l == null ) first = newNode; else l.next = newNode; size++; modCount++; } Node<E> node (int index) { if (index < (size >> 1 )) { Node<E> x = first; for (int i = 0 ; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1 ; i > index; i--) x = x.prev; return x; } } void linkBefore (E e, Node<E> succ) { final Node<E> pred = succ.prev; final Node<E> newNode = new Node <>(pred, e, succ); succ.prev = newNode; if (pred == null ) first = newNode; else pred.next = newNode; size++; modCount++; }
LinkedList的插入就是一个修改链接的过程,不过应该尽量避免指定插入位置,那样会多一个寻址过程。
2.2.2. remove :java.util.LinkedList 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public boolean remove (Object o) { if (o == null ) { for (Node<E> x = first; x != null ; x = x.next) { if (x.item == null ) { unlink(x); return true ; } } } else { for (Node<E> x = first; x != null ; x = x.next) { if (o.equals(x.item)) { unlink(x); return true ; } } } return false ; } E unlink (Node<E> x) { final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null ) { first = next; } else { prev.next = next; x.prev = null ; } if (next == null ) { last = prev; } else { next.prev = prev; x.next = null ; } x.item = null ; size--; modCount++; return element; }
remove(Object o)
的语义与ArrayList一样,删除第一个equals成立的元素,都有一个遍历比较的过程,不过即便删除指定索引的元素,LinkedList依然免不了遍历,所以考虑在LinkedList上插入删除操作的代价时,除了操作本身之外可能还有一个遍历操作。
3. 线程安全 上面的代码中都有一个modCount
计数,它被用来记录当前容器的修改次数,比如新增或删除。与其它非线程安全容器一样,它们对于并发修改都会表现出及时失败,并反馈一个ConcurrentModificationException,即当检测到modCount
不是期望值时就立即异常退出,比如上面的迭代实现。
虽然modCount
的设计初衷是为了防止并发修改,不过即便在单线程环境下也很容易触发这个异常,比如在迭代过程中通过迭代器自身之外的方法修改容器,导致expectedModCount = modCount
不成立便会异常,因此需要注意。