Java容器ArrayList源码分析

电玩女神 2021-12-13 04:44 328阅读 0赞

#### 一、什么是容器 ####

容器，用来存储一类相同的数据。数组是一种容器，它是一种线性结构，在查找方面，效率非常高，但是数组的长度需要我们在创建的时候，就设定好。这一性质，让它有些时候并不占优势，所以我们就要选择一种可变的容器，如List ,Set。他们都可以用来存储相同数据，并且加入的泛型设置，可以在编译器，就对存入的数据进行类型检查，泛型提供了更安全的容器保证。（**java中容器的框架图：**）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMjk1NQ_size_16_color_FFFFFF_t_70]

> Collections：是utils包下，一个工具类，提供了很多对于集合的工具方法，简便开发。  
> Collection：是List 、Set、Queue接口的父类。（Map与Collection并没有直接关系，他们有映射依赖关系）  
> Arrays:一个操作数组的工具类

#### 1、ArraysList源码 ####

`ArrayList`是`list`接口下的一个实现类。其实用数组实现的，用数组复制来进行扩容。**（特性： 有序，可以存放相同数据）**

**1、构造方法**`public ArrayList(Collection<? extends E> c)`可以将视图集合，转换成一个可以操作的集合.

public ArrayList(Collection<? extends E> c) { 
            elementData = c.toArray();
            if ((size = elementData.length) != 0) { 
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    // 复制一份新的数组 内部也是使用System.arraycopy()方法
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else { 
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

**2、get方法**：获得指定索引的元素

public E get(int index) { 
           // 范围检查 越界抛出异常IndexOutOfBoundsException(outOfBoundsMsg(index))
            rangeCheck(index);
            // 数组插入数据
            return elementData(index);
        }

**3、set方法**：用新元素替换指定位置的元素，并返回被替换的元素

public E set(int index, E element) { 
       		// 同样 先进行范围检查
            rangeCheck(index);
    		// 获取老元素
            E oldValue = elementData(index);
            //进行替换
            elementData[index] = element;
            // 返回被替换的元素
            return oldValue;
        }

**4、add方法**：往容器中追加一个元素

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
        public boolean add(E e) { 
            ensureCapacityInternal(size + 1);  // Increments modCount!
            //size++ 先设置elementData[size] = e; 然后执行 size = size + 1
            elementData[size++] = e;
            return true;
        }
    
        private void ensureCapacityInternal(int minCapacity) { 
       	 // 如果初始数组是空{}
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            // 确定最小容纳容量 DEFAULT_CAPACITY = 10 
    		// 如果第一次进行添加 则选择目标预期容量10
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    		
            ensureExplicitCapacity(minCapacity);
        }
    
    
        private void ensureExplicitCapacity(int minCapacity) { 
        //增加modCount值 后面记录
        //该字段由迭代器和列表迭代器实现使用 expectedModCount = modCount 当这成立才正常执行next() 方法
        //否则将会抛出异常ConcurrentModificationException。
        //例如我们在foreach循环的时候，删除某一个元素，就会抛出异常。要使用迭代器的remove方法
            modCount++;
            // size+1 之后 容量不够
            if (minCapacity - elementData.length > 0)
            // 进行扩容
                grow(minCapacity);
        }
    
        private void grow(int minCapacity) { 
            // overflow-conscious code
            //获得老数组的长度
            int oldCapacity = elementData.length;
            // 新的长度 = old+old长度 右移1位 也即是扩容老数组的一半 如果是基数 则往下取整
            //如:老数组 10 10>>1 = 5
            // 新数组 = 10 + 5
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 第一次的时候 newCapacity：0 minCapacity：10 要容量设置为10
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
                //考虑溢出
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            /
            //复制旧数组，设置容量为newCapacity 返回数组
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    	
    	//当出现很大的容纳能力的时候
        private static int hugeCapacity(int minCapacity) { 
        //如果溢出抛出异常
            if (minCapacity < 0) //
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

**流程小结：**  
**一、list刚创建执行add方法**  
1、当执行`new ArrayList<>()`的时候，底层会创建一个默认的空数组`{}`  
2、执行`add()`方法，先会确定期望容量，(数组初始的容量是0)，add之后最小的容量是`size+1`、认的容量`DEFAULT_CAPACITY`值为`10`，选取两者较大的一个，作为新的最小容量  
3、如果所需要的需容量，小于实际数组的容量。那么进行扩容操作`grow()`,否则直接执行添加方法。  
4、`扩容:` `newCapacity = oldCapacity + (oldCapacity >> 1)`计算出，新的`容量`，然后`Arrays.copyOf`复制旧数组的元素到新的数组，完成扩容。（其中进行了防止最大，负数溢出处理）

**5、remove方法**：移除list的index位置的元素。

public E remove(int index) { 
            rangeCheck(index); // 检查越界
            //每次操作都会 modCount++
            modCount++;
            // 取出数据
            E oldValue = elementData(index);
            // 需要移动的元素的个数
            int numMoved = size - index - 1;
            if (numMoved > 0)
            //元素： 1 2 3 4 5 
            // 0 1 2 3 4 remove(2)
            // numMoved = 2 
            // 1 2 4 5 null
            // 0 1 2 3 4 
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
              // 将最后一个元素 设置为 null 
            elementData[--size] = null; // clear to let GC do its work
    		// 返回移除的元素
            return oldValue;
        }

##### 二、迭代器Iterator #####

> 迭代器：提供一种方法顺序访问一个聚合对象的各个元素，且不需要暴露对象的内部表示形式。

因为集合的种类有，`List<T>`,`Map<K,V>`,`Set<T>`,有着不同的存储方式，这导致我们操作集合的时候，需要使用不同的方法。但是集合的内部存在的迭代器的设计模式，对于不同的集合，可以通过`迭代器`来访问，迭代器提供了一套接口访问和集合（具体细节又迭代器实现，对用户来说是透明的。）这样就方便了我们对集合的操作。  
**传统通过for循环遍历集合**

List<String> list = new ArrayList<>();
            list.add("A");
            list.add("B");
            list.add("C");
            list.add("D");
            for (int i = 0; i <list.size() ; i++) { 
                System.out.println(list.get(i));
            }

**可以使用迭代器遍历**

// 获得 list的迭代器
       Iterator<String> iterator = list.iterator();
       // 内部有指针指向每一个元素 
       //判断是否有下一个元素
            while (iterator.hasNext()){ 
            // 输出当前指针指向的元素 并且指针移动 
                System.out.println(iterator.next());
            }

#### ArrayList的迭代器 ####

// 实现迭代器接口
       private class Itr implements Iterator<E> { 
            int cursor;   // 有一个游标 初始值0 
            int lastRet = -1; // 当到达最后一个元素返回 -1 
            // 每次操作会判断expectedModCount = modCount是否相等 迭代器维护着元素的索引，
            int expectedModCount = modCount;
            public boolean hasNext() { 
            	// 光标没到最后一个 就返回true
                return cursor != size;
            }
    
            @SuppressWarnings("unchecked")
            public E next() { 
                checkForComodification(); // 判断expectedModCount = modCount是否相等 不相等抛出异常ConcurrentModificationException
                int i = cursor;
                if (i >= size)
                    throw new NoSuchElementException();
                 // 获得数组
                Object[] elementData = ArrayList.this.elementData;
                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 { 
                	//调用外部类的 remove方法 删除最后一个元素
                    ArrayList.this.remove(lastRet);
                    cursor = lastRet;
                    lastRet = -1;
                    // 显示使得两个相等
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) { 
                    throw new ConcurrentModificationException();
                }
            }
        }

#### 注意： ####

遍历集合的时候移除元素，要使用迭代器的remove方法，使用list.remove()会导致`expectedModCount != modCount`，，从而抛出异常`ConcurrentModificationException`\*\*,因为集合在被遍历期间内容发生变化，就会修改`modCount`的值，每当迭代器使用`hashNext()，next()`时都会检查,`expectedModCount`是否与其相等。相等正常遍历，否则，抛出异常。

**（ArrayList对象维护着，`modCount`,每次操作会修改`modCount`）  
（迭代器器里有一个`expectedModCount`初始值与`modCount`，相等每次`hashNext()，next()`都会检查两者是否相等）**

> jdk注释的解释：  
> 如果Map的结构修改，迭代器创建后的任何时间，以任何方式除了通过迭代器的remove方法，迭代器将抛出一个ConcurrentModificationException。因此，在并发修改的面前，迭代器失败迅速和干净，而不是冒着任意的，非确定性的行为在未来的一个不确定的时间。  
> 注意迭代器不能快速失败行为得到保证的话，一般来说，不可能在不同步的并发修改的存在作出难以保证。快速失败迭代器扔ConcurrentModificationException尽最大努力的基础上。因此，要写一个程序，依靠这一例外的正确性错误：快速失败迭代器的行为只能用来检测错误。（所以不能用来保证）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczMjk1NQ_size_16_color_FFFFFF_t_70]: /images/20211210/16de8feb415e4eb9a3539a096f2badb1.png