jdk源码解析一之Collection

太过爱你忘了你带给我的痛 2023-02-12 04:28 23阅读 0赞

### 文章目录 ###

*  Collection架构
 *  List
 *   *  ArrayList
     *   *  add
         *  其他查找,修改,删除
         *  迭代器
         *  总结
     *  LinkedList
     *   *  offer&add
         *  push
         *  poll &remove
         *  peek&element
         *  remove
         *  set
         *  总结
     *  Vector
 *  Set
 *   *  HashSet
     *  LinkedHashSet
     *  TreeSet
 *  总结

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70]

# Collection架构 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 1]

# List #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 2]

## ArrayList ##

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

protected native Object clone() throws CloneNotSupportedException;

[具体点击此博客][Link 1]

RandomAccess在java.util.Collections\#shuffle有用,源码如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 4]  
JDK中推荐的是对List集合尽量要实现RandomAccess接口  
如果集合类是RandomAccess的实现，则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历，在效率上要差一些。反过来，如果List是Sequence List，则最好用迭代器来进行迭代。  
[具体请点击此博客][Link 2]

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

### 迭代器 ###

public Iterator<E> iterator() {
        
            return new Itr();
        }
    
        /**
         * An optimized version of AbstractList.Itr
         */
        private class Itr implements Iterator<E> {
        
            //记录下一个返回的值索引
            int cursor;       // index of next element to return
            //记录上一个返回的值索引
            int lastRet = -1; // index of last element returned; -1 if no such
            //记录修改次数,根据迭代器和ArrayList的修改次数判断是否并发修改,从而快速失败
            int expectedModCount = modCount;
    
            Itr() {
        }
    
            public boolean hasNext() {
        
                return cursor != size;
            }
    
            @SuppressWarnings("unchecked")
            public E next() {
        
                //检查是否并发修改
                checkForComodification();
                int i = cursor;
                //没有多余的元素
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                //执行到这里说明确保有多余的元素,可i依旧>数组长度,说明中间执行了删除操作,则并发异常
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }
    
            public void remove() {
        
                if (lastRet < 0)
                    throw new IllegalStateException();
                //检查是否并发修改
                checkForComodification();
    
                try {
        
                    //删除上一个元素
                    ArrayList.this.remove(lastRet);
                    //移动到删除元素的下一个元素
                    cursor = lastRet;
                    //重置,防止remove之后再次remove,也就是一个next对应一个remove
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
        
                    throw new ConcurrentModificationException();
                }
            }
    
            @Override
            @SuppressWarnings("unchecked")
            public void forEachRemaining(Consumer<? super E> consumer) {
        
                Objects.requireNonNull(consumer);
                final int size = ArrayList.this.size;
                int i = cursor;
                if (i >= size) {
        
                    return;
                }
                final Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length) {
        
                    throw new ConcurrentModificationException();
                }
                while (i != size && modCount == expectedModCount) {
        
                    consumer.accept((E) elementData[i++]);
                }
                // update once at end of iteration to reduce heap write traffic
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
    
            final void checkForComodification() {
        
                //当修改次数和迭代器不一致,则说明并发修改,直接fail-fast Iterator,快速失败并抛出异常
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }

### 总结 ###

默认容量10,本质是一个elementData数组,可以传Null值  
扩容大小方法为grow,每次扩容当前大小1.5倍  
实现了RandomAccess，所以在遍历它的时候推荐使用for循环提升效率。  
继承List接口,作者明确表示是一个意外，因为AbstractList也继承了  
因为本身是数组,元素的物理存储地址是连续的,所以查询修改快,O(1)  
删除和插入因为调用native方法,后续节点向前偏移,所以慢,o(n)

当采用迭代器遍历的时候,利用mod和迭代器的expectedModCount记录修改次数,根据迭代器和ArrayList的修改次数判断是否并发修改,从而快速失败

迭代器执行remove后,重置lastRet,这样避免避免一个next对应一个remove

## LinkedList ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 5]  
因为继承了队列接口,所以新增了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 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 6]

## 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,线性表的原因,查询速度很快

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201211162314289.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200524141003642.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200524141315225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200524141733679.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/qq_37113604/article/details/81168224
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200524142623952.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70
[Link 2]: https://blog.csdn.net/keda8997110/article/details/8635005
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020052415462593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200524170258445.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L051YW5fRmVuZw==,size_16,color_FFFFFF,t_70