ArrayList的源码分析

集合体系 优点

• 降低编程难度
• 提高程序性能
• 提高API间的互操作性
• 降低学习难度
• 降低设计和实现相关API的难度
• 增加程序的重用性

Collection

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。

List接口 常用实现类 Arraylist类

用数组实现

linkedList类

链表类 实现了Queue 和 List接口

Vector

和ArrayList差不多 子类有一个 stack类

Set接口 继承 Collection接口 TreeSet

基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。

HashSet

基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。

linkedHashSet

具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。

Queue 继承 Collection接口 linkList

可以用它来实现双向队列。

PriorityQueue

基于堆结构实现，可以用它来实现优先队列。

Map TreeMap

有顺序。

HashMap

键值对应

linkedHashMap

使用双向链表来维护元素的顺序，顺序为插入顺序。

源码剖析 List接口下的ArrayList

ArrayList 顺序容器，元素存放的顺序与放进去的顺序相同，允许放入null值，底层是一个数组。 该类 没有实现线程的同步，是线程不安全的。

由于底层 是一个 Object 数组 可以放进任何元素 这里使用了泛型来表示任意元素的类型

我们知道 数组 在 查找元素方面的效率 是常数级别的。

ArrayList 的构造方法

ArrayList (int initialCapacity)

ArrayList()

ArrayList(Collection c)

//源码  初始化容量
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);//容量小于零 抛出异常
        }
    }

//空的构造方法
  public ArrayList() {
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 //赋给一个空的数组。
  }
//集合作为参数的构造方法
public ArrayList(Collection c) {
        elementData = c.toArray();
    //传进来的集合转为数组
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            //传进来的集合没有值的话  初始化空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

对于两个常量数组 为什么这么规范

可以看下面这个博客

EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA两个空数组的区别_闻赤松之清尘，愿承风乎遗则的博客-CSDN博客

自动扩容的机制

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。

源码如下

//字段
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
  

每次扩容1.5倍 这种代价 是很高的 容量不够 的话 一直递增给数组扩容 会花费较长的时间

我们可以使用ensureCapacity（int）方法进行手动扩容 我们知道 要存的元素个数 我们直接手动扩容 这样会减少不少的时间

add，addAll()方法

//末尾添加
  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
//指定位置添加元素
  public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
//这里没加if  没看懂
//数组大了就是扩容 —> 涉及到 数组的复制
//然后 添加元素 -> 涉及到数组的移动 所以有着n的时间复杂度

addAll() 分析

public boolean addAll(Collection 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 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);                            

原生拷贝方法解析

public static void arraycopy(Object[] src, int srcPos, Object[] dest, int destPos, int length)

src:源数组;

srcPos:源数组要复制的起始位置;

dest:目的数组;

destPos:目的数组放置的起始位置;

length:复制的长度.

set(), get()

地城数组 通过下标改值即可

trimToSize()

功能 ：将底层数组的容量调整为当前列表保存的实际元素的大小的功能

//源码
public void trimToSize() {
        modCount++;//防止并发修改的操作。
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTdata: Arrays.copyOf(elementData, size);
        }
    }

indexOf(),lastIndexOf()方法

功能：获取索引

//底层是使用equals方法判断对象是否相等的
 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 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;
    }