ArrayList

  1. ArrayList底层内存结构

  2. ArrayList的扩容机制

  3. 深、浅拷贝

一些关键概念

标记接口:解析到标记接口，做一些处理

RandomAccess:表明该类支持随机访问(下标访问，就是告诉别人你底层用的是数组)

Cloneable:表明该类支持克隆(深拷贝，浅拷贝)

  1.     /*
  2.         JDK1.7字符串常量池是在堆(常量池)中的
  3.         JDK1.8做了优化，出现一个新概念：元空间(又叫非堆)，元空间并不在虚拟机中，而是使用本地内存(可调节)
  4.     */
  5.     String aa=new String("aa");
  6.     String bb="a"+"a";
  7.     System.out.println(aa==bb);//false 指针相同，但是不相等
  8.     System.out.println(aa.hashCode());
  9.     System.out.println(bb.hashCode());
  10.     System.out.println(aa.equals(bb));//true
  11.     String t1="123"+"4";
  12.     String t2="1234";
  13.     System.out.println(t1==t2);//true String拼接是相同的
  14.     System.out.println(("123"+"4").hashCode());
  15.     System.out.println("1234".hashCode());
  16.     System.out.println(t1.equals(t2));
  17.     String r1=new String("123"+"4");
  18.     String r2=new String("1234");
  19.     System.out.println(r1==r2);//false
  20.     System.out.println(r1.hashCode());
  21.     System.out.println(r2.hashCode());
  22.     System.out.println(r1.equals(r2));//true

Serializable:序列化

  1. public class Demo02 implements Serializable, Cloneable {
  2.     private int id=11;
  3.     private String name="1231321";
  4.     private Demo01 demo01=new Demo01();
  5.     //省略set/get
  7.     @Override
  8.     protected Object clone() throws CloneNotSupportedException {
  9.         //第一种方式(比较死板)
  10.         Object obj = null;
  11.         obj = super.clone();
  12.         Demo02 demo02 = (Demo02) obj;
  13.         //对引用类型的单独处理
  14.         demo02.demo01 = (Demo01) demo01.clone();
  15.         return obj;
  16.     }
  18.     /**
  19.      * <p>使用IO的方式克隆</p>
  20.      *
  21.      * @return
  22.      */
  23.     public Object deepProtoCloneByIO() {
  24.         //创建流对象
  25.         ByteArrayInputStream bis = null;
  26.         ByteArrayOutputStream bos = null;
  27.         ObjectInputStream ois = null;
  28.         ObjectOutputStream oos = null;
  29.         try {
  30.             //序列化
  31.             bos = new ByteArrayOutputStream();
  32.             oos = new ObjectOutputStream(bos);
  33.             oos.writeObject(this);//当前这个对象以对象流的方式输出
  34.             //反序列化
  35.             bis = new ByteArrayInputStream(bos.toByteArray());
  36.             ois = new ObjectInputStream(bis);
  37.             Demo02 o = (Demo02) ois.readObject();
  38.             return o;
  39.         } catch (Exception e) {
  40.             e.printStackTrace();
  41.         }
  42.         return null;
  43.     }
  45. }

ArrayList组成:

私有属性:

  1.     //默认的容量是10
  2.     private static final int DEFAULT_CAPACITY = 10;
  4.     private static final Object[] EMPTY_ELEMENTDATA = {};
  6.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  8.     //elementData存储ArrayList内的元素，
  9.     /*
  10.         transient关键字解释：Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成            员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字             transient
  11.         */
  12.     transient Object[] elementData; // non-private to simplify nested class access
  14.     //size表示它包含的元素的数量。
  15.     private int size;

构造方法:

  2.     public ArrayList(int initialCapacity) {
  3.         if (initialCapacity > 0) {
  4.             this.elementData = new Object[initialCapacity];
  5.         } else if (initialCapacity == 0) {
  6.             this.elementData = EMPTY_ELEMENTDATA;
  7.         } else {
  8.             throw new IllegalArgumentException("Illegal Capacity: "+
  9.                                                initialCapacity);
  10.         }
  11.     }
  14.     public ArrayList() {
  15.         //默认是空数组
  16.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  17.     }
  19.     public ArrayList(Collection<? extends E> c) {
  20.         elementData = c.toArray();
  21.         if ((size = elementData.length) != 0) {
  22.             // c.toArray might (incorrectly) not return Object[] (see 6260652)
  23.             if (elementData.getClass() != Object[].class)
  24.                 elementData = Arrays.copyOf(elementData, size, Object[].class);
  25.         } else {
  26.             // replace with empty array.
  27.             this.elementData = EMPTY_ELEMENTDATA;
  28.         }
  29.     }

操作元素的一些方法:

  • set(int index, E element)
  1. // 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。
  2. public E set(int index, E element) {  
  3.    //检验下他的长度合不合理
  4.    RangeCheck(index);  
  6.    E oldValue = (E) elementData[index];  
  7.    elementData[index] = element;  
  8.    return oldValue;  
  9. }
  • add(E e)
  1. // 将指定的元素添加到此列表的尾部。
  2. public boolean add(E e) {  
  3.    //扩容
  4.    /*
  5.          先调用了ensureCapacity(size+1)方法，之后将元素的索引赋给elementData[size]，而后size自增
  6.    */
  7.    ensureCapacity(size + 1);   
  8.    elementData[size++] = e;  
  9.    return true;  
  10. }
  • add(int index, E element)
  1. // 将指定的元素插入此列表中的指定位置。
  2. // 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。
  3. public void add(int index, E element) {  
  4.    if (index > size || index < 0)  
  5.        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  
  6.    // 如果数组长度不足，将进行扩容。
  7.    ensureCapacity(size+1);  // Increments modCount!!  
  8.       // 将 elementData中从Index位置开始、长度为size-index的元素，  
  9.     // 拷贝到从下标为index+1位置开始的新的elementData数组中。
  10.     // 即将当前位于该位置的元素以及所有后续元素右移一个位置。
  11.    System.arraycopy(elementData, index, elementData, index + 1, size - index);  
  12.    elementData[index] = element;  
  13.    size++;  
  14. }
  • addAll(Collection<? extends E> c)
  1. // 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。
  2. public boolean addAll(Collection<? extends E> c) {  
  3.    Object[] a = c.toArray();  
  4.    int numNew = a.length;  
  5.     //扩容
  6.    ensureCapacity(size + numNew);  // Increments modCount  
  7.    System.arraycopy(a, 0, elementData, size, numNew);  
  8.    size += numNew;  
  9.    return numNew != 0;  
  10. }
  • addAll(int index, Collection<? extends E> c)
  1. // 从指定的位置开始，将指定collection中的所有元素插入到此列表中。
  2. public boolean addAll(int index, Collection<? extends E> c) {  
  3.    if (index > size || index < 0)  
  4.        throw new IndexOutOfBoundsException(  
  5.            "Index: " + index + ", Size: " + size);  
  7.    Object[] a = c.toArray();  
  8.    int numNew = a.length;  
  9.    ensureCapacity(size + numNew);  // Increments modCount  
  11.    int numMoved = size - index;  
  12.    if (numMoved > 0)  
  13.        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);  
  15.    System.arraycopy(a, 0, elementData, index, numNew);  
  16.    size += numNew;  
  17.    return numNew != 0;  
  18.    }
  • romove(int index):
  1. /*
  2.     首先是检查范围，修改modCount，保留将要被移除的元素，将移除位置之后的元素向前挪动一个位置，将list末尾元素置空（null），返回    被移除的元素。
  3. */
  4. public E remove(int index) {
  5.         rangeCheck(index);
  7.         modCount++;
  8.         E oldValue = elementData(index);
  10.         int numMoved = size - index - 1;
  11.         if (numMoved > 0)
  12.             System.arraycopy(elementData, index+1, elementData, index,
  13.                              numMoved);
  14.         elementData[--size] = null; // clear to let GC do its work
  16.         return oldValue;
  17.     }
  • remove(Object o)
  1. /*
  2.     remove(Object o)中通过遍历element寻找是否存在传入对象，一旦找到就调用fastRemove移除对象。为什么找到了元素就知道了index，不通过remove(index)来移除元素呢？因为fastRemove跳过了判断边界的处理，因为找到元素就相当于确定了index不会超过边界，而且fastRemove并不返回被移除的元素
  3. */
  4. public boolean remove(Object o) {
  5.         if (o == null) {
  6.             for (int index = 0; index < size; index++)
  7.                 if (elementData[index] == null) {
  8.                     //这个方法是关键
  9.                     fastRemove(index);
  10.                     return true;
  11.                 }
  12.         } else {
  13.             for (int index = 0; index < size; index++)
  14.                 if (o.equals(elementData[index])) {
  15.                     //这个方法是关键
  16.                     fastRemove(index);
  17.                     return true;
  18.                 }
  19.         }
  20.         return false;
  21.     }
  22. //==============================》fastRemove(int index)
  23.   private void fastRemove(int index) {
  24.         modCount++;
  25.         int numMoved = size - index - 1;
  26.         if (numMoved > 0)
  27.             System.arraycopy(elementData, index+1, elementData, index,
  28.                              numMoved);
  29.         elementData[--size] = null; // clear to let GC do its work
  30.     }

扩容机制:

图解说明:

当ArrayList如果不指定构造个数的话，第一次往里面添加元素时底层数组会初始化一个长度为10的数组,看一下ArrayList里的源码，当添加第11个元素时

Arraylist扩容机制理解 - 图1

再看grow()方法

Arraylist扩容机制理解 - 图2

再看Arrays.copyOf()方法

Arraylist扩容机制理解 - 图3

代码说明:

  • ensureExplicitCapacity(int minCapacity)
  1. private void ensureExplicitCapacity(int minCapacity) {
  2.     modCount++;
  4.     // overflow-conscious code
  5.     if (minCapacity - elementData.length > 0)
  6.         //这里进行了真正的扩容
  7.         grow(minCapacity);
  8. }
  • grow(int minCapacity)
  1. private void grow(int minCapacity) {
  2.         // overflow-conscious code
  3.         int oldCapacity = elementData.length;
  4.         //相当于int newCapacity = oldCapacity + (oldCapacity/2)，但性能会好一些。
  5.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  6.         if (newCapacity - minCapacity < 0)
  7.             newCapacity = minCapacity;
  8.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  9.             newCapacity = hugeCapacity(minCapacity);
  10.         // minCapacity is usually close to size, so this is a win:
  11.         elementData = Arrays.copyOf(elementData, newCapacity);
  12.     }
  • copyOf(U[] original, int newLength, Class<? extends T[]> newType)
  1. public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
  2.     @SuppressWarnings("unchecked")
  3.     T[] copy = ((Object)newType == (Object)Object[].class)
  4.         ? (T[]) new Object[newLength]//这是以新的长度创建一个新的数组
  5.         : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  6.     //把源数组里的元素拷贝到新数组并返回
  7.     System.arraycopy(original, 0, copy, 0,
  8.                      Math.min(original.length, newLength));
  9.     return copy;
  10. }