A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 大蓝鲸Java 于 2017-12-1 12:33 编辑

【南京校区】 ArrayList完全解析

    在平时的资料学习中,很多都认为ArrayList底层是数组,默认长度为10,每次扩容1.5倍.但是实际上真的是这样的吗?本文从源码角度做详细的分析.
      ArrayList 有三个构造:
                1, public ArrayList() {}
                2,public ArrayList(int initialCapacity) { }
                3,public ArrayList(Collection<? extends E> c) {}
             其中第一个构造表示将一个空的数组赋值给集合底层的那个数组.
             第二个构造表示将创建一个指定容量大小的集合
             第三个方法是创建一个集合,将参数集合的数据都添加到现在创建的集合中,类似addAll();
           另外ArrayList 承于AbstractList,实现了List接口,是一个长度可变的集合,提供了增删改查的功能。集合中允许null的存在。ArrayList类还是实现了RandomAccess接口,可以对元素进行快速访问。实现了Serializable接口,说明ArrayList可以被序列化,还有Cloneable接口,可以被复制。和Vector不同的是,ArrayList不是线程安全的。

方法解析:
                 void add(int index, E element)   将指定的元素插入此列表中的指定位置。
                           //如果集合中最大索引是3.
                           那么调用此方法,可以在4索引插入元素。但是超过4索引就报错了。
-----------------------------------------------------------------------------------------------------------------------
                boolean add(Object e): 向集合中添加元素
                            //方法源码分析:
                            public boolean add(E e) {
                                     ensureCapacityInternal(size + 1);        //重新计算长度,并让modCount++
                                                                                               //modCount是并发修改异常中的关键,下面会解释
                                     elementData[size++] = e;//每次往数组的末尾存。保证了存取有序
                                     return true;        //因为ArrayList可重复所以每次都是true。跟HashSet相对
                            }
                            -----------------------        
                            private void ensureCapacityInternal(int minCapacity) {
                                  if (elementData == EMPTY_ELEMENTDATA) {
                                            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//默认大小跟实际大小比较
                                   }        //保证了ArrayList只要刚开始添加就有一个默认10大小的容量,因为DEFAULT_CAPACITY = 10;
                                            ensureExplicitCapacity(minCapacity);
                             }
                            ------------------------
                            private void ensureExplicitCapacity(int minCapacity) {
                                  modCount++;//modCount是并发修改异常中的关键,下面会解释
                                       if (minCapacity - elementData.length > 0)//比较长度
                                             grow(minCapacity);
                            }
                           ------------------------
                            private void grow(int minCapacity) {
                                   int oldCapacity = elementData.length;//旧容量
                                       int newCapacity = oldCapacity + (oldCapacity >> 1);//新容量 = 旧容量 + 旧容量/2
                                       if (newCapacity - minCapacity < 0)
                                              newCapacity = minCapacity;
                                       if (newCapacity - MAX_ARRAY_SIZE > 0)
                                              newCapacity = hugeCapacity(minCapacity);
                                              elementData = Arrays.copyOf(elementData, newCapacity);//数组的拷贝//底层调用System.arraycopy拷贝
                              }
        终上所述:ArrayList 底层是一个长度为0的数组。在刚添加一个元素后,变成默认大小10.
                          只要是存满了。那么就把原来的长度*1.5(也就是扩容原先的1.5倍大小。)
                          如果此时一下子添加多个元素,那么会拿添加元素个数 + 原来集合的个数 跟扩容之后的1.5倍相比,比一比谁长. 谁长听谁的.
                          再创建了一个新的数组,新的数组的长度为比较后的结果
                          利用 System.arraycopy 的方法将原数组的内容拷贝到新的数组中去。

-----------------------------------------------------------------------------------------------------------------------
                void clear():清空集合中所有元素
                               //方法源码分析
                               for (int i = 0; i < size; i++)  //遍历集合
                               elementData = null;            //得到每一个元素,把每一个元素变成null
                               size = 0;                             //将长度变为0
-----------------------------------------------------------------------------------------------------------------------
                boolean contains(Object o):判断集合中是否包含某个元素
                              //方法源码分析
                              public boolean contains(Object o) {
                                      return indexOf(o) >= 0;//调用indexOf看参数在集合中是多少索引。
                                                                           //如果索引为正数,那么集合中就包含参数
                                                        }
                             ------------------------
                               public int indexOf(Object o) {
                                    if (o == null) {        //判断参数是否为null
                                        for (int i = 0; i < size; i++)//遍历
                                                 if (elementData==null)//判断遍历到的是否为null
                                                      return i;                //如果存在就直接return
                                    } else {
                                        for (int i = 0; i < size; i++)//遍历
                                               if (o.equals(elementData))//利用equals进行判断
                                                       return i;                //如果存在就直接return
                                              }
                                              return -1;//如果不存在就return-1
                                }
        终上所述:"方法底层是依赖 equals" 方法来判断是否是否与集合内部某一个元素相同。
                          如果我们没有重写equals。那么用的是object里面的equals。此时判断的是地址值。
                          当遇到一个匹配的直接return,所以当重复时候,只能返回第一个。

-----------------------------------------------------------------------------------------------------------------------

                boolean isEmpty():判断集合中的元素是否为空
                          //方法源码分析
                               public boolean isEmpty() {
                                return size == 0;//就是判断长度是否为0
                             }
-----------------------------------------------------------------------------------------------------------------------
                boolean remove(Object o):根据元素的内容来删除某个元素
                           //方法源码分析
                             public boolean remove(Object o) {
                                  if (o == null) {//判断参数是否为null
                                     for (int index = 0; index < size; index++)//遍历
                                          if (elementData[index] == null) {
                                               fastRemove(index);        //调用另外的方法删除。
                                                 return true;//只要成功删除一个,就直接return了。
                                         }
                                    } else {
                                         for (int index = 0; index < size; index++)//遍历
                                            if (o.equals(elementData[index])) {"方法底层是依赖 equals"
                                                  fastRemove(index);//调用另外的方法删除。
                                                         return true;//只要成功删除一个,就直接return了。
                                           }
                                        }
                                                return false;
                                     }
                      ------------------------
                                  private void fastRemove(int index) {
                                         modCount++; //重新计算长度,并让modCount++
                                                                //modCount是并发修改异常中的关键,下面会解释
                                         int numMoved = size - index - 1;//表示要删除的元素右边还有几个
                                         if (numMoved > 0)
                                        System.arraycopy(elementData, index+1, elementData, index,numMoved);//把数组复制给自己。
                                                                                              //从要删除的后一个开始复制给自己
                                                                                              //复制到要删除的索引开始,复制numMoved个。
                                           elementData[--size] = null;
                                   }
                                      "方法底层是依赖 equals"
        终上所述:"方法底层是依赖 equals" 方法来判断是否是否与集合内部某一个元素相同。
                          如果我们没有重写equals。那么用的是object里面的equals。此时判断的是地址值。
                          当遇到一个匹配的直接return,所以当重复时候,只能删除第一个。
                          删除完毕,数组长度--。调用System.arraycopy拷贝给自己。
        "注意点"
                boolean remove(Object o)有一个重载的方法
                E remove(int index)
                在ArrayList<Integer> al = new ArrayList<>();这样创建对象
                        用al调用remove.传递2
                        al.remove(2);//此处的2不会自动装箱。删除的是2索引
                但是如果 Collection<Integer> al = new ArrayList<>();这样创建对象
                        用al调用remove.传递2
                        al.remove(2);//多态创建
                        编译看左边,Collection中只有remove(Object o)的方法
                        所以右边会走remove(Object o)
-----------------------------------------------------------------------------------------------------------------------
                int size():获取集合的长度
                          //方法源码分析
                         public int size() {
                             return size;//实际上就是数组的长度
                         }
-----------------------------------------------------------------------------------------------------------------------
                Object[] toArray():能够将集合转换成数组并把集合中的元素存储到数组中
                       //方法源码分析
                       public Object[] toArray() {
                              return Arrays.copyOf(elementData, size);
                      }
------------------------------------------------------------------------------------------------------------------
                    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
                                   // original 要拷贝的数组  newLength 集合的长度,也就是转成数组后数组的长度
                          T[] copy = ((Object)newType == (Object)Object[].class)?
                                 (T[]) new Object[newLength]//创建一个Object类型的数组,再转换成T类型的数组。
                                    //T就是toArray()重载方法toArray(T[] a)传递的参数
                                    : (T[]) Array.newInstance(newType.getComponentType(), newLength);
                               System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
                                             //数组的复制
                           return copy;//将创建的数组返回。
                 }
        终上所述:如果是 toArray()就创建了一个新的Object类型的数组。
                          如果有参数toArray(new String[0])就创建了一个新的Object类型的数组再转成String类型
                          利用System.arraycopy的方法,将元素拷贝到数组中去。再将新数组返回
-----------------------------------------------------------------------------------------------------------------------
                <T> T[] toArray(T[] a):能够将集合转换成数组并把集合中的元素存储到数组中
                         public <T> T[] toArray(T[] a) {
                                if (a.length < size)//如果参数数组长度小于集合长度
                                        return (T[]) Arrays.copyOf(elementData, size, a.getClass());//按照集合长度进行拷贝
                                   System.arraycopy(elementData, 0, a, 0, size);//如果参数数组长度大于集合长度直接拷贝
                                 if (a.length > size)//将过于的赋值为null
                                        a[size] = null;//引用数据类型默认null。所以不赋值也是可以的,就是初始化值
                                             return a;//将数组返回
                               }
        终上所述:如果有参数toArray(new String[0])
                                先判断0跟集合长度的大小。如果集合长度大,按照集合长度进行拷贝,创建一个新的Object类型的数组再转成String类型
                                利用System.arraycopy的方法,将元素拷贝到数组中去。再将新数组返回
                                如果一样长,直接拷贝
                                如果参数数组长度大,那么后面的赋值为null。因为集合是引用数据类型。
                                所以直接是默认初始化值
                          "从效率而言,此处toArray(new String[list.size()])"
                          参数大小设置为集合长度最合适。

4 个回复

正序浏览
大神大神,膝盖给你!
回复 使用道具 举报
郭俊峰老师 来自手机 高级黑马 2017-12-5 16:15:56
板凳
集合写了那么多,用得最多是array
回复 使用道具 举报
我表示很崇拜的路过
回复 使用道具 举报
厉害了我的哥!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马