ArrayList底层实现原理

1, 属性&＃xff1a;
private static final int DEFAULT_CAPACITY &＃61; 10;private static final Object [] EMPTY_ELEMENTDATA &＃61; {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA &＃61; {};transient Object [] elementData;private int size; // 动态数组的实际大小2,构造方法&＃xff1a;public ArrayList(){this.elementData &＃61; DEFAULTCAPACITY_EMPTY_ELEMENTDATA&＃xff1b;}调用无参的构造方法&＃xff0c;则会将elementData赋上为空的一个数组.public ArrayList(Collectionextends E> c){elementData &＃61; c.toArray();if(size &＃61; elementData.length !&＃61; 0){if(elementData.getClass()!&＃61;Object[].class)elementData &＃61; Arrays.copyOf(elementData,size,Object[].class);}else{elementData &＃61; EMPTY_ELEMENTDATA;}
}调用有参的构造方法&＃xff0c;参数是一个带范型的集合。生成一个可以不为空的集合。
如果参数使用toArray(),返回类型不是Object[],则使用copyOf() 复制下并赋值给elementData&＃xff0c;public ArrayList(int initialCapacity){if(initialCapacity > 0){this.elementData &＃61; new Object[initialCapacity];}else if(initialCapacicty &＃61;&＃61; 0){this.elementData &＃61; EMPTY_ELEMENTDATA;}else{throw new IlleagalArgumentException("illagal initialCapacity"&＃43;initialCapcity)&＃xff1b;}
}调用有参的构造函数&＃xff0c;初始化储存元素的容量。定义之后&＃xff0c;内存会为开辟初始化容量大小的空间。
随着ArrayList 里面元素的增加直到initialCapacity&＃xff0c;不需要数组向新数组的拷贝。Tips&＃xff1a;
Arraylsit list &＃61; new ArrayList(10);
默认的Object[] elementData 的长度为10&＃xff1b;
list.size();的长度还是为0因为size 代表的逻辑长度&＃xff0c;内存中实际存在的元素的长度。3,add&＃xff1b;public boolean add(E e){ensureCapacityInternal(size &＃43; 1);elementData[size&＃43;&＃43;] &＃61; e&＃xff1b;return true;
}private void ensureCapacityInternal(int minCapacity){if(elementData &＃61;&＃61; DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity &＃61; Math.max(DEFAILT_CAPACITY,minCapacity);}ensureExplicitCapacity(minCapacity);
}向ArrayList 里面增添元素的时候&＃xff0c;当ArrayList 的为空的时候&＃xff0c;add元素时&＃xff0c;如果没有设定Arraylist的Object elementData的长度&＃xff0c;
会设定默认的Object[] elementData 的长度为10&＃xff0c;所以在长度为10 之前能够避免在每添加一个新的元素时候&＃xff0c;就要复制原来的元素的数组到新的数组的里面去。private void ensureExplicitCapacity(int minCapacity){modCount &＃43;&＃43;;//extends from AbstactArrayListif(minCapacity - elementData.length > 0)grow(minCapacity);//长度不够&＃xff0c;每次扩充1.5倍<粗略>

}private void grow(int minCapacity){int oldCapacity &＃61; elementData.length;int newCapacity &＃61; oldCapacity &＃43; (oldCapacity >> 1);if(newCapacity - minCapacity <0)newCapacity &＃61; minCapacity;if(newCapacity - MAX_ARRAY_SIZE > 0)newCapacity &＃61; hugeCapacity(minCapacity);//MAX_ARRAY_SIZE 2147483639
elementData &＃61; Arrays.copyOf(elementData,newCapacity);//扩充了Obect elementData[]的长度
}private void hugeCapacity(int minCapacity){if(minCapacity <0)//因为minCapacity int 型&＃xff0c;超过int 的最大值就会<0,就代表内存溢出throw new OutOfMemoryError();return(minCapacity > Max_ARRAY_SIZE)?Integer.MAX_VALUE:MAX_ARRAY_SIZE;
//最大上限就是Integer的最大值-8&＃xff1b;
}4,add
public void add(int index,E element){rangeCheckForAdd(index);ensureCapacityInternal(size &＃43; 1); //开辟空间System.arraycopy(elemntData,index,elementData,index &＃43; 1,size - index);size &＃43;&＃43;;
}private void rangeCheckForAdd(int index){if(index > size || index <0 ){throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
}add(int index,E elemenmt)中使用System.arraycopy的思想&＃xff0c;是因为elementData的容器长度大于逻辑长度&＃xff0c;即它本身的留有一个空位null,可用作填充数据。例&＃xff1a;
Object [] elementData &＃61; {"one","two","three","four","five","null","null","null"};
要想在index为3的位置插入"six",
System.arraycopy(elementData,3,elementData,4,2);
elementData:源数组
3:源数组的起始位置
elementData:目标数组
4:目标数组的开始位置
2&＃xff1a;size - index,size代表的是elementData中不为null的元素的长度所以&＃xff0c;就可以将index &＃43; 1 后半段的不为null 的元素复制到源数组的本身&＃xff0c;同时将index 这个位置空出来,然后插入就可以实现add插入指定位置的功能。
elementData[index] &＃61; "six";
size &＃43;&＃43;;Arrays.copyOf(),System.copyof()
system.arraycopy(Object src,int srcPos,Object dest,destPos,length);native 方法&＃xff0c;源码是由C&＃43;&＃43; 实现
Arrays.copyOf()&＃xff0c;内部实现的也是System.arraycopy(),只是ArrayCopy()会创建一个新的数组&＃xff0c;将源数组向新数组复制。5,removepublic E remove(int index){rangeCheck(index);//先check下index有没有有越界modCount&＃43;&＃43;;//非安全线程
E oldValue &＃61; elementData[index];int numMoved &＃61; size - index - 1;if(numMoved > 0)System.arraycopy(elementData,index &＃43; 1,elementData,numMoved);//如果numMoved &＃61;&＃61; 0 的情况也就是源数组只有一个元素的情况&＃xff0c;就无需复制数组&＃xff0c;只需执行elemnetData[--size]即elementData[0] &＃61;nullelementData[--size] &＃61; null;//将elementData 的空间变成nullreturn oldValue;
}private void rangeCheck(int index){if(index >&＃61; size){throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
}从一定程度上来说&＃xff0c;remove(int index)的原理是和add(int index, E element)的逻辑是差不多的。6,remove
public boolean remove(Object o){if(o &＃61;&＃61; null){for(int index &＃61; 0;index ){if(elementData[index]&＃61;&＃61;null){fastRemove(index);return true;}}}else{for(int index &＃61; 0;index ){if(o.equals(elementData[index])){fastRemove(index);return true;}}}return false;
}private void fastRemove(index){modCount&＃43;&＃43;;//非安全线程int numMoved &＃61; size - index - 1;if(numMoved > 0)System.arraycopy(elementData,index &＃43; 1,elementData,numMoved);elementData[--size] &＃61; null;//将elementData 的空间变成null

}remove(Object o) 删除集合中匹配的元素<最先匹配的元素>&＃xff0c;其思路和remove(index)是一样的
remove(index)是直接告知index,remove(Obejct o)是先找到匹配的index,然后再进行和remove(index) 大致的操作。其中&＃xff0c;remove(Obejct o)需考虑元素o 是否为null&＃xff0c;关于两元素是否相等的比较方法&＃61;&＃61; 和 equals
&＃61;&＃61; 在值类型中&＃xff0c;就是比较值是否相等&＃xff0c;但是在引用类型中&＃xff0c;实际比较的是在内存中的地址是否相等
equals,是Obejct 中的方法&＃xff0c;如下&＃xff1a;public boolean equals(Object o){return (this &＃61;&＃61; o);
}Object 是所有类的父类&＃xff0c;Obejct 中的equals 方法就是&＃61;&＃61;&＃xff0c;是比较内存中的地址是否相等&＃xff0c;
许多类会重写Obejct 中的equals方法&＃xff0c;例如String 类&＃xff0c;重写之后就是对字符串值进行比较在remove(Obejct o) 中的equals 方法实际比较的就是内存中地址的相等。但是如果对于对Object中equals 方法重写的类&＃xff0c;
则实际比较的就是值是否相等。