一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之ArrayList

怼烎@ 2023-03-02 04:48 23阅读 0赞

[一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之ArrayList][ArrayList_LinkedList_HashMap_HashSet -----_ArrayList]  
[一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之LinkedList][ArrayList_LinkedList_HashMap_HashSet -----_LinkedList]  
[一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之HashMap][ArrayList_LinkedList_HashMap_HashSet -----_HashMap]  
[一文搞定ArrayList、LinkedList、HashMap、HashSet -----源码解读之HashSet ][ArrayList_LinkedList_HashMap_HashSet -----_HashSet]

### 一、ArrayList 源码解读 ###

ArrayList的定义：继承`AbstractList`实现了`List`、`RandomAccess`、`Cloneable`、`Serializable`接口。

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable

为了解读`ArrayList`类，先解读接口的作用

--------------------

### 1、`Serializable`接口解读 ###

该接口是一个空接口，作用是将类进行序列化和反序列化，如果一个类想要进行序列化但是没有实现该空接口，则会报`java.io.NotSerializableException`异常

package java.io;//在java.io包下
    
    public interface Serializable { 
    }

例如`未序列化的`普通`User`实体代码

import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public class User { 
    
        private String username;
        private Integer age;
    
    }

测试代码：将对象写入文件`1.txt`(这个过程称为序列化)

import java.io.*;
    
    public class TestDemo1 { 
        
        public static void main(String[] args) throws Exception { 
            User user = new User("张三", 18);
            ObjectOutputStream outputStream=new ObjectOutputStream(new FileOutputStream("1.txt"));
            outputStream.writeObject(user);
            outputStream.close();//关闭流
        }
    
    }

会发现报`User`对象 未序列化异常  
解决方式就是在User加上Serializable接口

import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    import java.io.Serializable;
    
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public class User implements Serializable { 
    
        private String username;
        private Integer age;
    
    }

然后重新执行代码会发现能够写入`1.txt`文件，序列化后的内容不用看懂！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70]  
进行反序列化的操作则代码应该是

import java.io.*;
    
    public class TestDemo1 { 
    
        public static void main(String[] args) throws Exception { 
            User user = new User("张三", 18);//创建对象
    
            //序列化到文件中
            ObjectOutputStream outputStream=new ObjectOutputStream(new FileOutputStream("1.txt"));
            outputStream.writeObject(user);
            outputStream.close();
    
            //反序列化
            ObjectInputStream inputStream=new ObjectInputStream(new FileInputStream("1.txt"));
            Object o = inputStream.readObject();
            inputStream.close();
            System.out.println(o);
        }
    
    }

输出结果：  
![在这里插入图片描述][20200727165845771.png]

--------------------

### 2、`Cloneable`接口解读 ###

Cloneable接口的作用是将对象`浅拷贝（内嵌对象只是复制地址）`出另一个对象  
要想使用该接口，必须重写父类`Object`中的`clone()`方法。如果不实现`Cloneable`接口则会报  
`java.lang.CloneNotSupportedException`错误，也就是将下面的`implements Cloneable`去除则会报错

省略错误的测试案例，直接实现`Cloneable`接口的`User`代码可以这样写

import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public class User implements Cloneable { 
    
        private String username;
        private Integer age;
    
        @Override
        public Object clone() throws CloneNotSupportedException { 
            return super.clone();
        }
    }

测试代码：  
会发现拷贝出来的一个对象是一个新的对象，但是有缺点，这种方式是浅拷贝

public class TestDemo1 { 
    
        public static void main(String[] args) throws Exception { 
            User user = new User("张三", 18);//创建对象
            Object user2 = user.clone();
            System.out.println(user == user2);
            System.out.println("user="+user);
            System.out.println("user2="+user2);
        }
    
    }

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

##### 证明clone()是浅拷贝 #####

`Object`中的`clone()`方法是这样定义的。这个clone方法调用的是由c编写的库，所以看不到源码的实现

@HotSpotIntrinsicCandidate
    protected native Object clone() throws CloneNotSupportedException;

Object自带的clone方法只能实现浅拷贝的作用。  
例如下面这个类进行clone拷贝的时候会出现问题

import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    class IDCard implements Cloneable { 
        private String id;
        @Override
        public Object clone() throws CloneNotSupportedException { 
            return super.clone();
        }
    }
    
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public class User implements Cloneable { 
    
        private String username;
        private Integer age;
        private IDCard idCard;
    
    
        @Override
        public Object clone() throws CloneNotSupportedException { 
            return super.clone();
        }
    }

测试案例：

public class TestDemo1 { 
    
        public static void main(String[] args) throws Exception { 
            IDCard idCard = new IDCard("123456");
            User user = new User("李四", 18, idCard);
            User user2 = (User)user.clone();//先拷贝一份user2
    		//修改idcard会导致拷贝的user2中的id也变了，说明是浅拷贝
            idCard.setId("666666");
    
            System.out.println("user1 "+user);
            System.out.println("user2 "+user2);
        }
    
    }

![在这里插入图片描述][20200727202043799.png]  
从这里可以看出默认的父类`Object`中提供的`clone()`方法是浅拷贝。也就是对于引用其他对象的属性会直接引用其地址，因此修改圆对象的属性就会修改`clone()`后的和`clone()`前的对象。  
因此重写的`clone()`方法应该修改一些，对于嵌套的对象则应该`重新new一个或者clone一个`，重新给User对象赋值，改进的代码可以这样写

我这里使用了Lombok插件，动态生成`get、set、toString、全参、无参方法`，如果要考虑性能和内存空间的利用则建议使用传统的方法`重写toString()方法`。  
关于`toString`方法不要使用`IDE`默认生成的`toString()`方法，因为字符串拼接会造成新的对象，对造成内存浪费。使用`StringBuilder`一次性生成一个字符串对象，这样就能减少字符串通过`+`拼接生成新的字符串对象的空间浪费。  
使用StringBuilder的示例代码  
IDEA提供了模板代码，按住`alt+insert`快捷键激活快捷生成代码的窗口，选择`toString()`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 2]  
一般情况下，使用下面提供的StringBuilder就可以满足需求了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 3]  
如果有自定义模板的需求，点击设置，进行添加  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 4]

@Override
     public String toString() { 
         StringBuilder stringBuilder = new StringBuilder();
         stringBuilder.append("User{")
                 .append("username='").append(username)
                 .append("',age=").append(age)
                 .append(",idCard=").append("IDCard{").append("id='").append(idCard.getId()).append("'}},");
         return stringBuilder.toString();
     }

--------------------

### 3、`RandomAccess`接口解读 ###

该接口是随机访问接口，也是一个空接口，实现该接口的集合类，随机访问更快，性能更好

> 如果实现了RandomAccess接口的集合类  
> for (int i=0, n=list.size(); i < n; i++)  
>   list.get(i); //随机获取  
> 运行速度比这个循环快：  
> for (Iterator i=list.iterator(); i.hasNext(); )  
>    i.next();//顺序获取

为了测试该接口确实对随机访问有提升速度如下实例代码

import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;
    
    public class TestDemo1 { 
    
        public static void main(String[] args) { 
            List<String> list=new ArrayList<>();
            for (int i = 0; i < 10000000; i++) { 
                list.add(i+" ");
            }
            long begin = System.currentTimeMillis();
    
            for (int i = 0; i < list.size(); i++) { 
                list.get(i);//获取元素
            }
            long end = System.currentTimeMillis();
    
            System.out.println("time="+(end-begin));
            long begin2 = System.currentTimeMillis();
            for (Iterator i = list.iterator(); i.hasNext(); ){ 
                i.next();
            }
            long end2 = System.currentTimeMillis();
            System.out.println("time2="+(end2-begin2));
        }
    
    }

会发现的确第一种方式性能更好  
![在这里插入图片描述][20200727210953432.png]  
因为ArrayList是实现了`RandomAccess`接口的所以随机访问性能会顺序访问快。

另外如果将`ArrayList`换成`LinkedList`则效率成相反  
如下差异很大，我还将数字调小了，如果更多则相差更大  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 5]  
因此请合理的应用`ArrayList`和`LinkedArrayList`，以及选择正确的遍历方法，否则会造成没必要的等待。  
`LinkedList`没有实现该接口，并且底层是由链表形成的。

### `RandomAccess`接口的使用场景(重要) ###

通过数据库持久层框架获取的集合对象，该集合类型可能实现了`RandomAccess`接口，也可能没有实现该接口。

--------------------

在实际开发过程中：可能遇到的情况  
①已有的接口数据返回的是所有数据，但是我们只想获取其中的一条数据，也就是说要进行遍历  
②已有的多组数据需要进行合并，需要进行再次封装，同样可能需要遍历（建议通过sql返回的数据就是我们想要的数据）

鉴于上面的访问效率对比。  
建议能使用sql解决的问题不要用java代码进行遍历！如果实在没办法必须遍历，则对返回的数据进行`instanceof`判断，如果实现了`RandomAccess`接口。则使用  
集合的

for (int i=0, n=list.size(); i < n; i++)
    	list.get(i); //随机获取

如果没有实现该接口则通过迭代器遍历

for (Iterator i=list.iterator(); i.hasNext(); )
    	i.next();//顺序获取

也就是说代码应该这样写 `推荐的代码`

List list = new ArrayList();/* 通过dao获取的集合数据 */
    if (list instanceof RandomAccess) {   //判断是否实现了RandomAccess接口
        for (int i = 0; i < list.size(); i++) { 
            Object obj = list.get(i);
            /** * 逻辑代码 */
        }
    } else { 
        for (Iterator i = list.iterator(); i.hasNext(); ) { 
            Object obj = i.next();
            /** * 逻辑代码 */
        }
    }

--------------------

### 4、父类`AbstractList`解读 ###

引用api文档说明  
此类提供了`List`接口的 `骨架`实现，以最小化的实现“随机访问”数据存储所需的工作（如数组）。  
对于顺序存取的数据（如`LinkedArrayList`），应优先使用`AbstractSequentialList`而不是此类。

--------------------

要实现一个`不可修改的`列表，只需扩展此类，并提供实现`get(int)`和`size()`方法。

要实现`可修改的`列表，必须额外地覆盖`set(int, E)`方法,否则，会抛出`UnsupportedOperationException`异常。如果该列表为可变大小的容器必须另外重写的`add(int, E)`和`remove(int)`的方法。

--------------------

根据Collection接口规范建议，程序员通常应该提供一个`void（无参数）`和集合构造方法，  
不像其他的抽象集合实现，程序员不必提供迭代器实现; 迭代器和列表迭代器由此类实现的，对的“随机访问”方法核心是： `get(int) set(int, E) add(int, E)和remove(int)`

--------------------

总结：继承了`AbstractList`子类的强制要求重写`get(int) set(int, E) add(int, E)和remove(int)`这几个方法，如果直接调用父类`AbstractList`的这些方法则会直接抛`UnsupportedOperationException`异常

![在这里插入图片描述][20200729000605728.png]  
![在这里插入图片描述][20200729000646136.png]  
![在这里插入图片描述][20200729000707190.png]  
![在这里插入图片描述][20200729000725719.png]  
父类`AbstractList其他方法都有自己的实现`而且`不会抛异常`以及方法不会有`abstract`声明

--------------------

### 开始解读源码 ###

--------------------

#### 解决`面试过程中常常问的1个问题`：ArrayList的初始容量为10。为什么大家都回答默认的初始容量是10，是真的吗？—实际说的不精确，在`添加第一个元素`的时候才会将容器的容量设置为10。 ####

### `ArrayList空参构造方法` ###

分析`new ArrayList();`的过程

private static final int DEFAULT_CAPACITY = 10;//类初始化就会初始化容量为10
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };//默认空元素集合数组
    transient Object[] elementData;//实际上存储元素数据的数组
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

会发现空参构造函数创建的是一个空数组`{}`,并没有如大家所说的初始容量为10，可还有很多人说`ArrayList`的默认初始容量为10，并且会发现源码中有一个静态常量`DEFAULT_CAPACITY = 10`  
之所以说默认初始容量为`10`，并不是说在创建的时候就提前分配了容量为`10`的数组。从源码很容易看出空参的ArrayList只是对实际的容器进行了一次初始化`this.elementData={}`替换`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`直接的意思就是创建一个空数组。  
当我们向容器添加一个元素的时候会调用下面3个`add()`方法的其中一个

--------------------

private void add(E e, Object[] elementData, int s) { 
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

public boolean add(E e) { 
        modCount++;
        add(e, elementData, size);
        return true;
    }

public void add(int index, E element) { 
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);//目的是将index以后的数据向后移动一位，空出index的位置，将新元素加入该位置
        elementData[index] = element;
        size = s + 1;
    }

--------------------

#### 按照习惯①大家会直接调用`add(E e)`这个方法，传入的是一个泛型E ####

看代码出现了一个成员变量`modCount`并且发现ArrayList中没有定义这个成员变量，实际上这个成员变量是继承与父类`AbstractList`，在该父类中这个成员变量是这样定义的

protected transient int modCount = 0;//默认初始化为0

会发现方法中用到了成员变量`size`这个成员是`int`类型的数据，没有赋值则会初始化为0

private int size;//会直接初始化size=0

翻译一下add过程意思就是  
`modCount 初始为0 进行自增`  
`add(e, elementData, size);调用另外一个add,翻译成add(e,{},0)`  
调用了三个参数得`add`方法这个时候就得看3个参数的add方法  
翻译过程下来就是执行下面得代码

if (0 == 0)
        elementData = grow();//添加第一个元素时符合条件，进行扩容操作，执行grow方法进行扩容
    elementData[s] = e;
    size = s + 1;

符合条件，调用扩容方法`grow()`，去看`grow()`

//2、通过无参得grow调用过来
    private Object[] grow(int minCapacity) { 
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else { //3、进入else分支，因为if不满足
        						//4、等于new Object[10] ，10和1比较最大值当然是10
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
    //1、先进来这个无参的
    private Object[] grow() { 
        return grow(size + 1);//2、间接调用有参的扩容函数
    }

最终执行有参的扩容方法  
就是`grow(0+1)`  
翻译下来就是  
`int oldCapacity = 0`  
`判断 0 > 0 吗 或者 [] != []`  
不符合条件进入else  
`return elementData = new Object[Math.max(10, 1)];`  
等同于`return elementData = new Object[10];`,

#### 这个时候才让`ArrayList`数组的容量变为10的!!! ####

也就是说这个时候容器变为10了，那么我们时从add过来的，回到执行`grow()`方法  
后面的操作是  
`elementData[0] = e;`  
`size = 0 + 1;`接着就是结束了add方法  
那么也就明白了，实际上在创建ArrayList对象的时候并没有将容器就设置为10，而是在添加第一个元素的时候才将容器进行扩容到10。

--------------------

##### 同样的道理可能调用的不是这个`add(E e)`方法而是两个参数的`add(int index,E e)`， #####

如果调用的是2个参数的`add(int index, E element)`方法  
第一行会执行检查索引和数组容量，如果索引值大于容量 或者 索引值小于0  
则会抛异常`throw new IndexOutOfBoundsException(outOfBoundsMsg(index));`  
也就是说如果是第一个元素则应该传入的 index=0这样才不会抛异常。换句话说就是`add(0,e)`e是泛型E的实例  
s=0 是否 和 `[].length=0`相等，  
符合条件执行扩容`grow()`  
与直接`add(E e)`方法不同的是，扩容后是通过  
`System.arraycopy(elementData, 0, elementData, 0+1 , 0-0);`方法将index开始，后面所有元素向后移动一位  
原型是

@HotSpotIntrinsicCandidate
        public static native void arraycopy(Object src,  int  srcPos,
                                            Object dest, int destPos,
                                            int length);

该方法的作用是拷贝一份长度为`length`的临时数组，将src数组中的`srcPos`到`srcPos+length-1`之间的数据拷贝到临时数组中。---->这里`add(int index,E e)`的用法是将index开始的元素全部后移空出一位，让新元素加入进来  
换句话说就是拷贝一份临时的空数组`[]`，然后再执行后面的  
`elementData[index] = element;`  
`size = s + 1;`和前面一样，将第一个元素放在下表为0的数组中

##### 同样的道理三个参数在一个参数的时候就调用过了，效果是一样的 #####

这里省略三个参数的add因为前面已经分析过了。

#### 解决`面试过程中经常问的第2个问题`ArrayList的扩容机制。 ####

在前面我们分析到`grow()`并且进入的是`else`分支，这次会进入到`if`分支  
从`if`开始分析，当我们添加一个元素当达到初始的默认容器大小10时，会再次调用`grow()`  
最终会进入到带参数的`grow(int minCapacity)`  
参数minCapacity就是 在容器元素个数上+1，因为添加了一个元素，所以新容器的大小至少要比原来大1

private Object[] grow(int minCapacity) { 
        int oldCapacity = elementData.length;//再次扩容，第一次扩容到10，因此这里为10
        //10>0 || 非空数组 != [] 这个条件显然成立，进入if分支
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* 最小的扩容长度 */
                    oldCapacity >> 1           /*扩容旧容器单位是旧容器长度的一半*/);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else { 
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

上面扩容数组的代码会执行下面的代码，也就说对于`add()方法`传入的`minGrowth始终为1`，因为ArrayList没有提供直接批量添加的方法所以只能一个一个添加进中，所以`minGrowth=1`  
那么也就是说`newLength = prefGrowth + oldLength;`也就是说新的长度始终=原长度+原长度一半，  
也就是1.5倍,这个答案就是面试时经常回答的问题

public static int newLength(int oldLength, int minGrowth, int prefGrowth) { 
        int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
        if (newLength - MAX_ARRAY_LENGTH <= 0) { 
            return newLength;
        }
        return hugeLength(oldLength, minGrowth);
    }

--------------------

### `ArrayList有参构造方法` ###

有了前面的基础的前提下，可以很容易知道这里做了什么事情。  
这里分3中情况  
`< 0 抛异常`  
`== 0 赋值为空数组[]`  
`> 0 初始容量为initialCapacity`

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

也就是说这里的作用只是创建一个自定义长度的初始数组。

###### `那么问题来了，这种方式的扩容机制也是扩容到原来的1.5倍吗？` ######

**在进入add操作的时候才会触发扩容！**  
继续解读源码，会发现扩容机制是一样的，只是这里的初始容量不在是默认的10，而是自定义的容量，因此扩容的时候需要注意，会按照自定义的初始长度的一半进行扩容，例如初始容量如果为`11`则对应二进制是`1011`右移一位就是`0101`对应十进制就是5，也就是说向下取整，新长度=11+11/2`(向下取整)`=11+5=16

### ArrayList面试题总结： ###

并不是在一创建ArrayList的时候容量就是10，如果是执行空参的构造函数初始的容量是0，第一次添加元素就会进行扩容，这个时候才会从容量0到10.  
如果用的是有参的构造函数，则初始容量由用户传入的值设定，后面扩容也会根据这个值进行扩容新容器长度=原来的1.5倍，如果原来的容量是奇数则向下取整`原因在于，奇数就是最后一个1，这个数字被移走了自然相当于(奇数-1)再除2`

`addAll()`方法源码

public boolean addAll(Collection<? extends E> c) { 
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }

public boolean addAll(int index, Collection<? extends E> c) { 
        rangeCheckForAdd(index);
    
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
    
        int numMoved = s - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index,
                             elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size = s + numNew;
        return true;
    }

有过前面的基础，看这个源码很简单，关键点在于扩容条件

if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);

这个点解开了我前面看代码没有看懂的地方，s + numNew实际就是=元素个数+新添加的元素个数  
也就是传入扩容的`minCapacity`，例如原先容量是10，已有7个元素，批量添加11个元素，则这里的s=7，numNew=11。按理来说扩容至18就可以，所以源码的设计就是这种想法，因此有了下面的去最大值的算法取一次性添加的个数大还是扩容机制原先的一半大，谁大就按照谁进行扩容，也就是或如果`addAll()`添加的个数如果是5个那么扩容的大小不是 7+5=12，而是10 + 5 = 15

--------------------

### 因此 这里需要注意，很可能就会在面试中考到 ###

--------------------

就是为什么源码要用`int newLength = Math.max(minGrowth, prefGrowth) + oldLength;`这样设计而不是直接  
新数组长度=原来长度+原来长度的一半。而是由一个`minGrowth`这下子我想明白了，因为`addAll`方法可能一次性添加的长度超过了原来值得一半，如果按照这种想法那么addAll就会导致一些元素超出了扩容机制1.5倍，所以这个时候得扩容机制相当于冲洗设定了初始容量，可以理解为初始容量变成了=`原容器元素个数+添加得个数`然后后面如果只是`add(E e)`进行添加元素相当于有参的构造方法设定初始容量。

`set()`方法源码，这个代码没有什么好讲的，只是修改index索引指定的内容，就是第一行做了一索引检查，并且会返回修改前的值

public E set(int index, E element) { 
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

`get()`方法源码，这个代码也没有什么好讲的，做完检查索引直接返回了索引所对应的元素。

public E get(int index) { 
         Objects.checkIndex(index, size);
         return elementData(index);
     }

`toString()`方法源码，ArrayList中没有自定义的toString()方法，  
使用的是`AbstractCollection类的toString`,  
`ArrayList继承AbstractList`,  
`AbstractList继承AbstractCollection`  
相当于继承了爷爷的`toString`方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 6]

public String toString() { 
        Iterator<E> it = iterator();
        if (! it.hasNext())
            return "[]";
    
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) { 
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }

### `迭代器 iterator()方法` ###

分析迭代器执行的过程

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { 
    	public Iterator<E> iterator() { 
            return new Itr();
        }
        // 内部类 Itr
        private class Itr implements Iterator<E> { 
            int cursor = 0;//相当于指针游标，指向的是下一个元素的索引
            int lastRet = -1;//
            int expectedModCount = modCount;
    		//判断是否由下一元素
            public boolean hasNext() { 
                return cursor != size();//索引值!=集合的大小说明集合有元素
            }
    		//获取下一个元素
            public E next() { 
                checkForComodification();//校验并发修改异常
                try { 
                    int i = cursor;
                    E next = get(i);//获取当前索引 cursor指向的元素，调用的是ArrayList中的get方法
                    lastRet = i;    //上一个返回的索引值 实际就是保存当前索引
                    cursor = i + 1; //当前索引+1，指向下一个元素。cursor时成员变量，所以全局引用
                    return next;//返回进入代码块 cursor指向的元素
                } catch (IndexOutOfBoundsException e) { 
                    checkForComodification();
                    throw new NoSuchElementException();//get方法可能抛异常，如果get失败则抛出没有元素异常
                }
            }
    		//移除元素
            public void remove() { 
                if (lastRet < 0)//如果当前要移除的元素<0说明索引不存在
                    throw new IllegalStateException();//抛出非法状态异常
                checkForComodification();//再次检查并发修改异常
    
                try { 
                    AbstractList.this.remove(lastRet);//移除当前索引的元素
                    if (lastRet < cursor)//说明有元素，因为lastRet>=0，前面已经处理了<0的情况。
                        cursor--;//cursor指向的是下一个元素位子，移除一个元素需要向前一个位置，进行自减
                    /** * 重置lastRet （对于修改相当于当前元素），说明上一个元素不存在了 * 当调用next是lastRet会重新赋值 */
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException e) { 
                    throw new ConcurrentModificationException();
                }
            }
    		//校验并发修改异常的方法
            final void checkForComodification() { 
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }

文章未完待续，后续接着深入

[ArrayList_LinkedList_HashMap_HashSet -----_ArrayList]: https://blog.csdn.net/qq_41813208/article/details/107614811
[ArrayList_LinkedList_HashMap_HashSet -----_LinkedList]: https://blog.csdn.net/qq_41813208/article/details/107651652
[ArrayList_LinkedList_HashMap_HashSet -----_HashMap]: https://blog.csdn.net/qq_41813208/article/details/107651659
[ArrayList_LinkedList_HashMap_HashSet -----_HashSet]: https://blog.csdn.net/qq_41813208/article/details/107651662
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70]: /images/20230208/f95aa5cd13874dfd8801b267503d2774.png
[20200727165845771.png]: /images/20230208/b846ce94a20e49c0822fdf72cf1b3254.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200727171626659.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4,size_16,color_FFFFFF,t_70
[20200727202043799.png]: https://img-blog.csdnimg.cn/20200727202043799.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200729130130378.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020072913030049.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200729130704657.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4,size_16,color_FFFFFF,t_70
[20200727210953432.png]: https://img-blog.csdnimg.cn/20200727210953432.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200727211754689.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4,size_16,color_FFFFFF,t_70
[20200729000605728.png]: https://img-blog.csdnimg.cn/20200729000605728.png
[20200729000646136.png]: https://img-blog.csdnimg.cn/20200729000646136.png
[20200729000707190.png]: https://img-blog.csdnimg.cn/20200729000707190.png
[20200729000725719.png]: https://img-blog.csdnimg.cn/20200729000725719.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200729051049561.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4,size_16,color_FFFFFF,t_70