来自mrcode：代码有毒
从结构来看
4个顶层接口来看至少有以下功能
1.Cloneable：
此类实现了 Cloneable 接口，以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制。
2.RandomAccess：
List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
3.Serializable：
序列化接口没有方法或字段，仅用于标识可序列化的语义
4.Iterable：
实现这个接口允许对象成为 “foreach” 语句的目标。
实现/继承
1.AbstractList：
此类提供 List 接口的骨干实现，以最大限度地减少实现“随机访问”数据存储（如数组）支持的该接口所需的工作。对于连续的访问数据（如链表），应优先使用 AbstractSequentialList，而不是此类。
2.List：
有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。
3.AbstractCollection：
此类提供 Collection 接口的骨干实现，以最大限度地减少了实现此接口所需的工作。
4.Collection：Collection
层次结构 中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接 实现：它提供更具体的子接口（如 Set 和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。
从功能阅读-简单函数开始
一般在使用中最常用的就是，数据的存、取、删、循环遍历，就从这几个点分析源码。
要使用就得先初始化对象实例。
构造函数
/**
* Constructs an empty list with an initial capacity of ten.
* 构建一个初始化容量为10的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 用指定容量创建列表
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
add - 将指定的元素添加到此列表的尾部。
//把元素添加到元素末尾
public boolean add(E e) {
//确保列表的容量足够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add - 将指定的元素插入此列表中的指定位置。
总结：
- 下标不能越界
- 每次操作都需要移动元素的个数：频繁使用该方法将会影响性能
// 将指定的元素插入次列表中的指定位置
//将指定位置元素开始的下标都往后+1（往后移动一个位置）
public void add(int index, E element) {
//检查指定下标是否越界
rangeCheckForAdd(index);
//调用核心函数1 确保足够的容量
ensureCapacityInternal(size + 1); // Increments modCount!!/
// 移动元素
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
/**
* A version of rangeCheck used by add and addAll.
* 检查指定下标是否越界，该方法供add 和 addAll使用
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
核心函数1：确保足够的列表容量
总结：
- 支持最大容量：Integer.MAX_VALUE（约21亿条数据）
- 每次扩容都在原有基础上增加一半的容量；所以适当的估算初始容量是很重要的（默认初始容量 10）
//确保列表的容量足够：1. 入口
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//1.1. 修改次数+1，是否扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument. *
* @param minCapacity the desired minimum capacity
* 扩容；至少能容纳下minCapacity所需要的容量
*/
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)
// 进行重新计算确定新的容量：结果：最大Integer.MAX_VALUE
// 所以这里的结果就是：一个list最多支持21亿多条数据，一般也不会用到这么大的，完全够用
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 把原来的数据拷贝到新容量数组中去
elementData = Arrays.copyOf(elementData, newCapacity);
}
remove - 按索引移除元素
总结：
- 移除索引不能大于最大元素数量
- 每次操作都需要对移除后的数据进行移动操作：在删除较多的场景里面使用该方法影响性能
//按索引移除该元素，并返回被移除的元素值
public E remove(int index) {
// 检查索引的有效性，索引大于size则数组越界
rangeCheck(index);
modCount++; //快速失败思想，增加修改次数
E oldValue = elementData(index);
//计算需要移动的元素个数
int numMoved = size - index - 1;
if (numMoved > 0)
//把源数组的删除索引之后的元素都往前copy覆盖
System.arraycopy(elementData, index+1, elementData, index,numMoved);
//置空最后一个元素，并把size减少1
//这里置空元素，只是为了让gc尽快的回收掉移除的元素，小技巧用得很对
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
// 检查指定下标是否在范围内
private void rangeCheck(int index) {
//这里可以看到只检查了是否大于等于siez，如果为负数的话，则没有检查，那么在插入的时候Native Method会抛出数据越界的
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
remove - 移除指定的元素
总结：
- 按value删除元素，只会删除第一次出现的元素
- 按value删除元素，在内部会进行for循环匹配元素，并且要移动受影响的元素：所以对于删除来说，list性能稍低
// 移除指定的元素，如果这个元素存在的话，并且移除的是第一次出现的元素
// 移除成功或则返回true，未搜索找元素则返回false
public boolean remove(Object o) {
//因为list支持 null 元素，所以对null进行特殊处理
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.
* 私有的删除元素方法，不进行边界检查和是否存在的检查，直接按照指定的索引进行删除
* （貌似又学到一个规则：公开的的方法必须校验边界规则什么的，私有的方法就不用了，方便公用 * 吗？）
* 该方法的代码和public remove(index) 中的代码部分主要删除逻辑一致
*/
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
}
set - 用指定的元素替代此列表中指定位置上的元素。
总结：
- 直接根据下标替换掉原有元素
//用指定的元素替代此列表中指定位置上的元素。
public E set(int index, E element) {
//在remove中也使用了该函数，检查 index>=siez
rangeCheck(index);
//记录替换之前的元素
E oldValue = elementData(index);
//直接更新
elementData[index] = element;
return oldValue;
}
//获得指定下标的 元素
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
get - 返回此列表中指定位置上的元素。
public E get(int index) {
//检查下标是否越界size
rangeCheck(index);
//直接通过下标拿到了元素
return elementData(index);
}
Iterator - 遍历
总结一
要让一个对象拥有foreach的目标，则需要有以下两个要求：
1.目标对象实现 Iterable 接口
2.实现Iterator，对数据进行常用操作访问实现接口的方法会返回一个 Iterator 类型的对象，所以得自己实现对自己数据结构的访问等操作
foreach 是调用了 Iterator 的方法实现的。
所以问题就来了：
for(i=0;i<size;i++) 这种语法是不是和迭代器无关了，从这个看来，for(;;)只是对i进行了
一个自增的操作，和具体的对象不是绑定状态，但是由于ArrayList能使用下标访问数据，所以
就能多一种遍历方式了
总结二
1.遍历获取元素 是通过下标直接获取
2.但是删除元素的话是委托了 原来的删除方式，很原来的删除原理一致，但是保证了当前元素下标的正确性，弥补了for(;;)删除导致容器size变化和元素下标位置发生变化 从而无法获取正确的元素的 问题
3.Iterator 可以使用while来遍历
// 返回一个在一组 T 类型的元素上进行迭代的迭代器。
// 这个跌迭代器是 快速失败的，也就是会检查modCount，发现不对就抛出异常
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
* 对父类的优化。- 这个抽象层次真好
*/
private class Itr implements Iterator<E> {
// 返回下一步元素的索引
int cursor; // index of next element to return
//返回最后一次操作的元素索引，-1 表示没有操作过元素，用于删除操作使用
int lastRet = -1; // index of last element returned; -1 if no such
//快速失败检查，保留一个当前迭代器所持有的数据版本；
int expectedModCount = modCount;
//是否有下一个元素
public boolean hasNext() {
// 当前游标不等于size的话，就表示还有下一个元素
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor; //在开头获取下一步的值，且以0开始，则i表示当前操作的元素下标
if (i >= size) /当前元素索引如果大于了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() {
// 如果还没有操作过元素，比如，没有调用next方法，就调用该方法就表示状态不正确
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); //每次操作都需要检查是否快速失败
try {
//调用原来的移除方法进行删除元素，当前也会使modCount次数增加
ArrayList.this.remove(lastRet);
cursor = lastRet; //因为删除了元素，删除下标后面的元素都会往前移动
lastRet = -1; //变成-1 状态，如果连续调用该方法则抛出异常（这里设计得真的好巧妙，保证了删除操作）
//更改当前迭代器所持有的数据版本，否则就会导致快速失败异常了
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
//对于数据越界操作，都定义为 当方法检测到对象的并发修改，但不允许这种修改时，抛出此异常
throw new ConcurrentModificationException();
}
}
//检查当前迭代器的版本是否与 容器列表中的数据版本是否一致，如果不一致，那么当前迭代数据就会发生下标越界等异常，所以需要抛出异常（比如在多线程中，或则在迭代中使用list.remove() 或则add等方法 都会导致抛出异常）
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
contains - 如果包含指定的元素返回true
总结：
1.查找是否包含同样是从头到尾的循环遍历匹配
2.是否匹配 使用equals方法比对，所以自己可以覆盖equals方法来查找引用型自定义对象
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// 在数组中循环遍历查找指定的元素，如果存在则返回该元素下标，是返回首次出现的元素哦
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;
}
小结总结
其实从上面已经就可以看出来了，list的一些常用总结特性：底层使用数组实现
优点：
1.随机访问比较快，因为直接通过下标获取元素
2.覆盖更新元素也比较快，也是直接通过下标覆盖
缺点
1.在remove多的场景下性能稍微低下（针对其他的集合来说）
2.在按value remove的情况下会循环遍历整个数组，性能稍低
3.随机插入操作性能较低，因为需要把插入下标后面所有的元素都移动位置
4.当前容量不够的时候会触发扩容操作，每次扩容都需要把源数据拷贝到新的扩容数组中去，不合理估算初始容量的话，性能较低
源码分析的测试用列：
因为是工具类，直接对使用的方法进行分析；
public class ArrayListStudyTest {
private ArrayList<Integer> data;
@Before
public void createTestData(){
data = new ArrayList<>(3);
data.add(0);
data.add(1);
data.add(2);
}
@Test
public void add(){
data.add(1,2);
}
@Test
public void remove(){
data.remove(1);
data.remove(Integer.valueOf(2));
}
@Test
public void set(){
data.set(-1,3);
}
@Test
public void get(){
Integer integer = data.get(0);
}
@Test
public void foreach(){
Iterator<Integer> iterator = data.iterator();
while (iterator.hasNext()){
Integer next = iterator.next();
}
for (Integer num : data) {
System.out.println(num);
}
}
}
编写自己的Arraylist
简单编写了下 基本功能的arraylist，编写过程中发现，要费不少时间，特别是你还要考虑到各种暴露方法调用会出现的bug，现在才感觉一个工具类真的可能要经过多次迭代和认真考虑各个使用环境下，才能编写出好的工具类
/**
* @author zhuqiang
* @version V1.0
* @date 2016/7/22 0022 9:44
*/
public class MyArrayList<E> implements Iterable<E>{
private Object[] elementData; //底层实现用数组
private final static Object[] EMPTY_ELEMENTDATA = {};
private final static int DEFAULT_CAPACITY = 10; //默认初始容量
private int size; //容器大小
private int modCount; //快速失败 版本
public MyArrayList() {
elementData = EMPTY_ELEMENTDATA;
}
public MyArrayList(int initialCapacity) {
if(initialCapacity < 0){
throw new IllegalArgumentException("初始化容量不能小于0");
}
this.elementData = new Object[initialCapacity];
}
/**
* 把元素添加到列表末尾
* @param e
* @return
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
// 确保底层容量能存储数据
private void ensureCapacityInternal(int minCapacity) {
if(EMPTY_ELEMENTDATA == elementData){
this.elementData = new Object[DEFAULT_CAPACITY];
}
if(minCapacity - this.elementData.length > 0){
ensureCapacity(minCapacity);
}
}
// 扩容操作
private void ensureCapacity(int minCapacity) {
int oldCapacity = this.elementData.length;
int newCapacity = oldCapacity + (oldCapacity>>1); //新的容量计算
elementData = Arrays.copyOf(elementData,newCapacity); //把原数据拷贝到新的容量数组中
}
/**
* 移除指定下标的元素
* @param index
* @return
*/
public E remove(int index){
E oldValue = elementData(index);
//计算需要移动的元素个数
int numMoved = size - index -1; // 减掉被移除的自己
System.arraycopy(elementData,index+1,elementData,index,numMoved);
elementData[--size] = null;
return oldValue;
}
/**
* 替换指定下标的元素
* @param index
* @param element 返回被替换掉的元素的值
* @return
*/
public E set(int index, E element){
E oldValue = elementData(index);
this.elementData[index] = element;
return oldValue;
}
public E get(int index){
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
public int size(){
return size;
}
@Override
public Iterator iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
@Override
public boolean hasNext() {
return cursor != size;
}
@Override
public E next() {
int i = cursor;
E e = MyArrayList.this.elementData(i);
cursor++;
return e;
}
@Override
public void remove() {
}
}
public static void main(String[] args) {
MyArrayList<Integer> data = new MyArrayList<>();
data.add(0);
data.add(1);
data.add(2);
data.add(3);
for (Integer i : data) {
System.out.println(i);
}
System.out.println("==========");
for (int i = 0; i < data.size(); i++) {
System.out.println(data.get(i));
}
System.out.println("==========");
data.remove(1);
for (int i = 0; i < data.size(); i++) {
System.out.println(data.get(i));
}
}
}
网友评论