Java深入研究Collection集合框架

Java集合框架位于java.util包下,主要包含List、Set、Map、Iterator和Arrays、Collections集合工具类,涉及的数据结构有数组、链表、队列、键值映射等,Collection是一个抽象接口,对应List、Set两类子接口,Map是key-value形式的键值映射接口,Iterator是集合遍历的迭代器,下面是整体框架图

集合框架整体框架图

在util包下还涉及SortedMap、SortedSet接口,分别对应Map、Set接口,在concurrent包下有常见的 ArrayBlockingQueue、ConcurrentHashMap、CopyOnWriteArrayList等实现类对Queue、Map、List接口的扩展实现,下面分别从List/Queue/Set/Map接口常用实现类一探究竟

ArrayList实现

我们先来看看初始化方式,

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
复制代码

从源码中定义的两个Object数组可知ArrayList采用数组作为基本存储方式,在String字节码中也有定义数组,不过是private final char[] value,transient关键字主要是序列化时忽略当前定义的变量;在ArrayList无参函数中给定默认数组长度为10,在实际开发中,一般如果能预知数组长度则会调用带有长度阈值的构造函数,

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}
复制代码

源码方法中会直接按照指定长度创建Object数组并赋值给this.elementData,接下来继续看看没有指定数组长度时,数组是如何扩容从而满足可变长度?此时ArrayList中的add方法登场

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
复制代码

size为ArrayList中定义的int类型变量,默认为0,当调用ensureCapacityInternal(1),继续往下看

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
复制代码

该方法会判断底层数组elementData与临时数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA是否相等,如果是就取两个阈值中的最大值,minCapacity为1,DEFAULT_CAPACITY为10(默认值),然后继续走ensureExplicitCapacity(10),

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
复制代码

modCount用于记录操作次数,如果minCapacity大于底层数组长度,开始调用扩容方法grow

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);
}
复制代码

oldCapacity为默认底层数组长度,newCapacity = oldCapacity + (oldCapacity >> 1)等价于 newCapacity = oldCapacity + (oldCapacity / 2);在Java位运算中,oldCapacity << 1 相当于oldCapacity乘以2;oldCapacity >> 1 相当于oldCapacity除以2 , 此时新的长度为原始长度的1.5倍,如果扩容后的长度小于minCapacity,则直接赋值为minCapacity,再往下的if判断中是对int最大值的边界判定,可以看到最后通过Arrays.copyOf进行数组的copy操作,这是Arrays工具类中的方法,该方法最终调用如下

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
    return copy;
}
复制代码

通过System.arraycopy进行数组复制并return this,System.arraycopy方法为native方法,对应方法如下

//原始数组      //位置     //目标数组   //位置
 public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos,
                                    int length);//copy长度
复制代码

调用一连串方法最终也只是copy一个默认长度为10的空数组,我们继续看add方法中的 elementData[size++] = e;//把当前对象放置在elementData[0]上,在ArrayList中size()方法是直接返回定义的size值,即为返回数组元素长度,而非底层数组长度(默认10),所以ArrayList在初始时就占用一定空间,下面我们看下ArrayList中的查询方法

public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    return (E) elementData[index];
}
复制代码

如果要查找List中某个对象,假如已知对象在数组中的位置,则直接return (E) elementData[index]返回,在计算算法效率中以O表示时间,此时可以以O(1)表示查询到指定对象的时间复杂度,因为通过下标查找我们只需要执行一次,如果我们无法得知具体下标,通常是for循环查找位置直到返回对象,假设数组长度为n,此时的时间复杂度为O(n),这种方式实则取的是查找到该对象所消耗的时间的最大值,有可能在for循环中第一个或是中间一个位置就已经查找到了,则可记为O(1)或者O(n/2)

LinkedList实现

LinkedList基于双向链表+内部类Node<>泛型集合实现,初始化没有默认空间大小,根据头尾节点查找元素,下面先看下双向链表的数据结构图

链表中elem为当前元素,prev为当前元素的上一个节点,next为下一个节点,LinkedList初始化时链表是空的,所以firs头节点、last尾节点都是null,下面看下初始化源码,

transient int size = 0;  //transient标记序列化时忽略
transient Node<E> first; //头节点
transient Node<E> last; //尾节点

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
复制代码

有参函数对应加入整个集合,下面先看下内部类Node的定义,

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;
    }
}
复制代码

E表示泛型元素类型,prev记录当前元素的上一个节点,next记录下一个节点,当我们往LinkedList中add一个元素时,看下源码是怎么处理Node节点,

public boolean add(E e) {
    linkLast(e);
    return true;
}
    
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++;
}
复制代码

在进行添加操作时默认是追加至last节点,linkLast方法中首先将当前数组中last节点赋值临时变量,然后调用Node<>构造函数将当前添加元素与last关联,此时l赋值给Node<>中的perv节点,接着判断l是否为null,如果是表示数组中没有元素,就直接赋值给first作为第一个,否则就追加至原数组最后一个元素的next节点,从而完成add操作,下面我们看下指定插入位置add方法,

public void add(int index, E element) {
    checkPositionIndex(index);   //校验index边界>=0 && <=size
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
Node<E> node(int index) {
    // assert isElementIndex(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) {
    // assert succ != null;
    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++;
}
复制代码

linkBefore方法中首先会调用node(int index)节点生成方法,该方法中首先通过二分法的方式判定元素插入位置,然后分别对first、last节点中的next、prev节点进行赋值操作,最后返回插入的节点元素,传递给linkBefore方法,该方法会判断传入的节点元素的上一个节点是否为null,对节点进行相应赋值操作,从而完成指定下标插入元素,下面继续看下LinkedList删除元素方法remove(int index),

public E remove(int index) {
    checkElementIndex(index);  //index边界判定>=0 && <size
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    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;
}
复制代码

删除元素方法基本都会调用unlink(Node x),原理就是把x元素的前后节点指向关系进行替换,然后将当前x元素所有属性置空,达到删除元素目的同时等待GC回收,顺带看下LinkedList查询方法

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
复制代码

核心是通过类似二分法定位下标对应的元素并返回该对象的element值,可以看到LinkedList在增删元素时,只是修改当前下标所在元素的前后节点指向关系,相对于ArrayList的copy数组效率要高,而查询元素时虽采用二分法提高查询效率,但其时间复杂度还是O(logN),二分法找一次就排除一半的可能,log是以2作为底数,相对于ArrayList直接索引查询要慢得多

Queue、Deque的实现

PriorityQueue是基于优先堆的一个无界队列，该优先队列中的元素默认以自然排序方式或者通过传入可比较的Comparator比较器进行排序,下面看下PriorityQueue的add方法源码

private static final int DEFAULT_INITIAL_CAPACITY = 11;   //队列默认大小
transient Object[] queue;                                 //队列底层数组存储结构
int size;                                                 

public boolean add(E e) {
    return offer(e);
}
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}
复制代码

在offer方法中如果插入的元素为null则会直接抛出异常,当队列长度大于等于容量值时开始自动扩容,grow方法与ArrayList的扩容方法类似,最后都调用了Arrays.copyOf方法,唯一区别在于扩容长度不一样,可自行查看此处源码,offer方法中i=0时标记为队列第一个元素,直接赋值queue[0],如果不是第一个,则开始调用siftUp()上浮方法,

private void siftUp(int k, E x) {        // k != 0
    if (comparator != null)
        siftUpUsingComparator(k, x);    //指定排序比较器
    else
        siftUpComparable(k, x);         //使用默认自然顺序比较器
}
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable,<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}
复制代码

在siftUpComparable方法中,将传入的可比较的对象转换为Comparable,如果k下标大于0,计算父节点的下标int parent = (k - 1) >>> 1 等价于int parent = (k - 1)/2;然后取出父一级的节点对象,通过compareTo方法对插入的对象于当前对象比较是否>=0,如果不大于则把当前对象赋值给k位置,再把parent位置赋值给k做替换,最后通过queue[k] = key实现元素上浮排序,继续看下remove方法

public boolean remove(Object o) {
    int i = indexOf(o);               //遍历数组找到第一个满足o.equals(queue[i])元素的下标
    if (i == -1)               
        return false;
    else {
        removeAt(i);
        return true;
    }
}
E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i)                         // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);             //调整顺序
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}
复制代码

删除元素时下标是从后往前,当i = s是最后一个元素下标时直接置空,否则从队列数组中取出要删除的元素,调用一次siftDown下沉方法对最小堆节点位置进行调整,以不指定比较器的方法源码分析

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;                          // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1;                   // assume left child is least
        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;                               //将子节点c上移
        k = child;
    }
    queue[k] = key;                                 //key向下移动到k位置
}
复制代码

根据int half = size/2 找到非叶子节点的最后一个节点下标并与当前k的位置作比较,从k的位置开始，将x逐层向下与当前节点的左右节点中较小的那个交换，直到x小于或等于左右节点中的任何一个为止,从而达到删除非最后一个元素的节点排序,相应的时间复杂度也是O(logN),通过此处的方法也可以得知在数组下标从0开始情况下,节点下标计算方式为

left = k * 2 + 1 ,right = k * 2 + 2, parent = (k -1) / 2, 当然PriorityQueue还有一些其它Queue接口的实现方法,如poll、peek方法,包括在concurrent包下的PriorityBlockingQueue,DelayQueue,ConcurrentLinkedDeque等实现Queue、Deque接口的扩展类,可自行去看下jdk 1.8源码实现,加深二叉队列排序原理的理解