源码分析之ArrayList

BNVJayson 7年前
   <p>ArrayList 是我们常用的集合类,是基于数组实现的。不同于数组的是 ArrayList 可以动态扩容。</p>    <h3>类结构</h3>    <p>ArrayList 是 Java 集合框架 List 接口的一个实现类。提供了一些操作数组元素的方法。</p>    <p>实现 List 接口同时,也实现了 RandomAccess , Cloneable , java.io.Serializable 。</p>    <p>ArrayList 继承与 AbstractList 。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/634b38902a9e8056fb5928aeccd752ea.jpg"></p>    <h3>类成员</h3>    <p>elementData</p>    <pre>  <code class="language-java">transient Object[] elementData;  </code></pre>    <p>elementData 是用于保存数据的数组,是 ArrayList 类的基础。</p>    <p>elementData 是被关键字 transient 修饰的。我们知道被 transient 修饰的变量,是不会参与对象序列化和发序列化操作的。而我们知道 ArrayList 实现了 java.io.Serializable ,这就表明 ArrayList 是可序列化的类,这里貌似出现了矛盾。</p>    <p>ArrayList 在序列化和反序列化的过程中,有两个值得关注的方法: writeObject 和 readObject :</p>    <pre>  <code class="language-java">privatevoidwriteObject(java.io.ObjectOutputStream s)      throws java.io.IOException{      // Write out element count, and any hidden stuff      int expectedModCount = modCount;      s.defaultWriteObject();        // Write out size as capacity for behavioural compatibility with clone()      s.writeInt(size);        // Write out all elements in the proper order.      for (int i=0; i<size; i++) {          s.writeObject(elementData[i]);      }        if (modCount != expectedModCount) {          throw new ConcurrentModificationException();      }  }    privatevoidreadObject(java.io.ObjectInputStream s)      throws java.io.IOException, ClassNotFoundException {      elementData = EMPTY_ELEMENTDATA;        // Read in size, and any hidden stuff      s.defaultReadObject();        // Read in capacity      s.readInt(); // ignored        if (size > 0) {          // be like clone(), allocate array based upon size not capacity          ensureCapacityInternal(size);            Object[] a = elementData;          // Read in all elements in the proper order.          for (int i=0; i<size; i++) {              a[i] = s.readObject();          }      }  }  </code></pre>    <p>writeObject 会将 ArrayList 中的 size 和 element 数据写入 ObjectOutputStream 。 readObject 会从 ObjectInputStream 读取 size 和 element 数据。</p>    <p>之所以采用这种序列化方式,是出于性能的考量。因为 ArrayList 中 elementData 数组在 add 元素的过程,容量不够时会动态扩容,这就到可能会有空间没有存储元素。采用上述序列化方式,可以保证只序列化有实际值的数组元素,从而节约时间和空间。</p>    <p>size</p>    <pre>  <code class="language-java">private int size;  </code></pre>    <p>size 是 ArrayList 的大小。</p>    <p>DEFAULT_CAPACITY</p>    <pre>  <code class="language-java">/**   * Default initial capacity.   */  private static final int DEFAULT_CAPACITY = 10;  </code></pre>    <p>ArrayList 默认容量是10。</p>    <p>构造函数</p>    <p>ArrayList 提供了2个构造函数 ArrayList(int initialCapacity) 和 ArrayList() 。</p>    <p>使用有参构造函数初始化 ArrayList 需要指定初始容量大小,否则采用默认值10。</p>    <p>add()方法</p>    <pre>  <code class="language-java">publicbooleanadd(E e){      ensureCapacityInternal(size + 1);  // Increments modCount!!      elementData[size++] = e;      return true;  }  </code></pre>    <p>在 add 元素之前,会调用 ensureCapacityInternal 方法,来判断当前数组是否需要扩容。</p>    <pre>  <code class="language-java">privatevoidensureCapacityInternal(intminCapacity){      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {          // 如果elementData为空数组,指定elementData最少需要多少容量。          // 如果初次add,将取默认值10;          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);      }      ensureExplicitCapacity(minCapacity);  }    privatevoidensureExplicitCapacity(intminCapacity){      modCount++;        // overflow-conscious code      // elementData容量不足的情况下进行扩容      if (minCapacity - elementData.length > 0)          grow(minCapacity);  }    privatevoidgrow(intminCapacity){      // overflow-conscious code      int oldCapacity = elementData.length;      int newCapacity = oldCapacity + (oldCapacity >> 1);      if (newCapacity - minCapacity < 0)          newCapacity = minCapacity;      if (newCapacity - MAX_ARRAY_SIZE > 0)          newCapacity = hugeCapacity(minCapacity);      // minCapacity is usually close to size, so this is a win:      elementData = Arrays.copyOf(elementData, newCapacity);  }  </code></pre>    <ul>     <li> <p>从 grow 方法中可以看出, ArrayList 的 elementData 数组如遇到容量不足时,将会把新容量 newCapacity 设置为 oldCapacity + (oldCapacity >> 1) 。二进制位操作 >> 1 等同于 /2 的效果,扩容导致的 newCapacity 也就设置为原先的1.5倍。</p> </li>     <li> <p>如果新的容量大于 MAX_ARRAY_SIZE 。将会调用 hugeCapacity 将 int 的最大值赋给 newCapacity 。不过这种情况一般不会用到,很少会用到这么大的 ArrayList 。</p> </li>    </ul>    <p>在确保有容量的情况下,会将元素添加至 elementData 数组中。</p>    <p>add(int index, E element) 方法</p>    <pre>  <code class="language-java">publicvoidadd(intindex, E element){      rangeCheckForAdd(index);        ensureCapacityInternal(size + 1);  // Increments modCount!!      System.arraycopy(elementData, index, elementData, index + 1,                       size - index);      elementData[index] = element;      size++;  }  </code></pre>    <p>带有 index 的 add 方法相对于直接 add 元素方法会略有不同。</p>    <ul>     <li>首先会调用 rangeCheckForAdd 来检查,要添加的 index 是否存在数组越界问题;</li>     <li>同样会调用 ensureCapacityInternal 来保证容量;</li>     <li>调用 System.arraycopy 方法复制数组,空出 elementData[index] 的位置;</li>     <li>赋值并增加 size ;</li>    </ul>    <p>remove(int index) 方法</p>    <pre>  <code class="language-java">publicEremove(intindex){      rangeCheck(index);        modCount++;      E oldValue = elementData(index);        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        return oldValue;  }  </code></pre>    <p>ArryList 提供了两个删除 List 元素的方法,如上所示,就是根据 index 来删除元素。</p>    <ul>     <li>检查 index 是否越界;</li>     <li>取出原先值的,如果要删除的值不是数组最后一位,调用 System.arraycopy 方法将待删除的元素移动至 elementData 最后一位。</li>     <li>将 elementData 最后一位赋值为null。</li>    </ul>    <p>remove(Object o) 方法</p>    <pre>  <code class="language-java">publicbooleanremove(Object o){      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;  }  </code></pre>    <p>remove(Object o) 是根据元素删除的,相对来说就要麻烦一点:</p>    <ul>     <li>当元素 o 为空的时候,遍历数组删除空的元素。</li>     <li>当元素 o 不为空的时候,遍历数组找出于 o 元素的 index ,并删除元素。</li>     <li>如果以上两步都没有成功删除元素,返回 false 。</li>    </ul>    <p>modCount</p>    <p>在 add 、 remove 过程中,经常发现会有 modCount++ 或者 modCount-- 操作。这里来看下 modCount 是个啥玩意。</p>    <p>modCount 变量是在 AbstractList 中定义的。</p>    <pre>  <code class="language-java">protected transient int modCount = 0;  </code></pre>    <p>modCount 是一个 int 型变量,用来记录 ArrayList 结构变化的次数。</p>    <p>modCount 起作用的地方是在使用 iterator 的时候。 ArrayList 的 iterator 方法。</p>    <pre>  <code class="language-java">publicIterator<E>iterator(){      return new Itr();  }     private classItrimplementsIterator<E>{      int cursor;       // index of next element to return      int lastRet = -1; // index of last element returned; -1 if no such      int expectedModCount = modCount;        publicbooleanhasNext(){          return cursor != size;      }        @SuppressWarnings("unchecked")      publicEnext(){          checkForComodification();          int i = cursor;          if (i >= size)              throw new NoSuchElementException();          Object[] elementData = ArrayList.this.elementData;          if (i >= elementData.length)              throw new ConcurrentModificationException();          cursor = i + 1;          return (E) elementData[lastRet = i];      }        publicvoidremove(){          if (lastRet < 0)              throw new IllegalStateException();          checkForComodification();            try {              ArrayList.this.remove(lastRet);              cursor = lastRet;              lastRet = -1;              expectedModCount = modCount;          } catch (IndexOutOfBoundsException ex) {              throw new ConcurrentModificationException();          }      }        @Override      @SuppressWarnings("unchecked")      publicvoidforEachRemaining(Consumer<?superE> 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 traffic          cursor = i;          lastRet = i - 1;          checkForComodification();      }        finalvoidcheckForComodification(){          if (modCount != expectedModCount)              throw new ConcurrentModificationException();      }  }  </code></pre>    <p>iterator 方法会返回私有内部类 Itr 的一个实例。这里可以看到 Itr 类中很多方法,都会调用 checkForComodification 方法。来检查 modCount 是够等于 expectedModCount 。如果发现 modCount != expectedModCount 将会抛出 ConcurrentModificationException 异常。</p>    <p>这里写一个小例子来验证体会下 modCount 的作用。简单介绍一下这个小例子:准备两个线程 t1 、 t2 ,两个线程对同一个 ArrayList 进行操作, t1 线程将循环向 ArrayList 中添加元素, t2 线程将把 ArrayList 元素读出来。</p>    <p>Test 类:</p>    <pre>  <code class="language-java">public classTest{        List<String> list = new ArrayList<String>();          publicTest(){        }          publicvoidadd(){            for (int i = 0; i < 10000; i++) {              list.add(String.valueOf(i));          }        }        publicvoidread(){            Iterator iterator = list.iterator();          while (iterator.hasNext()) {              System.out.println(iterator.next());          }        }  </code></pre>    <p>t1 线程:</p>    <pre>  <code class="language-java">public classTest1ThreadimplementsRunnable{        private Test test;        publicTest1Thread(Test test){          this.test = test;      }        publicvoidrun(){            test.add();        }  </code></pre>    <p>t2 线程:</p>    <pre>  <code class="language-java">public classTest2ThreadimplementsRunnable{        private Test test;        publicTest2Thread(Test test){          this.test = test;      }          publicvoidrun(){          test.read();      }  }  </code></pre>    <p>main 类</p>    <pre>  <code class="language-java">publicstaticvoidmain(String[] args)throwsInterruptedException{        Test test = new Test();      Thread t1  = new Thread(new Test1Thread(test));      Thread t2  = new Thread(new Test2Thread(test));        t1.start();      t2.start();    }  </code></pre>    <p>执行这个 mian 类就会发现程序将抛出一个 ConcurrentModificationException 异常。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/c647cb1c46b90d50d9073411836aae90.jpg"></p>    <p>由异常可以发现抛出异常点正处于在调用 next 方法的 checkForComodification 方法出现了异常。这里也就出现上文描述的 modCount != expectedModCount 的情况,原因是 t2 线程在读数据的时候, t1 线程还在不断的添加元素。</p>    <p>这里 modCount 的作用也就显而易见了,用 modCount 来规避多线程中并发的问题。由此也可以看出 ArrayList 是非线程安全的类。</p>    <p> </p>    <p>来自:http://lishuo.me/2017/04/12/源码分析之ArrayList/</p>    <p> </p>