jdk源码解析一之Collection

Collection架构

List

ArrayList

cloneable其实就是一个标记接口，只有实现这个接口后，然后在类中重写Object中的clone方法，然后通过类调用clone方法才能克隆成功，如果不实现这个接口，则会抛出CloneNotSupportedException(克隆不被支持)异常。Object中clone方法：

    protected native Object clone() throws CloneNotSupportedException;

具体点击此博客

RandomAccess在java.util.Collections#shuffle有用,源码如下

JDK中推荐的是对List集合尽量要实现RandomAccess接口
如果集合类是RandomAccess的实现，则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历，在效率上要差一些。反过来，如果List是Sequence List，则最好用迭代器来进行迭代。
具体请点击此博客

add

    public boolean add(E e) {
     //确定容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //可存null
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //初始化时,如设置的索引值<默认,则默认值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return 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;
        //扩充容量1.5倍
        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);
    }


    private static int hugeCapacity(int minCapacity) {
        //超过Int最大值,则异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

其他查找,修改,删除

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

   public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        //如果不是最后一个元素,则调用native
        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;
    }

总结

ArrayList可以传Null值
ArrayList扩容大小方法为grow,每次扩容当前大小的一半的容量
ArrayList本质是一个elementData数组
arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环提升效率。
ArrayList继承List接口,作者明确表示是一个意外，因为AbstractList也继承了
因为本身是数组
所以查询修改快,O(1)
删除,插入因为调用native方法,慢

LinkedList

因为继承了队列接口,所以新增了pop,poll,push,peek,offer等方法

offer&add

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

  void linkLast(E e) {
        final Node<E> l = last;
        //创建新的node
        final Node<E> newNode = new Node<>(l, e, null);
        //赋值成最后的节点
        last = newNode;
        //如果last为null,说明第一次赋值,则设置为first
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

push

    public void push(E e) {
        addFirst(e);
    }
    public void addFirst(E e) {
        linkFirst(e);
    }

    /**
     * Links e as first element.
     * 添加到第一个节点
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        //第一个值为first,因为当前节点设置为first,所以null
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        //f为null,说明第一次初始化,则最后的节点也是first
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

poll &remove

    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        //释放GC
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    public E remove() {
        return removeFirst();
    }
    public E removeFirst() {
        final Node<E> f = first;
        //为null抛出异常
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

peek&element

    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    public E element() {
        return getFirst();
    }
    public E getFirst() {
        final Node<E> f = first;
        //为null则异常
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

remove

    public boolean remove(Object o) {
        //对null的处理
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
   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;

        //first处理
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        //last处理
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        //释放GC
        x.item = null;
        size--;
        modCount++;
        return element;
    }

set

  public E set(int index, E element) {
        //index判断
        checkElementIndex(index);
        //查找
        Node<E> x = node(index);
        //修改值
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    Node<E> node(int index) {
        // assert isElementIndex(index);

        //如果小于node一半大小,从头遍历
        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;
        }
    }

总结

维护头尾2个node
查询,index<size/2则first开始,否则last开始
可以存null
因为采用链表数据结构存储
所以查询,修改慢 O(N)
插入,删除快O(1)+O(N)
peek和poll针对null做了异常处理

Vector

    public Vector() {
        this(10);
    }


    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
    private void ensureCapacityHelper(int minCapacity) {
        // 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 + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

默认10容量,且线程安全,因为添加了方法级别的同步锁,因为锁比较重量级,所以相对很少用的上.一般采用分段锁,乐观锁来加锁.

Set

HashSet

//底层维护hashMap
    public HashSet() {
        map = new HashMap<>();
    }

   public boolean add(E e) {
      //利用hashMap存key,value存储虚拟值
        return map.put(e, PRESENT)==null;
    }
   public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

底层维护hashMap
利用PRESENT作为value

LinkedHashSet

    public LinkedHashSet() {
        super(16, .75f, true);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

底层维护LinkedHashMap

TreeSet

利用PRESENT作为value
底层维护TreeMap

总结

List和Set的区别在于是否唯一
如果存储的值唯一
则Set
排序?
是:TreeSet,内部使用二叉树
否:HashSet,数组+链表存储,所以无序,但因此访问速度O(1)+链表长度
否则List
增删多:LinkedList
因为底层链表的原因,所以修改的时候,只需要修改引用即可,所以O(1)
查询多:ArrayList,线性表的原因,查询速度很快

转载：https://blog.csdn.net/Nuan_Feng/article/details/106314451