一、前言

编码过程中，我们需要容器来装我们的数据或者对象。集合就是用来存放某类对象的，集合类有一个共同特点，就是它们只容纳对象（实际上是对象名，即指向地址的指针）。这一点和数组不同，数组可以容纳对象和简单数据。如果在集合类中既想使用简单数据类型，又想利用集合类的灵活性，就可以把简单数据类型数据变成该数据类型类的对象，然后放入集合中处理（基本数据的装箱与拆箱），但这样执行效率会降低。

1.1数组和集合的比较

数组不是面向对象的，存在明显的缺陷，集合弥补了数组的缺点，比数组更灵活更实用，而且不同的集合框架类可适用不同场合。如下：

数组能存放基本数据类型和对象，而集合类存放的都是对象，集合类不能存放基本数据类型。数组和集合存放的对象皆为对象的引用地址。
数组容易固定无法动态改变，集合类容量动态改变。
数组无法判断其中实际存有多少元素，length只告诉了数组的容量，而集合的size()可以确切知道元素的个数。
集合有多种实现方式和不同适用场合，不像数组仅采用顺序表方式。
集合以类的形式存在，具有封装、继承、多态等类的特性，通过简单的方法和属性即可实现各种复杂操作，大大提高了软件的开发效率

1.2 基础数据类型的装箱与拆箱

Java中有八种基本的数据类型，分别是：byte、short、char、int、long、float、double和boolean。这八种基本类型在Java中都有对应的包装类型：Byte、Short、Character、Integer、Long、Float、Double以及Boolean。

java中已经有了基本数据类型，为什么还需要包装类型呢？

这是由Java本身的语言特性决定的，Java是一种面向对象的编程语言，一切皆对象。基本类型不具备Java中对象的某些特征--对象内部可以封装一系列属性和行为，所以对应的包装类型就应运而生了。

装箱与拆箱

装箱和拆箱描述的是Java中这八种基本数据类型和对应的包装类型之间的转换过程。我们把基本数据类型转换成对应的包装类型的过程叫做装箱。反之就是拆箱。在Java中的装箱和拆箱不是人为操作的，是程序在编译的时候编译器完成这项任务的，自动拆装箱是在JDK1.5以后引入的，对于之前版本的Java，需要格外注意格式的转换。

装箱

Integer i = 20;
int j = 2;

将代码反编译之后可以得到：

Integer i = Integer.valueOf((int)20);
int j = 2;

可以看到对于数值类型直接赋值给包装类型，有一个自动装箱的操作，而自动装箱的操作就是利用了Integer中的valueOf方法，这就是前面在节约空间那部分提到的valueOf方法。Integer的valueOf方法中具有缓存的功能，也就是说在数值为-128到127之间的数据，都是被构造成同一个对象，这就是上面提到的享元模式的设计思路：

public static Integer valueOf(int i) {
 //IntegerCache.low = -128， IntegerCache.high = 127
   if (i >= IntegerCache.low && i <= IntegerCache.high)
       return IntegerCache.cache[i + (-IntegerCache.low)];
   return new Integer(i);
}

拆箱

Integer a = 100;
int b = 20;
int c = a + b;

代码反编译后得到：

Integer a = Integer.valueOf((int)100);
int b = 20;
int c = a.intValue() + b;

可以看到第一步进行了自动装箱操作，在第三行中，基本数据类型和包装类型进行运算，需要将包装类型进行拆箱操作，用到了intValue方法。在包装类型中，内部都有一个基本数据类型的字段用于存储对应基本类型的值，这个字段就是value。相应的其他包装类型在进行拆箱的时候，都会调用对应的xxxValue方法，例如：byteValue、shortValue等等方法。其实内部逻辑都是一样，直接返回存储的value值。

自动装箱和拆箱的时机

直接赋值：将一个字面量直接赋值给对应包装类型会触发自动装箱操作。
函数参数

//自动拆箱
public int getNum1(Integer num) {
    return num;
 }
//自动装箱
public Integer getNum2(int num) {
    return num;
}

集合操作:在Java的集合中，泛型只能是包装类型，但是我们在存储数据的时候，一般都是直接存储对应的基本类型数据，这里就有一个自动装箱的过程。
运算符运算:上面在拆箱操作的时候利用的就是这个特性，当基本数据类型和对应的包装类型进行算术运算时，包装类型会首先进行自动拆箱，然后再与基本数据类型的数据进行运算。说到运算符，这里对于自动拆箱有一个需要注意的地方：

Integer a = null;
int b = a;
int b = a.intValue();

这种情况编译是可以通过的，但是在运行的时候会抛出空指针异常，这就是自动拆箱导致的这种错误。因为自动拆箱会调用intValue方法，但是此时a是null，所以会抛异常。平时在使用的时候，注意非空判断即可。

自动装拆箱带来的问题

==比较

自动装箱的机制，我们不能依赖于操作符，它在一定范围内数值相同为true，但是在更多的空间中，数值相同的包装类型对象比较的结果为false。如果需要比较，可以考虑使用equals比较或者将其转换成对应的基本类型再进行比较可以保证结果的一致性。

空指针

自动拆箱的机制，如果初始的包装类型对象为null，那么在自动拆箱的时候的就会报NullPointerException，在使用时需要格外注意，在使用之前进行非空判定，保证程序的正常运行。

内存浪费

这里有个例子：

Integer sum = 0;
for(int i=1000; i<5000; i++){
 sum+=i;
}

上面代码中的 sum+=i 这个操作其实就是拆箱再装箱的过程，拆箱过程是发生在相加的时候，sum本身是Integer，自动拆箱成int与 i 相加。将得到的结果赋值给sum的时候，又会进行自动装箱，所以上面的for循环体中一句话，在编译后会变为：n = Integer.valueOf((int)(n.intValue() + i));每次调用valueOf方法都会返回一个Integer对象，所以在进行了5000次循环后，会出现大量的无用对象造成内容空间的浪费，同时加重了垃圾回收的工作量，所以在日常编码过程中需要格外注意，避免出现这种浪费现象。

二、Java集合

Java中的集合框架体系如下图：

网络异常，图片无法展示

如上图，我们可以看到Java集合有一个根父类接口Iterable（迭代接口），继承迭代接口中的方法，根据存放的数据结构不同有Collection(单列数据)和Map(双列数据)两种，在Collection的子类中有不同的数据结构实现的子类，在Map的子类有不同数据结构实现的子类，下面对这些子类进行详细介绍：

2.1 Iterable（迭代接口）

在Java中，Iterable接口是Java集合的顶级接口之一。Collection接口和Map接口都继承Iterable接口，所以Collection和Map的所有子类也实现了Iterable接口。由于集合的子类的不同特性，实现Iterable接口时采用了设计模式的迭代器模式。

Iterator,它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。

2.1.1 Iterable源码

package java.lang;
import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;
/**
 * Implementing this interface allows an object to be the target of
 * the "for-each loop" statement. See
 * <strong>
 * <a href="{@docRoot}/../technotes/guides/language/foreach.html">For-each Loop</a>
 * </strong>
 *
 * @param <T> the type of elements returned by the iterator
 *
 * @since 1.5
 * @jls 14.14.2 The enhanced for statement
 */
public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();
    /**
     * Performs the given action for each element of the {@code Iterable}
     * until all elements have been processed or the action throws an
     * exception.  Unless otherwise specified by the implementing class,
     * actions are performed in the order of iteration (if an iteration order
     * is specified).  Exceptions thrown by the action are relayed to the
     * caller.
     *
     * @implSpec
     * <p>The default implementation behaves as if:
     * <pre>{@code
     *     for (T t : this)
     *         action.accept(t);
     * }</pre>
     *
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    /**
     * Creates a {@link Spliterator} over the elements described by this
     * {@code Iterable}.
     *
     * @implSpec
     * The default implementation creates an
     * <em><a href="Spliterator.html#binding">early-binding</a></em>
     * spliterator from the iterable's {@code Iterator}.  The spliterator
     * inherits the <em>fail-fast</em> properties of the iterable's iterator.
     *
     * @implNote
     * The default implementation should usually be overridden.  The
     * spliterator returned by the default implementation has poor splitting
     * capabilities, is unsized, and does not report any spliterator
     * characteristics. Implementing classes can nearly always provide a
     * better implementation.
     *
     * @return a {@code Spliterator} over the elements described by this
     * {@code Iterable}.
     * @since 1.8
     */
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

2.1.2 源码解析

package java.lang; -->表示Iterable接口是在Java.lang下的接口
Implementing this interface allows an object to be the target of the "for-each loop" statement. See 这句话是对这个类的一个介绍，大致意思是表示：实现Iterable接口允许对象成为“for each loop”语句的目标.当我们的类实现了Iterable接口后，就可以定义一组可以迭代的Iterable对象，可以迭代其元素。
在Iterable接口中定义了三个成员方法

iterator()方法

在设计之初，设计者并没有让开发人员在实现Iterable接口直接就可以对集合进行迭代操作，而是巧妙地在Iterable接口内部定义了一个iterator()方法，当开发者调用iterator()方法后，就可以返回一个内部元素为T类型的迭代器，拿到迭代器后就可以调用迭代器内部的hasNext()和next()方法，来进行集合元素的遍历，实现了集合元素操作的隔离性。

/**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();

Iterator对象的成员方法：

网络异常，图片无法展示

hasNext() 如果有元素则继续迭代，返回true
next() 返回迭代的元素
remove() 移除返回的元素
代码示例：

List l = new ArrayList();\
l.add("aa");\
l.add("bb");\
l.add("cc");\
Iterator iterator = l.iterator();\
while (iterator.hasNext()){\
    String str = (String) iterator.next();\
    System.out.println(str);\
}

在后续介绍的集合中，不同的集合对Iterator对象的成员方法有不同的定义。

forEach

foreach方法是一个语法糖，在类加载完成后，会转化成迭代器Iterator实现，对每个元素进行特定操作，直到元素被处理完毕或抛出异常，用于循环处理集合中数据。

default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

spliterator

分割迭代器主要是用来对源数据元素进行遍历和分区。

default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }

2.2 Collection

2.2.1 Collection接口

Collection是所有单列集合的父接口，因此在Collection中定义了单列集合(List和Set)通用的一些方法，这些方法可用于操作所有的单列集合。方法如下：

1.添加元素

（1）add(E obj)：添加元素对象到当前集合中

（2）addAll(Collection<? extends E> other)：添加other集合中的所有元素对象到当前集合中。

2.删除元素

（1）boolean remove(Object obj) ：从当前集合中删除第一个找到的与obj对象equals返回true的元素。

（2）boolean removeAll(Collection<?> coll)：从当前集合中删除所有与coll集合中相同的元素。\

3.判断元素

（1）boolean isEmpty()：判断当前集合是否为空集合。

（2）boolean contains(Object obj)：判断当前集合中是否存在一个与obj对象equals返回true的元素。

（3）boolean containsAll(Collection<?> c):判断c集合中的元素是否在当前集合中都存在。即c集合是否是当前\集合的“子集”。

4.查询

（1）int size()：获取当前集合中实际存储的元素个数

（2）Object[] toArray()：返回包含当前集合中所有元素的数组\

5.交集

（1）boolean retainAll(Collection<?> coll)：当前集合仅保留与c集合中的元素相同的元素，即当前集合中仅保留两个集合的交集，即this = this ∩ coll；

2.2.2 List接口

List接口继承于Collection接口，除继承了collection的成员方法外，还有以下特性：

List集合特点：列表索引从0开始，就像数组一样，元素有序的，且可重复。
List允许您拥有'null'元素
List集合遍历：根据下标，foreach，迭代器遍历数据。
Lits集合扩容：Lits集合当我们实例出来，它的默认初始容量为10，当往List集合里面增加的数据超过10个以后，他就会扩容增加0.5倍，扩容以后就是15。即新容量 = 原容量 + 原容量 * 0.5。
List常用方法：
void add(int index, Object element) ：添加对象element到位置index上
boolean addAll(int index, Collection collection) ：在index位置后添加容器collection中所有的元素
Object get(int index) ：取出下标为index的位置的元素
int indexOf(Object element) ：查找对象element 在List中第一次出现的位置
int lastIndexOf(Object element) ：查找对象element 在List中最后出现的位置
Object remove(int index) ：删除index位置上的元素
ListIterator listIterator(int startIndex) ：返回一个ListIterator 迭代器，开始位置为startIndex
List subList(int fromIndex, int toIndex) ：返回一个子列表List ,元素存放为从 fromIndex 到toIndex之前的一个元素

元素有序不是指，我们存进Lits集合中的什么1,3,7,6他给我们从小到大，或者从大到小这样子，所谓的有序是我们该集合有下标，下标从0开始，然后我们按照什么顺序增加到list集合的，那么他就是什么样子的顺序)。

既然List的元素是有序可重复的，那我们就可以使用继承自Iterable接口的foreach方法和迭代器的方式遍历集合中的元素。

vector，ArrayList，LinkedList都是继承List，所以和List集合以上特点都是一样的。

2.2.2.1 ArrayList集合

2.2.2.1.1 对象数组

使用学生数组，存储三个学生对象，代码如下：

//学生对象类
public class Student {
    private String name;// 姓名
    private int age;// 年龄
    public Student() {
    }
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    publicvoid setName(String name) {
        this.name = name;
    }
    publicint getAge() {
        return age;
    }
    publicvoid setAge(int age) {
        this.age = age;
    }
}

对象数组的测试代码：

public class Test01StudentArray {
    public static void main(String[] args) {
        //创建学生数组
        Student[] students = new Student[3];
        //创建学生对象
        Student s1 = new Student("曹操", 40);
        Student s2 = new Student("刘备", 35);
        Student s3 = new Student("孙权", 30);
        //把学生对象作为元素赋值给学生数组
        students[0] = s1;
        students[1] = s2;
        students[2] = s3;
        //遍历学生数组
        for (int x = 0; x < students.length; x++) {
            Student s = students[x];
            System.out.println(s.getName() + "‐‐‐" + s.getAge());
        }
    }
}

Java中存储对象数据选择的容器有对象数组和集合，由上述代码可以看出，使用数组存储对象元素存在局限性，因为数组的长度是固定的，当数组的初始化以后，长度将不再可变，如果初始化的时候直接初始化一个大数据，后续使用过程中势必会造成内存资源的浪费，无法适应数据变化的需求。为了解决这个问题，Java提供了另一个容器java.util.ArrayList 集合类,让我们可以更便捷的存储和操作对象数据。

2.2.2.1.2 ArrayList集合

ArrayList是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List，RandomAccess，Cloneable，java.io.Serializable这些接口。ArrayList集合不适合随机的删除和增加.
ArrayList与Collection的关系如下图，实现代表继承，虚线代表实现接口：

网络异常，图片无法展示

ArrayList继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList实现了RandmoAccess接口，即提供了随机访问的功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。
ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
ArrayList实现了java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

2.2.2.1.2 ArrayList集合的使用

构造方法

public ArrayList() ：构造一个内容为空的集合。

基本格式:

ArrayList<String> list = new ArrayList<String>();

在JDK 7后,右侧泛型的尖括号之内可以留空，但是<>仍然要写。简化格式：

ArrayList<String> list = new ArrayList<>();

成员方法

public boolean add(E e) ：将指定的元素添加到此集合的尾部。参数 E e ，在构造ArrayList对象时，指定了什么数据类型，那么 add(E e) 方法中，只能添加什么数据类型的对象。
使用ArrayList类，存储三个字符串元素，代码如下：

public class Test02StudentArrayList {
public static void main(String[] args) {
//创建学生数组
ArrayList<String> list = new ArrayList<>();
//创建学生对象
String s1 = "曹操";
String s2 = "刘备";
String s3 = "孙权";
//打印学生ArrayList集合
System.out.println(list);
//把学生对象作为元素添加到集合
list.add(s1);
list.add(s2);
list.add(s3);
//打印学生ArrayList集合
System.out.println(list); 
    }
}

public E remove(int index) ：移除此集合中指定位置上的元素。返回被删除的元素。
public E get(int index) ：返回此集合中指定位置上的元素。返回获取的元素。
public int size() ：返回此集合中的元素数。遍历集合时，可以控制索引范围，防止越界。

public class Demo01ArrayListMethod {
public static void main(String[] args) {
//创建集合对象
ArrayList<String> list = new ArrayList<String>();
//添加元素
list.add("hello");
list.add("world");
list.add("java");
//public E get(int index):返回指定索引处的元素
System.out.println("get:"+list.get(0));
System.out.println("get:"+list.get(1));
System.out.println("get:"+list.get(2));
//public int size():返回集合中的元素的个数
System.out.println("size:"+list.size());
//public E remove(int index):删除指定索引处的元素，返回被删除的元素
System.out.println("remove:"+list.remove(0));
//遍历输出
for(int i = 0; i < list.size(); i++){ 
         System.out.println(list.get(i)); 
                           } 
                    }
        }

2.2.2.1.2 ArrayList集合源码分析

核心源码：

package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    /**
     * 默认初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 空数组（用于空实例）。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
     //用于默认大小空实例的共享空数组实例。
      //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
     * 保存ArrayList数据的数组
     */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * ArrayList 所包含的元素个数
     */
    private int size;
    /**
     * 带初始容量参数的构造函数（用户可以在创建ArrayList对象时自己指定集合的初始大小）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //如果传入的参数大于0，创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //如果传入的参数等于0，创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //其他情况，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    /**
     *默认无参构造函数
     *DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    /**
     * 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
     */
    public ArrayList(Collection<? extends E> c) {
        //将指定集合转换为数组
        elementData = c.toArray();
        //如果elementData数组的长度不为0
        if ((size = elementData.length) != 0) {
            // 如果elementData不是Object类型数据（c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断）      
            if (elementData.getClass() != Object[].class)
                //将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 其他情况，用空数组代替
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    /**
     * 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。 
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }
//下面是ArrayList的扩容机制
//ArrayList的扩容机制提高了性能，如果每次只扩充一个，
//那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。
    /**
     * 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量
     * @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        //如果是true，minExpand的值为0，如果是false,minExpand的值为10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
        //如果最小容量大于已有的最大容量
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
   //得到最小扩容量
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              // 获取“默认的容量”和“传入参数”两者之间的最大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
  //判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }
    /**
     * 要分配的最大数组大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        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);
    }
    //比较minCapacity和 MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
    /**
     *返回此列表中的元素数。 
     */
    public int size() {
        return size;
    }
    /**
     * 如果此列表不包含元素，则返回 true 。
     */
    public boolean isEmpty() {
        //注意=和==的区别
        return size == 0;
    }
    /**
     * 如果此列表包含指定的元素，则返回true 。
     */
    public boolean contains(Object o) {
        //indexOf()方法：返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1 
        return indexOf(o) >= 0;
    }
    /**
     *返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1 
     */
    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++)
                //equals()方法比较
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    /**
     * 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。.
     */
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    /**
     * 返回此ArrayList实例的浅拷贝。 （元素本身不被复制。） 
     */
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            //Arrays.copyOf功能是实现数组的复制，返回复制后的数组。参数是被复制的数组和复制的长度
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // 这不应该发生，因为我们是可以克隆的
            throw new InternalError(e);
        }
    }
    /**
     *以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。 
     *返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
     *因此，调用者可以自由地修改返回的数组。 此方法充当基于阵列和基于集合的API之间的桥梁。
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    /**
     * 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 
     *返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组，则返回其中。 
     *否则，将为指定数组的运行时类型和此列表的大小分配一个新数组。 
     *如果列表适用于指定的数组，其余空间（即数组的列表数量多于此元素），则紧跟在集合结束后的数组中的元素设置为null 。
     *（这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。） 
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // 新建一个运行时类型的数组，但是ArrayList数组的内容
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
            //调用System提供的arraycopy()方法实现数组之间的复制
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }
    // Positional Access Operations
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
    /**
     * 返回此列表中指定位置的元素。
     */
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
    /**
     * 用指定的元素替换此列表中指定位置的元素。 
     */
    public E set(int index, E element) {
        //对index进行界限检查
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        //返回原来在这个位置的元素
        return oldValue;
    }
    /**
     * 将指定的元素追加到此列表的末尾。 
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }
    /**
     * 在此列表中的指定位置插入指定的元素。 
     *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
     *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    /**
     * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。 
     */
    public E remove(int index) {
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
        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;
    }
    /**
     * 从列表中删除指定元素的第一个出现（如果存在）。 如果列表不包含该元素，则它不会更改。
     *返回true，如果此列表包含指定的元素
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        modCount++;
        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
    }
    /**
     * 从列表中删除所有元素。 
     */
    public void clear() {
        modCount++;
        // 把数组中所有的元素的值设为null
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }
    /**
     * 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    /**
     * 将指定集合中的所有元素插入到此列表中，从指定的位置开始。
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
    /**
     * 从此列表中删除所有索引为fromIndex （含）和toIndex之间的元素。
     *将任何后续元素移动到左侧（减少其索引）。
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);
        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }
    /**
     * 检查给定的索引是否在范围内。
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    /**
     * add和addAll使用的rangeCheck的一个版本
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    /**
     * 返回IndexOutOfBoundsException细节信息
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    /**
     * 从此列表中删除指定集合中包含的所有元素。 
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        //如果此列表被修改则返回true
        return batchRemove(c, false);
    }
    /**
     * 仅保留此列表中包含在指定集合中的元素。
     *换句话说，从此列表中删除其中不包含在指定集合中的所有元素。 
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    /**
     * 从列表中的指定位置开始，返回列表中的元素（按正确顺序）的列表迭代器。
     *指定的索引表示初始调用将返回的第一个元素为next 。 初始调用previous将返回指定索引减1的元素。 
     *返回的列表迭代器是fail-fast 。 
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
    /**
     *返回列表中的列表迭代器（按适当的顺序）。 
     *返回的列表迭代器是fail-fast 。
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }
    /**
     *以正确的顺序返回该列表中的元素的迭代器。 
     *返回的迭代器是fail-fast 。 
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

Arraylist的扩容机制

首先以创建无参构造为例，创建后一开始不会马上扩容为默认的大小10，会先是一个空的Object数组，如果使用了add方法后才会扩容为10。因为这时 ensureCapacityInternal(size + 1); 也就是说size=1；

//minCapacity=1
   private void ensureCapacityInternal(int minCapacity) {
   //这时的elementData还是0
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//true
              // 获取“默认的容量”和“传入参数”两者之间的最大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//所以这里minCapacity会是10
        }
    //把minCapacity=10传入
        ensureExplicitCapacity(minCapacity);
    }

ensureExplicitCapacity方法：

//判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        //这时10-0>0,所以执行我们的扩容方法
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容，调用此方法代表已经开始扩容了
            grow(minCapacity);
    }

grow方法

private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;//0这里是
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);//这里还是0
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity; //这里就变成10了
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        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);
    }

接下来继续添加：然后会继续比较 ensureCapacityInternal(size + 1); 也就是说size=2；

//minCapacity=2
   private void ensureCapacityInternal(int minCapacity) {
   //这时的elementData被扩容成了10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//false
              // 获取“默认的容量”和“传入参数”两者之间的最大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    //把minCapacity=2传入
        ensureExplicitCapacity(minCapacity);
    }

所以后面添加直到第11个才会扩容。

扩容机制代码已经做了详细的解释。另外值得注意的是大家很容易忽略的一个运算符：移位运算符。

简介：移位运算符就是在二进制的基础上对数字进行平移。按照平移的方向和填充数字的规则分为三种:<<(左移)、>>(带符号右移)和>>>(无符号右移)。　　作用：对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源　　比如这里：int newCapacity = oldCapacity + (oldCapacity >> 1); 右移一位相当于除2，右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。

Java基础篇--集合(上)（1）

一、前言

1.1数组和集合的比较

1.2 基础数据类型的装箱与拆箱

装箱与拆箱

装箱

拆箱

自动装箱和拆箱的时机

自动装拆箱带来的问题

==比较

空指针

内存浪费

二、Java集合

2.1 Iterable（迭代接口）

2.1.1 Iterable源码

2.1.2 源码解析

2.2 Collection

2.2.1 Collection接口

2.2.2 List接口

2.2.2.1 ArrayList集合

2.2.2.1.1 对象数组

2.2.2.1.2 ArrayList集合

2.2.2.1.2 ArrayList集合的使用

2.2.2.1.2 ArrayList集合源码分析

热门文章

最新文章

相关课程

相关电子书

相关实验场景