[java学习]java容器源码初探(1)

一、动态数组ArrayList

在我们开发者眼中，这就是一个“动态数组”，可以“动态”地调整数组的大小，虽然说数组从定义了长度后，就不能改变大小。
实现“动态”调整的基本原理就是：按照某个调整策略，重新创建一个调整后一样大小的数组，然后将原来的数组赋值回去。
下面我们来解析一下几个与数组不一样的方法。

看看ArrayList中主要的几个字段（源码剖析）：

// 默认的初始数组大小
private static final int DEFAULT_CAPACITY = 10;

// 空数组的表示
private static final Object[] EMPTY_ELEMENTDATA = {};

// 数据保存的数组，主体就是它
private transient Object[] elementData;

// 数组元素个数（不一定等于数组的length）
private int size;

添加元素（源码剖析）：

public boolean add(E e) {
    // 判断数组需不需要扩容，需要就扩容（动态调整数组大小的关键方法）
    ensureCapacityInternal(size + 1);
    // 数组元素赋值，数组元素个数+1
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    // 监测是否是数组越界
    rangeCheckForAdd(index);
    // 判断数组需不需要扩容，需要就扩容（动态调整数组大小的关键方法）
    ensureCapacityInternal(size + 1);
    // index和index的元素向后移动
     System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // index位置上赋值
    elementData[index] = element;
    // 数组元素+1
    size++;
}

删除元素，这里注意，并没有真正的缩小数组的大小，只是修改size的值（源码剖析）：

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);
    // 移除引用，方便GC回收
    elementData[--size] = null;
    return oldValue;
}

public boolean remove(Object o) {
    if (o == null) {
        // 遍历数组，查找到第一个为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;
}
// 与E remove(int index)的差不多，我就不多说了。
// 这里我就不明白，remove(int index)和fastRemove(int index)明明可以代码复用，为何不复用代码呢？
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // 置null，让GC可以回收它
    elementData[--size] = null;
}

看看最重要的数组扩容方法（源码剖析）：

private void ensureCapacityInternal(int minCapacity) {
    // 判断数组是否为空数组
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // 修改次数+1
    modCount++;
    // 判断需不需要扩容：比较数组大小和需要扩容的大小
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 增加容量开始
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // x1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        // 扩容的大小太小了
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 扩容的大小不会超过最大容量Integer.MAX_VALUE-8
        newCapacity = hugeCapacity(minCapacity);
    // 数组复制
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList被称为“动态数组的原理”，大致就如源码解析中注释。里面还有其他数组操作的方法，这里就不多讲，其实思路也是差不多的，一切以源码为准。

二、链表队列LinkedList

（双向）链表+队列（Deque）。以前我一直以为LinkedList只是个链表而已，没想到它可以当队列用。

看看结点代码，一看就知道是双向的结点（源码）：

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;
    }
}

几个重要字段（源码解析）：

// transient：不被序列化
// 结点个数
transient int size = 0;
// 第一个结点
transient Node<E> first;
// 最后一个结点
transient Node<E> last;

简单的看看链表的代码（源码解析）：

// 添加结点
public void add(int index, E element) {
    // 检查index是否越界
    checkPositionIndex(index);
    if (index == size)
        // 添加最后一个
        linkLast(element);
    else
        // 添加到原index结点前面
        linkBefore(element, node(index));
}
// 删除结点
public E remove(int index) {
    // 检查index是否越界
    checkElementIndex(index);
    // 解除结点链接
    return unlink(node(index));
}
// 查找结点
public E get(int index) {
    // 检查越界了没
    checkElementIndex(index);
    // 开始查找
    return node(index).item;
}
// “真正”是使用这个方法来查找
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;
    }
}

简单的看看队列的代码（源码解析）：

// 入队
public boolean offer(E e) {
    return add(e);
}
// 也是入队
public boolean add(E e) {
    // 接到最后一个结点
    linkLast(e);
    // 个人觉得这个return true没必要，完全可以无返回值void，以为如果入队失败linkLast会抛异常。既然是抛异常了，就不会return false了，那就没必要return true。
    return true;
}
// “温柔地”取队头元素，队为空不会抛出异常，只会返回null
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
// “粗暴地”取队头元素，队为空抛出NoSuchElementException异常
public E element() {
    return getFirst();
}
// “温柔地”出队，队为空不会抛出异常，只会返回null
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// “粗暴地”出队，队为空抛出NoSuchElementException异常
public E remove() {
    return removeFirst();
}

三、安全的动态数组Vector

加锁版的ArrayList（线程安全）。方法实现与ArrayList差不多，不同的是线程不安全的方法都加上锁（synchronized）了，这里就不讲啦。
一般不使用Vector而使用ArrayList，除非在多线程环境下（万不得已）才使用Vector。

四、栈Stack

栈，父类是Vector，所以你懂的（加锁版动态数组）。既然父类“安全”了，作为子类的栈也要“安全”了（加锁！），这么说栈也不是很快嘛~。
Stack规定数组最后一个元素为栈顶元素。

入栈（源码解析）:

// 不加锁？父类Vector的addElement已经加锁了，所以不加多余的锁。
public E push(E item) {
    // 添加元素到数组最后一个元素的后面
    addElement(item);
    // 返回压入栈的元素
    return item;
}

出栈（源码解析）:

// 出栈
public synchronized E pop() {
    E obj;
    // 栈中元素个数
    int len = size();
    // 取栈顶元素
    obj = peek();
    // 移除最后的一个元素（就是移除栈顶元素啦）
    removeElementAt(len - 1);
    // 返回移除的栈顶元素
    return obj;
}
// 取栈顶元素
public synchronized E peek() {
    int len = size();
    if (len == 0)
        // 空栈异常
        throw new EmptyStackException();
        // 取数组最后一个元素
    return elementAt(len - 1);
}

栈中元素查找，从栈顶（最后一个数组元素）到栈底（第一个数组元素）（源码解析）:

public synchronized int search(Object o) {
    // 找到最后一个符合要求的元素
    int i = lastIndexOf(o);
    if (i >= 0) {
        // 找到了
        return size() - i;
    }
    // 没找到
    return -1;
}

五、优先队列PriorityQueue

PriorityQueue实现了优先队列（默认最小堆）。
实现优先队列的难点：需要调整堆。
调整堆的方法有：上滤和下滤。

几个重要字段（源码解析）：

// 默认的初始化容器大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 元素数组
private transient Object[] queue;
// 元素个数
private int size = 0;
// 比较器（可拓展），可以为空，为空的话E就必须实现Comparable接口。
private final Comparator<? super E> comparator;
// 修改次数
private transient int modCount = 0;

添加元素（入队）（源码解析）：

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    // 修改次数+1
    modCount++;
    int i = size;
    // 判断是否应该扩充数组
    if (i >= queue.length)
    // 数组扩容
        grow(i + 1);
    // 数组元素增加1
    size = i + 1;
    if (i == 0)
    // 第一个入队的元素
        queue[0] = e;
    else
    // 因为有元素加入，需要调整堆（从下到上）：上滤
        siftUp(i, e);
    return true;
}

我们来看看调整堆的方法（源码解析）：

上滤（源码解析）：

// 选择比较器上滤还是Comparable对象的上滤
private void siftUp(int k, E x) {
    if (comparator != null)
        // 优先选择有比较器的进行上滤
        siftUpUsingComparator(k, x);
    else
        // Comparable对象的上滤
        siftUpComparable(k, x);
}

// Comparable对象的上滤
private void siftUpComparable(int k, E x) {
    // 强制转换成Comparable对象，这样才能有下面的比较
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        // k是子结点在数组中的下标，(k-1)/2可以求出父结点下标
        int parent = (k - 1) >>> 1;
        // 取得父结点
        Object e = queue[parent];
        // 如果key大于或等于父节点
        if (key.compareTo((E) e) >= 0)
            break;
        // key小于父结点
        // 父结点与子结点交换值
        queue[k] = e;
        // k跑到父结点的位置
        k = parent;
    }
    // 赋值到合适位置
    queue[k] = key;
}
// 使用比较器的上滤（解析和siftUpComparable一样）
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

下滤（源码解析）：

// 下滤（和上滤一样有两次方式）
private void siftDown(int k, E x) {
     if (comparator != null)
         siftDownUsingComparator(k, x);
     else
         siftDownComparable(k, x);
 }
 // Comparable对象的下滤
 private void siftDownComparable(int k, E x) {
     Comparable<? super E> key = (Comparable<? super E>)x;
     // 计算出非叶子结点个数
     int half = size >>> 1;
     while (k < half) {
         // 计算出左孩子的位置
         int child = (k << 1) + 1;
         // 取得左孩子的对象
         Object c = queue[child];
         // 右孩子的位置
         int right = child + 1;
         // 如果右孩子存在，并且左孩子大于右孩子
         if (right < size &&
             ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
             // 选择右孩子作为与父结点的比较对象
             c = queue[child = right];
         // 父子结点比较
         if (key.compareTo((E) c) <= 0)
             // 如果父节点小于或等于子结点，则找到要调整的位置
             break;
         // 子结点值赋值到父结点
         queue[k] = c;
         // 换子结点进入下次循环的比较
         k = child;
     }
     // 找到调整的位置，赋值
     queue[k] = key;
 }
 // 使用比较器的下滤（解析和siftDownComparable一样）
 private void siftDownUsingComparator(int k, E x) {
     int half = size >>> 1;
     while (k < half) {
         int child = (k << 1) + 1;
         Object c = queue[child];
         int right = child + 1;
         if (right < size &&
             comparator.compare((E) c, (E) queue[right]) > 0)
             c = queue[child = right];
         if (comparator.compare(x, (E) c) <= 0)
             break;
         queue[k] = c;
         k = child;
     }
     queue[k] = x;
 }

总结：阅读一下java容器包中的类后，对数据结构的了解又加深了一层，确实源码里的都是“好东西”。这里的讲的类还不全面，未完持续！