Java集合
废话不多说，先看下集合结构。今天的三个主角都是继承自AbstractList这个抽象类，所以他们有很多的相似性（增删查操作），却因为特性所以用在不同的场景。接下来先分别介绍下，再比较说明。
Vector :它是一个封装好的线程安全的动态数组。通过synchronized对方法加锁，以此保证线程安全。Vector集合平时基本用不到。如果不是不需要线程安全，就不要使用，所以这里就不重点说了。
ArrayList :平时Java开发用的最多的就是ArrayList了，他与Vector相似，内部都是通过数组来保存元素。但是它是线程不安全的所以效率要高于Vector，但是每次超过了原来的大小就需要动态扩容，扩展需要进行copy，是一个耗时操作。ArrayList扩容增加之前的一半大小，而Vector是增加一倍大小。
LinkedList：它的内部并不是个动态数组，而是维护者一个双向列表，数组在物理空间中是连续的，链表不需要连续存储，上个元素会保存下个元素的存储地址。所以相对ArrayList的优点就在于，LinkedList的插入删除的效率很高，如果访问的效率就很低，需要遍历才可以。所以选择LinkedList还是ArrayList是需要根据业务来选择的。
这三个集合都是同一个父类，具体用法简单相似不一一介绍。以ArrayList为例，带着以下的问题出发。
- ArrayList动态数组的扩容流程？
- AbstractList中的Iterator设计模式场景？
- ArrayList的Sort排序算法？
一、ArrayList动态数组的扩容流程
先看下ArrayList的一个构造方法，一开始就设置一个动态数组大小，如果使用ArrayList之前就已经知道大致的长度是多少，就最好使用这个构造方法创建，以减少扩容的开销。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
扩容的触发动机只有在添加的时候，发现原来的数据容量不够了，才开始扩容。找个add方法作为入口查看。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 核心，确保容量够大，就执行下一步添加数据
elementData[size++] = e;
return true;
}
// 核心方法 minCapacity为数组大小加一
private void ensureCapacityInternal(int minCapacity) {
// 如果数组为{}，也就是一开始无参构造方法中给动态数组赋值{}，那么就给一个默认的大小，我的源码是10
if (elementData == 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); // 新的长度为之前的1.5倍
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:
// 之间完成copy工作，Arrays是一个处理数组的工具类
elementData = Arrays.copyOf(elementData, newCapacity);
}
到此，就基本知道如何实现扩容的了，整体比较简单，就是判断数组够不够用了，不过再多给你一半长度，完成数组的copy
二、AbstractList中的设计模式之Iterator
个人理解，迭代器模式，就是给数据源提供一个遍历操作方法，这里就是遍历操作动态数组
迭代器模式结构图
可以分为两部分理解，一部分肯定提供一个Iterator模板，比如next()。另一部分是提供数据源，并创建一个具体的Iterator，没有数据源Iterator操作什么了。
在ArrayList中将Iterator作为ArrayList的内部类，这样就可以持有外部动态数组的引用了，就可以直接操作数据源了。
三、ArrayList的Sort排序算法
直接看源码，Arrays.sort的内部使用的是一种归并和二分插入排序相结合的方法TimSort。
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c); // 给一个排序规则Comparator ，和ArrayList数据源
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
网友评论