Java集合分析 前言
从开始接触Java的时候, 就在强调的一个重要版块, 集合. 终于能够开始对它的源码进行分析, 理解, 如果不懂得背后的思想, 那么读懂代码, 也仅仅是读懂了 if else 仅仅是读懂了代码的逻辑而已, 对背后深藏的原因, 却没有能力进行一个深入的探究.
我会知道为什么这样写, 但我却不知道这样写的优点, 我知道 for 可以进行循环, 但却不知道这里为什么要做这个循环. 而正是这样的原因, 读代码变成一件很枯燥的事情. 所幸, 现在是有一定的能力进行一个初步的探究.
集合Java中常用到的集合, 无非是 LinkedList, ArrayList, HashSet, TreeSet, HashMap, TreeMap 并不是说 其他的集合并不重要, 而是现在没有提到的必要.
初步学过算法, 对红黑树, 散列表 符号表的空间时间运行效率, 存储量等概念才有了一个比较初步的认知.
而并发, 安全性, 强弱引用, Stream流等目前并不在考虑范围内.
需要注意的是:
以下提到的有序, 指的是按照 Comparable的实现进行排序后的有序, 而非按照输入的顺序来进行排序.
ArrayListArrayList 是线程不安全的集合, 如果想要在多线程情况下使用:
List list = Collections.synchronizedList(new ArrayList(...));
允许元素为空, 同时数组和插入时的顺序一致.
实现:
add()
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } 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); }在ArrayList中, 并没有太多值得关注的地方, 但还是需要知道他的扩容策略. 从上面不难知道, 在第一次扩容的时候, 会扩容至DEFAULT_CAPACITY 也就是10, 如果超过10, 则会扩容1.5倍.
在之前使用 ArrayList的时候, 一般不指定长度, 如果需要存储800个元素.
就需要经过11次扩容, 每次都需要重新创建数组, 复制元素.
另一个问题是如果需要存储元素不超过10000个, 但在扩容的时候, 会达到14000, 占据不必要的空间. 因此在使用的时候,最好对自己的元素上限有所估计, 选取合适的值. 使用 ArrayList(int capacity)构造函数.
同时会看到一个比较有趣的参数 modCount, 表示修改次数.当调用删除和添加操作的时候, 都会令这个值加1, 而当批量添加或删除的时候, 也仅仅只增加一次.
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; }这里有个细节, elementData[--size] = null;删除的时候将元素置为null, 回收. 在这里就不难发现, 在每次remove的时候, 都会将整个数组重新复制一遍.
特别是在 remove(Object o)时, 需要将整个数组遍历一遍, 先查找, 后复制. 随着数组越来越大, 成本越来越高.
removeAll()
public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }从这里就可以看出一种比较有效的处理方式, 对待这种底层为数组的数据结构的时候, 需要提供 removeAll() 这种批量删除的操作, 在这里就只需要将数组遍历的同时复制一遍, 即可.
所以不难想象, 当需要批量删除的时候, 将被删除的元素在第一遍遍历的时候存进另一个集合. 而后再通过 removeAll() 操作一次性删除, 效率会远远高于找到一个删除一个. 当然这同样需要根据数据的特点来看, 如果本次需要删除的数据量特别大, 用于存储删除元素的集合 也要选取 TreeSet这样的有序集合, 因为 contains()效率远高于 ArrayList()方法;