集合arraylist源码（java arraylist集合）
本文目录一览：
- 1、一常用 API ——第三节、ArrrayList类，是集合
- 2、arraylistgetalldata出错
- 3、如何自己实现一个简单的ArrayList
- 4、arraylist源代码问题
- 5、ArrayList源码中的toArray方法中的这块代码是什么意思？
- 6、ArrayList详解，自动扩容原理
一常用 API ——第三节、ArrrayList类，是集合
1、ArrayList的底层数据结构就是一个数组，查找快，增删慢
2、ArrayList的线程安全性
对ArrayList进行添加元素的操作的时候是分两个步骤进行的，即第一步先在object[size]的位置上存放需要添加的元素；第二步将size的值增加1。由于这个过程在多线程的环境下是不能保证具有原子性的，因此ArrayList在多线程的环境下是线程不安全的。
具体举例说明：在单线程运行的情况下，如果Size = 0，添加一个元素后，此元素在位置 0，而且Size=1；而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增 加 Size 的值。 那好，现在我们来看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而Size却等于 2。这就是“线程不安全”了。
如果非要在多线程的环境下使用ArrayList，就需要保证它的线程安全性，通常有两种解决办法：第一，使用synchronized关键字；第二，可以用Collections类中的静态方法synchronizedList();对ArrayList进行调用即可。
public boolean add(E,e)：参数的类型和泛型一致， 对于add方法来说，添加一定是成功的，返回值可用可不用。但是对于其他集合来说，add添加动作不一定成功，
在add()方法中主要完成了3件事：
首先确保能够将希望添加到集合中的元素能够添加到集合中，即确保ArrayList的容量（判断是否需要扩容）；
然后将元素添加到elementData数组的指定位置；
最后将集合中实际的元素个数加1。
public E get (int index)从集合中获取元素，参数是索引编号，返回值是对应位置的元素，索引从0开始，
set(int index, E element)方法的作用是指定下标索引处的元素的值。在ArrayList的源码实现中，方法内首先判断传递的元素数组下标参数是否合法，然后将原来的值取出，设置为新的值，将旧值作为返回值返回。
indexOf(Object o)方法的作用是从头开始查找与指定元素相等的元素，如果找到，则返回找到的元素在元素数组中的下标，如果没有找到返回-1。与该方法类似的是lastIndexOf(Object o)方法，该方法的作用是从尾部开始查找与指定元素相等的元素。
public E remove(int index)方法的作用是删除指定下标的元素。在该方法的源码中，将指定下标后面一位到数组末尾的全部元素向前移动一个单位，并且把数组最后一个元素设置为null，这样方便之后将整个数组不再使用时，会被GC，可以作为小技巧。而需要移动的元素个数为：size-index-1。
public int size():获取集合的大小， 返回值是集合中包含的元素个数
定义以指定格式打印集合的方法，ArrayList类型作为参数，使用{}扩起集合，使用@分隔每隔元素，格式参照元素@元素@元素
arraylistgetalldata出错
这个集合是线程不安全的，在多线程当中，建议使用vector。
ArrayList是基于数组的数据结构。
与LinkedList相比，更加适合在查询多、增删操作少的场景下使用，并且它是非线程安全的，如果并发量比较大的场景，需要改用线程安全的版本或者用JUC包中的CopyOnWriteArrayList。
ArrayList是以数组的方式存放数据的。在看ArrayList源码的时候，会发现有一个变量是modCount，在增删改的方法中均涉及到对它的++操作。
如何自己实现一个简单的ArrayList
ArrayList是Java集合框架中一个经典的实现类。他比起常用的数组而言，明显的优点在于，可以随意的添加和删除元素而不需考虑数组的大小。
实现一个简单的ArrayList，实现的过程：
实现的ArrayList主要的功能如下：
默认构造器和一个参数的有参构造器
add方法
get方法
indexOf方法
contains方法
size方法
isEmpty方法
remove方法
这个简单的ArrayList类 取名为SimpleArrayList，全部的代码查看SimpleArrayList代码
构造器
源码ArrayList一共有三个构造器，一个无参构造器，一个参数为int型有参构造器，一个参数为Collection型的有参构造器。参数为Collection型的构造器用来实现将其他继承Collection类的容器类转换成ArrayList。SimpleArrayList类因为还没有手动实现其他的容器类，所以实现的构造方法只有2个。代码如下：
public SimpleArrayList(){ this(DEFAULT_CAPACITY);
} public SimpleArrayList(int size){ if (size 0){ throw new IllegalArgumentException("默认的大小" + size);
}else{
elementData = new Object[size];
}
}
无参构造器中的 DEFAULT_CAPACITY是定义的私有变量，默认值是10，用来创建一个大小为10的数组。有参构造器中，int参数是用来生成一个指定大小的Object数组。将创建好的数组传给elementData。elementData是真正的用来存储元素的数组。
add方法
add 方法用来往容器中添加元素，add方法有两个重载方法，一个是add(E e),另一个是add(int index, E e)。add本身很简单，但是要处理动态数组，即数组大小不满足的时候，扩大数组的内存。具体的代码如下：
public void add(E e){
isCapacityEnough(size + 1);
elementData[size++] = e;
}
方法isCapacityEnough就是来判断是否需要扩容，传入的参数就是最小的扩容空间。因为add一个元素，所以最小的扩容空间，即新的长度是所有元素+ 1。这里的size就是真正的元素个数。
private void isCapacityEnough(int size){ if (size DEFAULT_CAPACITY){
explicitCapacity(size);
} if (size 0){ throw new OutOfMemoryError();
}
}
判断扩容的方法也很简单，判断需要扩容的空间是不是比默认的空间大。如果需要的空间比默认的空间大，就调用explicitCapacity进行扩容。这里有个size小于0的判断，出现size小于0主要是因为当size超过Integer.MAX_VALUE就会变成负数。
private final static int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8; private void explicitCapacity(int capacity){ int newLength = elementData.length * 2; if (newLength - capacity 0){
newLength = capacity;
} if (newLength (MAX_ARRAY_LENGTH)){
newLength = (capacity MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
}
elementData = Arrays.copyOf(elementData, newLength);
}
上面的代码是扩容的代码，首先，定义一个数组最大的容量的常量为最大值，这个值按照官方的源码中的解释是要有些VM保留了数组的头部信息在数组中，因此实际存放数据的大小就是整数的最大值 - 8
然后设定一个要扩容的数组的大小，虽然上面说了有一个扩容空间的值 size + 1 ，这个是实际我们最小需要扩容的大小。但为了继续增加元素，而不频繁的扩容，因此一次性的申请多一些的扩容空间。这里newLength 打算申请为 数组长度的2倍，然后去判断这个长度是否满足需要的扩容空间的值。 即有了后续的两段代码
if (newLength - capacity 0){ newLength = capacity;
} if (newLength (MAX_ARRAY_LENGTH)){ newLength = (capacity MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
}
如果2倍的长度仍然不满足，则申请到需要的扩容长度。在我们只增加一个元素的情况下，这个判断是永远不会生效的，但是如果有addAll方法，则增加的元素很多，就要导致一次申请2倍的长度是不够的。第二个判断是判断newLength的长度如果超过上面定义的数组最大长度则判断要需要的扩容空间是否大于数组最大长度，如果大于则newLength为 MAX_VALUE ，否则为 MAX_ARRAY_LENGTH。
最后，真正实现数组扩容到设定长度的方法就没意思了，调用Arrays.copyOf(elementData, newLength)得到一个扩容后的数组。
add的另一个重载方法也很简单。
public void add(int index, E e) {
//判断是不是越界
checkRangeForAdd(index);
//判断需不需要扩容
isCapacityEnough(size + 1);
//将index的元素及以后的元素向后移一位
System.arraycopy(elementData,index,elementData,index + 1,size - index);
//将index下标的值设为e
elementData[index] = e; size++;
}
private void checkRangeForAdd(int index){ //这里index = size是被允许的，即支持头，中间，尾部插入
if (index 0 || index size){ throw new IndexOutOfBoundsException("指定的index超过界限");
}
}
至此，一个简单的add方法就实现完了。
get方法
get方法用来得到容器中指定下标的元素。方法实现比较简单，直接返回数组中指定下标的元素即可。
private void checkRange(int index) { if (index = size || index 0){
throw new IndexOutOfBoundsException("指定的index超过界限");
}
} public E get(int index){
checkRange(index); return (E)elementData[index];
}
indexOf方法
indexOf方法用来得到指定元素的下标。实现起来比较简单，需要判断传入的元素，代码如下：
public int indexOf(Object o){ if (o != null) { for (int i = 0 ; i size ; i++){ if (elementData[i].equals(o)){ return i;
}
}
}else { for (int i = 0 ; i size ; i++){ if (elementData[i] == null) { return i;
}
}
} return -1;
}
判断传入的元素是否为null，如果为null，则依次与null。如果不为空，则用equals依次比较。匹配成功就返回下标，匹配失败就返回-1。
contains方法
contains用来判断该容器中是否包含指定的元素。在有了indexOf方法的基础上，contains的实现就很简单了。
public boolean contains(Object o){ return indexOf(o) = 0;
}
size方法
size方法用来得到容器类的元素个数，实现很简单，直接返回size的大小即可。
public int size(){ return size;
}
isEmpty方法
isEmpty方法用来判断容器是否为空，判断size方法的返回值是否为0即可。
public boolean isEmpty(){ return size() == 0;
}
remove方法
remove方法是用来对容器类的元素进行删除，与add一样，remove方法也有两个重载方法，分别是
remove(Object o)和remove(int index)
public E remove(int index) {
E value = get(index); int moveSize = size - index - 1; if (moveSize 0){
System.arraycopy(elementData,index + 1, elementData,index,size - index - 1);
}
elementData[--size] = null; return value;
}
public boolean remove(Object o){ if (contains(o)){
remove(indexOf(o)); return true;
}else { return false;
}
}
第一个remove方法是核心方法，首先得到要删除的下标元素的值，然后判断index后面的要前移的元素的个数，如果个数大于零，则调用库方法，将index后面的元素向前移一位。最后elementData[--size] = null;缩减size大小，并将原最后一位置空。
第二个remove方法不需要向第一个方法一样，需要告诉使用者要删除的下标对应的元素，只需要判断是否删除成功即可。如果要删除的元素在列表中，则删除成功，如果不在则失败。因此调用contains方法就可以判断是否要删除的元素在列表中。在则调用remove(int index),不在则返回失败。
arraylist源代码问题
protected AbstractList()唯一的构造方法。（由子类构造方法调用，通常是隐式的。）
抽象的类不是没有构造方法，只是不能实例化
java中构造器的调用是级联调用的．
一真会调用到Object
原因：
根据替代性原理，子类对象必须能够替代父类对象．因此在构造子类对象时，要首先构造一个父类对象，然后在父类对象的基础上进一步构造子类对象．也就是说，java中的子类对象中都隐含着一个父类对象，子类对象是在父类对象的基础上进一步雕琢成的．
书上原话．我也不是很明白．反正知道怎么调用就行了．
ArrayList源码中的toArray方法中的这块代码是什么意思？
pIf the list fits in the specified array with room to spare (i.e., the array has more elements than the list), the element in the array immediately following the end of the collection is set to ttnull/tt. (This is useful in determining the length of the list ionly/i if the caller knows that the list does not contain any null elements.)
这个是官方的注释，意思是如果你的这个参数a的长度比你的list的长度要长的话，就会在把arrayList中的元素复制完后加一个null，用于标记数组结尾。list的长度是size，所以a[size]要设置为null，做为一个结尾的符号
ArrayList详解，自动扩容原理
ArrayListE：说明ArrayList支持泛型。
extends AbstractListE ：继承了AbstractList。AbstractList提供List接口的骨干实现，以最大限度地减少“随机访问”数据存储（如ArrayList）实现Llist所需的工作。
implements ListE：实现了List。实现了所有可选列表操作。
implements RandomAccess：表明ArrayList支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
implements java.io.Serializable：表明该类具有序列化功能。有序列化功能
下面来看一些比较重要的参数：
ArrayList的实际大小（数组包含真正的元素个数）
执行完构造方法时还是一个空数组，等到add方法执行的时候则会初始化容量为10；
自己穿入想要的容量参数，对容量进行判断如果容量小于零，则会抛出异常，否则会创建一个容量为initialCapacity的空ArrayList
构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
先来看其中的add（）方法：
add方法首先会调用ensureCapacityInternal（size+1）方法，
ensureCapacityInternal（size+1）方法是用来进行容量检查，决定扩容的想要的最小容量，举个例子，第一次扩容的时候，size默认为0则minCapacity（即想要的最小容量）为1，执行完Math.max语句minCapacity就变为10，这个时候也就是进行空构造第一次add的情况，当ensureCapacityInternal（size+1）传入的参数小于默认参数的时候，就把默认参数当做想要的最小容量，如果大于默认参数就把你想要的参数当做想要的最小容量
这个方法是用来判断是否扩容，如果你想要的最小容量大于数组长度则会调用grow方法进行扩容
通过grow方法可以看到新容量为当前数组容量的1.5倍，然后进行判断，如果理论扩容后新的容量小于小于你想要的最小容量（但我觉得这种情况不太可能会出现，因为为了节省空间，假如当前容量为10，只会传入11来和扩容后的进行比较因此我自己认为不会出现if为真的情况）真正的实现扩容其实是Arrays.copy方法，就是复制数组实现扩容，
但是如果出现了if为真的情况，从这个方法中可以看到数组的理论最大值为Integer的最大值减去8，但是如果你想要的最小容量已经大于数组的理论最大值，则会进行大容量分配为Integer的最大值至此扩容结束，
下面粗略的谈一下快速失败机制（因为对线程还没有一个好的认识）
fail-fast是怎么产生的。步骤如下：
新建了一个ArrayList，名称为arrayList。
向arrayList中添加内容
新建一个“线程a”，并在“线程a”中通过Iterator反复的读取arrayList的值。
新建一个“线程b”，在“线程b”中删除arrayList中的一个“节点A”。
这时，就会产生有趣的事件了。
在某一时刻，“线程a”创建了arrayList的Iterator。此时“节点A”仍然存在于arrayList中，创建arrayList时，expectedModCount = modCount(假设它们此时的值为N)。
在“线程a”在遍历arrayList过程中的某一时刻，“线程b”执行了，并且“线程b”删除了arrayList中的“节点A”。“线程b”执行remove()进行删除操作时，在remove()中执行了“modCount++”，此时modCount变成了N+1！
“线程a”接着遍历，当它执行到next()函数时，调用checkForComodification()比较“expectedModCount”和“modCount”的大小；而“expectedModCount=N”，“modCount=N+1”,这样，便抛出ConcurrentModificationException异常，产生fail-fast事件。
至此，我们就完全了解了fail-fast是如何产生的！
即，当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
方法1
在单线程的遍历过程中，如果要进行remove操作，可以调用迭代器的remove方法而不是集合类的remove方法。看看ArrayList中迭代器的remove方法的源码：
可以看到，该remove方法并不会修改modCount的值，并且不会对后面的遍历造成影响，因为该方法remove不能指定元素，只能remove当前遍历过的那个元素，所以调用该方法并不会发生fail-fast现象。该方法有局限性。
例子：
方法2
使用java并发包(java.util.concurrent)中的类来代替ArrayList 和hashMap。
比如使用 CopyOnWriterArrayList代替ArrayList，CopyOnWriterArrayList在是使用上跟ArrayList几乎一样，CopyOnWriter是写时复制的容器(COW)，在读写时是线程安全的。该容器在对add和remove等操作时，并不是在原数组上进行修改，而是将原数组拷贝一份，在新数组上进行修改，待完成后，才将指向旧数组的引用指向新数组，所以对于CopyOnWriterArrayList在迭代过程并不会发生fail-fast现象。但 CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。
对于HashMap，可以使用ConcurrentHashMap，ConcurrentHashMap采用了锁机制，是线程安全的。在迭代方面，ConcurrentHashMap使用了一种不同的迭代方式。在这种迭代方式中，当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException，取而代之的是在改变时new新的数据从而不影响原有的数据 ，iterator完成后再将头指针替换为新的数据 ，这样iterator线程可以使用原来老的数据，而写线程也可以并发的完成改变。即迭代不会发生fail-fast，但不保证获取的是最新的数据。
