深圳福田区网站建设,wordpress文章数量,做服装必须看的十大网站,东莞网站开发公司ArrayList集合源码分析 文章目录 ArrayList集合源码分析一、字段分析二、构造方法分析三、方法分析四、总结 内容如有错误或者其他需要注意的知识点#xff0c;欢迎指正或者探讨补充#xff0c;共同进步。
一、字段分析
//默认初始化容量。这里和Vector一样#xff0c;只是…ArrayList集合源码分析 文章目录 ArrayList集合源码分析一、字段分析二、构造方法分析三、方法分析四、总结 内容如有错误或者其他需要注意的知识点欢迎指正或者探讨补充共同进步。
一、字段分析
//默认初始化容量。这里和Vector一样只是Vector,没有用一个变量而是调用无参构造函数时直接塞了个10。
private static final int DEFAULT_CAPACITY 10;
//这里给出了两个空数组。有两个疑问1.为什么给空数组2.为什么还给了两个
//1。在我们创建空的ArrayList集合时为了避免创建多个空的数组而换成统一用这里的口空数组代替达到了节约内存和提高效率。
//2。为了区分我们在构造集合时是用的有参构造函数还是无参函数。不同的构造也会带来扩容机制的不同。
// - 无参构造函数会使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组在第一次添加元素是扩容后的容量是10。
// - 有参构造函数如果传入的是0则是用EMPTY_ELEMENTDATA 扩容是1.5的扩容。0-1-2-3-4-6-9-13如果数据很少
// 少到比10还小能够降低内存消耗的。
//所以又有了疑问那为什么不用一个就可以了呢第一次扩容都用容量10。
// - 源码上面的注释是Shared empty array instance used for default sized empty instances.
// We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.
// 这是用于默认大小的空实例的共享空数组实例。我们将其与EMPTY_ELEMENTDATA区分开来以便在添加第一个元素时知道要扩充多少空间。
// 同时如果有那种添加很少元素的需求元素数量小于10这样做是可以减少内存消耗的达到更适配相应需求的目的。
private static final Object[] EMPTY_ELEMENTDATA {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};//用来存储数据的数组
transient Object[] elementData;//实际存储了数据的个数
private int size;二、构造方法分析
从构造方法可以看出我们在创建 ArrayList 时并没有更新容量就是用的默认容量10。
public ArrayList(int initialCapacity) {if (initialCapacity 0) {this.elementData new Object[initialCapacity];} else if (initialCapacity 0) {//如果初始容量为0则空数组代替size 0this.elementData EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException(Illegal Capacity: initialCapacity);}}public ArrayList() {//如果没有指定容量则用默认的空数组代替this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public ArrayList(Collection? extends E c) {//toArray()通常会将泛型擦除掉比如应该是ListInteger 会变成 Objects[];//为何这样做呢即便你不擦除掉在代码编译时也会将泛型擦除掉所以为了提高效率加快编译速度。elementData c.toArray();if ((size elementData.length) ! 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)//这里为什么要加这样的判断呢因为通常来说c.toArray();已经返回了Object[],但如果这个是个人实现的//比如里面调用了c.toArray(Integer[]);则会返回Integer[],所以这里额外判断下//为了确保elementData 为Object数组如果使用系统提供的toArray()方法会返回if (elementData.getClass() ! Object[].class)elementData Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData EMPTY_ELEMENTDATA;}}三、方法分析
添加元素 方法是非线程安全的方法。并且在添加元素的时候会校验是否需要扩容。
//向已有元素的末尾添加元素
public boolean add(E e) {//判断是否需要扩容所需容量最少为已有元素数量 1//但里面其实会判断存储数据的数据是否为空空则需最小容量为 DEFAULT_CAPACITY //否则取Math.max已有元素数量 1DEFAULT_CAPACITY 可向下看ensureCapacityInternal(size 1); // Increments modCount!!//已有元素的末尾添加上新元素elementData[size] e;//添加成功return true;}private void ensureCapacityInternal(int minCapacity) {//判断扩容之前判断所需的最小容量而calculateCapacity(elementData, minCapacity) 就是判断//所需的容量然后拿这个所需的最少容量去判断是否需要扩容。ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {//正如上面所说的如果数组为空则所需取其中较大值这不难理解//这里也是第一次扩容采用什么决策作出了判断如果是调用无参构造函数第一次扩容是10。//如果是有参且参数0则1.5倍扩容具体原因上面参数介绍时详细说了。if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}
//这时候我们拿到了我们所需要的最小容量来判断是否需要扩容了
private void ensureExplicitCapacity(int minCapacity) {//从Vector源码中我们之前到这个是继承自Abastrack用来记录版本号防止迭代过程中集合被修改了因为迭代器创建时//会保存创建那一时刻集合的版本号迭代的过程的会比较自己保存的版本号和集合的版本号从而判断跌倒过程中是否被修改。//这里的作用是一样的。modCount;// overflow-conscious code//如果我们所需要的最小容量比elementData数组长度还大那必须要扩容了不然要下标越界了。//如果是我们第一次添加元素从构造函数可以elementData是个空数组这里也会扩容。 10 - 0 0// 从这里可以看出在添加元素时如果元素数量大于数组长度 才会触发扩容就是数组已经被塞满了不是说达到数组//容量的百分之多少。if (minCapacity - elementData.length 0)grow(minCapacity);}//到这里就是确定要扩容了并且我们拿到了所需的最小容量用来判断该如何扩容
private void grow(int minCapacity) {// overflow-conscious code//记录当前数组长度int oldCapacity elementData.length;//记录扩容后的数组长度先按1.5倍来扩容//oldCapacity 1 相当于 oldCapacity / 2//那自己的一般 自己不就是自己原来的1.5倍。//至于最后是否会用这个值了还需后面判断。int newCapacity oldCapacity (oldCapacity 1);//如果扩容后的容量还是不够则先用所需的最小容量最为新容量的值。//你可能会疑问我们添加元素都是一个一个添加的按理说不可能扩容后容量还达不到需要的呀。//然后确实可能达不到如果使用的有参构造函数且参数为0那么第一次添加元素这里传入的值就是1//但是初始容量为01.5扩容后还是0显然不够的这是后就会扩容成容量为1的数组。其实第二次添加元素//扩容还是会不够注意我说的是开始调用有参构造函数且参数0因为无参构造第一次扩容为10这里不会触发。//还有一个可能是newCapacity 溢出了变成负数。则 新容量就是 minCapacity 了即数组扩容到length 1if (newCapacity - minCapacity 0)newCapacity minCapacity;//如果新容量值要溢出了注意是快要溢出MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;if (newCapacity - MAX_ARRAY_SIZE 0)//这时候我们继续确定新容量到底该多少newCapacity hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win://到这里新容量就去确定好了去做扩容啦。//这个方法会创建一个新的数组将旧的数组按索引依次赋值到新数组上未填充到的为数据类型的默认值//如 int 为0Object 为 null.//同时这是消耗新能的操作涉及到新数组的创建和所有元素的赋值。elementData Arrays.copyOf(elementData, newCapacity);}
//和 Vecotor.class 源码一样的如果快要溢出了则直接给所能给的容量的极限。
private static int hugeCapacity(int minCapacity) {if (minCapacity 0) // overflowthrow new OutOfMemoryError();return (minCapacity MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}//向指定索引位置添加元素
public void add(int index, E element) {rangeCheckForAdd(index);//判断是否需要扩容上面分析过了ensureCapacityInternal(size 1); // Increments modCount!!//上面已经进行过扩容动作了这段代码看起来好像没必要。//上面看见的Arrays.copyOf 其实底层最终调用就是这个方法达到扩容的目的。//难道这也是扩容此不是多此一举//首先依次介绍下这个方法参数含义//src源数组要将其内容复制到目标数组中。//srcPos源数组中开始复制的位置。//dest目标数组源数组的内容将复制到该数组中。//destPos目标数组中开始复制的位置。//length要复制的元素个数。//知道了含义就很好理解了是把将要插入的位置把该位置以及之后的所有元素往后移动一格。。。//从这里也可看出ArrayList 向指定下标插入元素效率低下时间复杂度O(n),并且并不是覆盖掉//该位置原先的元素而是统统靠后移。System.arraycopy(elementData, index, elementData, index 1,size - index);//好了这个位置被腾出位置了可以插了。elementData[index] element;size;}获取元素方法这个方法没啥好说的。 //根据索引获取元素
public E get(int index) {//检查索引是否越界rangeCheck(index);//返回该位置值return elementData(index);}
//检查索引是否越界
private void rangeCheck(int index) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
//返回index索引位置的值
E elementData(int index) {return (E) elementData[index];}扩容方法介绍添加元素方法时说过了。 移除元素方法可以根据下标位置移除元素也可根据元素值移除元素。和Vector源码很相似
//根据索引位置删除元素(可以发现这里和Vector 的源码一模一样)
public E remove(int index) {//检查索引是否越界rangeCheck(index);//版本号1modCount;//得到该索引位置的值E oldValue elementData(index);//需要移动的元素数量就是你讲index位置的元素删了那这个元素后院的所有的元素都要前移这个值就是需要//移动的元素数量即index后面元素的数量int numMoved size - index - 1;//判断index后面是否有值if (numMoved 0)//将要移动的元素前移其实是吧那个要删除的元素覆盖了从而达到了删除元素的目的。System.arraycopy(elementData, index1, elementData, index,numMoved);//为什么要删除末尾元素呢因为如果index 是最后以为元素那么就不会触发元素前移所以这里//多一步将末尾元素设置为null就是为了处理这一特殊情况。所以如果index 后面有值这一步是//多余的末尾已经是null了。 elementData[--size] null; // clear to let GC do its work//返回被删除的元素元素值return oldValue;}//根据元素值删除元素
public boolean remove(Object o) {//从这里也可看出,ArrayList是允许删除null元素值的同时有相同值元素是删除的是最靠前的那个。//我们在分析Vector删除源码时在获取o的下标位置时会调用indexOf方法和这里的判断是一样的。//同时有个疑问这个难道不可以统一写成elementData[index].equals(o)不就行了吗就可以处理o是null或不是null的情况//且不会报错,且能达到相同效果那这个判断不是冗余了嘛。你在说什么胡话刚刚才说的ArrayList是允许添加null的如果//遍历获取到的元素如果是null那不就是报错了吗所以这里这样写才可以避免传入的o是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 void fastRemove(int index) {modCount;int numMoved size - index - 1;if (numMoved 0)System.arraycopy(elementData, index1, elementData, index,numMoved);elementData[--size] null; // clear to let GC do its work}迭代器设计和Vector的一样提供了两种的迭代器。Itr 和 ListItr。 不同的是ArrayList 的迭代器在迭代过程中是不上锁的但是Vector上锁所以是线程不安全的。相同是的都有版本号坚持机制Itr迭代过程中不允许集合修改而Listitr 允许修改。 //这里和Vector几乎相同这里只标注不同的地方。
private class Itr implements IteratorE {int cursor; // index of next element to returnint lastRet -1; // index of last element returned; -1 if no suchint expectedModCount modCount;Itr() {}public boolean hasNext() {return cursor ! size;}SuppressWarnings(unchecked)public E next() {//和Vector 不同的是这里Vector会上锁保证线程安全。checkForComodification();int i cursor;if (i size)throw new NoSuchElementException();//这里和Vector不太一样。Vector 是没有这个判断的感觉有个疑问上面都判断了 i size 了//那么能到这里 i 肯定 size 了 而size是实际存储数据的个数即便数组塞满了那也是 size length//怎么可能 i size 却 i length所以感觉这里判断多此一举了。//要知道ArrayLIst是非线程安全的你在迭代的过程中是可能有并发操作修改了容量了而这里做了这样的判断//就是防止并发操作下做下检查。//而这种机制就是fail_fast(快速失败敲黑板)。这里也是做了双重检查checkForComodification也是检查是否被修改//这里拿到 elementData 之后再次检查尽量避免迭代过程中集合被修改。而Vector是加了锁的锁的还是class对象//所以检查一次即可。//这里双重检查就可避免非线程安全问题了吗但是不是比如Object[] elementData ArrayList.this.elementData;if (i elementData.length)throw new ConcurrentModificationException();//--------------------------------------------------- //比如你两次都检查过后到了这里发生了修改还是还会带来问题不过概率降低了。cursor i 1;return (E) elementData[lastRet i];}//这里逻辑 和 Vecotr的迭代器一样的唯一区别少了把锁public void remove() {if (lastRet 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.remove(lastRet);cursor lastRet;lastRet -1;expectedModCount modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}OverrideSuppressWarnings(unchecked)public void forEachRemaining(Consumer? super E consumer) {Objects.requireNonNull(consumer);final int size ArrayList.this.size;int i cursor;if (i size) {return;}final Object[] elementData ArrayList.this.elementData;if (i elementData.length) {throw new ConcurrentModificationException();}while (i ! size modCount expectedModCount) {consumer.accept((E) elementData[i]);}// update once at end of iteration to reduce heap write trafficcursor i;lastRet i - 1;checkForComodification();}//检查版本是否发生变化final void checkForComodification() {if (modCount ! expectedModCount)throw new ConcurrentModificationException();}}private class ListItr extends Itr implements ListIteratorE {ListItr(int index) {super();cursor index;}public boolean hasPrevious() {return cursor ! 0;}public int nextIndex() {return cursor;}public int previousIndex() {return cursor - 1;}SuppressWarnings(unchecked)public E previous() {checkForComodification();int i cursor - 1;if (i 0)throw new NoSuchElementException();Object[] elementData ArrayList.this.elementData;//这里同样多了此检查结构是否变化if (i elementData.length)throw new ConcurrentModificationException();cursor i;return (E) elementData[lastRet i];}//和Vector比少了把锁逻辑一样的public void set(E e) {if (lastRet 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.set(lastRet, e);} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}//这个也是一样的同样少了把锁。public void add(E e) {checkForComodification();try {int i cursor;ArrayList.this.add(i, e);cursor i 1;lastRet -1;expectedModCount modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}}四、总结
ArraList 底层使用数组存储结构删除或添加元素的效率时间复杂度On效率低下。查找元素快 O1。是线程不安全的数据结构并发场景下可能带来非线程安全的问题。扩容是按1.5来进行扩容当然不是绝对的比如第一次添加元素时会判断调用的是那种构造函数无参第一次扩容为10有参且为0扩容后为1。还有就是快要溢出的情况当需要的容量 MAX_ARRAY_SIZE,则新容量为Integer.MAA_VALUE。
