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<E> 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源码实现,加深二叉队列排序原理的了解

HashSet、HashMap、ConcurrentHashMap的实现

HashSet底层是基于HashMap实现,限于本文篇幅过长,残余源码剖析参见下篇

《Java深入研究HashMap实现原理》

以上波及JDK源码局部均来自 JDK 1.8