這篇文章給大家介紹怎么在Java中實(shí)現(xiàn)一個(gè)ArrayList.add方法，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

成都創(chuàng)新互聯(lián)公司是一家專業(yè)的成都網(wǎng)站建設(shè)公司，我們專注成都網(wǎng)站建設(shè)、成都網(wǎng)站制作、網(wǎng)絡(luò)營銷、企業(yè)網(wǎng)站建設(shè)，賣鏈接，一元廣告為企業(yè)客戶提供一站式建站解決方案，能帶給客戶新的互聯(lián)網(wǎng)理念。從網(wǎng)站結(jié)構(gòu)的規(guī)劃UI設(shè)計(jì)到用戶體驗(yàn)提高，創(chuàng)新互聯(lián)力求做到盡善盡美。

ArrayList是平時(shí)相當(dāng)常用的List實(shí)現(xiàn), 其中boolean add(E e) 的實(shí)現(xiàn)比較直接:

public boolean add(E e) {
  ensureCapacityInternal(size + 1); // Increments modCount!!
  elementData[size++] = e;
  return true;
}

有時(shí)候也使用 void add(int index, E element) 把元素插入到指定的index上. 在JDK中的實(shí)現(xiàn)是:

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
  rangeCheckForAdd(index);

  ensureCapacityInternal(size + 1); // Increments modCount!!
  System.arraycopy(elementData, index, elementData, index + 1,
           size - index);
  elementData[index] = element;
  size++;
}

略有差別, 需要保證當(dāng)前elementData 數(shù)組容量夠用, 然后把從index處一直到尾部的數(shù)組元素都向后挪一位. 最后把要插入的元素賦給數(shù)組的index處.

一直以來, 我都認(rèn)為 System.arraycopy 這個(gè)native方法, 它的c++實(shí)現(xiàn)是調(diào)用底層的memcpy, 直接方便, 效率也沒問題.

但今天看了openJDK的源碼發(fā)現(xiàn)并非如此.

以openJDK8u60 為例, 在objArrayKlass.cpp 中:

void ObjArrayKlass::copy_array(arrayOop s, int src_pos, arrayOop d,
                int dst_pos, int length, TRAPS) {
 assert(s->is_objArray(), "must be obj array");

 if (!d->is_objArray()) {
  THROW(vmSymbols::java_lang_ArrayStoreException());
 }

 // Check is all offsets and lengths are non negative
 if (src_pos < 0 || dst_pos < 0 || length < 0) {
  THROW(vmSymbols::java_lang_ArrayIndexOutOfBoundsException());
 }
 // Check if the ranges are valid
 if ( (((unsigned int) length + (unsigned int) src_pos) > (unsigned int) s->length())
   || (((unsigned int) length + (unsigned int) dst_pos) > (unsigned int) d->length()) ) {
  THROW(vmSymbols::java_lang_ArrayIndexOutOfBoundsException());
 }

 // Special case. Boundary cases must be checked first
 // This allows the following call: copy_array(s, s.length(), d.length(), 0).
 // This is correct, since the position is supposed to be an 'in between point', i.e., s.length(),
 // points to the right of the last element.
 if (length==0) {
  return;
 }
 if (UseCompressedOops) {
  narrowOop* const src = objArrayOop(s)->obj_at_addr(src_pos);
  narrowOop* const dst = objArrayOop(d)->obj_at_addr(dst_pos);
  do_copy(s, src, d, dst, length, CHECK);
 } else {
  oop* const src = objArrayOop(s)->obj_at_addr(src_pos);
  oop* const dst = objArrayOop(d)->obj_at_addr(dst_pos);
  do_copy (s, src, d, dst, length, CHECK);
 }
}

可以看到copy_array在做了各種檢查之后, 最終copy的部分在do_copy方法中, 而這個(gè)方法實(shí)現(xiàn)如下:

// Either oop or narrowOop depending on UseCompressedOops.
template  void ObjArrayKlass::do_copy(arrayOop s, T* src,
                arrayOop d, T* dst, int length, TRAPS) {

 BarrierSet* bs = Universe::heap()->barrier_set();
 // For performance reasons, we assume we are that the write barrier we
 // are using has optimized modes for arrays of references. At least one
 // of the asserts below will fail if this is not the case.
 assert(bs->has_write_ref_array_opt(), "Barrier set must have ref array opt");
 assert(bs->has_write_ref_array_pre_opt(), "For pre-barrier as well.");

 if (s == d) {
  // since source and destination are equal we do not need conversion checks.
  assert(length > 0, "sanity check");
  bs->write_ref_array_pre(dst, length);
  Copy::conjoint_oops_atomic(src, dst, length);
 } else {
  // We have to make sure all elements conform to the destination array
  Klass* bound = ObjArrayKlass::cast(d->klass())->element_klass();
  Klass* stype = ObjArrayKlass::cast(s->klass())->element_klass();
  if (stype == bound || stype->is_subtype_of(bound)) {
   // elements are guaranteed to be subtypes, so no check necessary
   bs->write_ref_array_pre(dst, length);
   Copy::conjoint_oops_atomic(src, dst, length);
  } else {
   // slow case: need individual subtype checks
   // note: don't use obj_at_put below because it includes a redundant store check
   T* from = src;
   T* end = from + length;
   for (T* p = dst; from < end; from++, p++) {
    // XXX this is going to be slow.
    T element = *from;
    // even slower now
    bool element_is_null = oopDesc::is_null(element);
    oop new_val = element_is_null ? oop(NULL)
                   : oopDesc::decode_heap_oop_not_null(element);
    if (element_is_null ||
      (new_val->klass())->is_subtype_of(bound)) {
     bs->write_ref_field_pre(p, new_val);
     *p = element;
    } else {
     // We must do a barrier to cover the partial copy.
     const size_t pd = pointer_delta(p, dst, (size_t)heapOopSize);
     // pointer delta is scaled to number of elements (length field in
     // objArrayOop) which we assume is 32 bit.
     assert(pd == (size_t)(int)pd, "length field overflow");
     bs->write_ref_array((HeapWord*)dst, pd);
     THROW(vmSymbols::java_lang_ArrayStoreException());
     return;
    }
   }
  }
 }
 bs->write_ref_array((HeapWord*)dst, length);
}

可以看到, 在設(shè)定了heap barrier之后, 元素是在for循環(huán)中被一個(gè)個(gè)挪動(dòng)的. 做的工作比我想象的要多.

如果有m個(gè)元素, 按照給定位置, 使用ArrayList.add(int,E)逐個(gè)插入到一個(gè)長度為n的ArrayList中, 復(fù)雜度應(yīng)當(dāng)是O(m*n), 或者O(m*(m+n)), 所以, 如果m和n都不小的話, 效率確實(shí)是不高的.

效率高一些的方法是, 建立m+n長度的數(shù)組或ArrayList, 在給定位置賦值該m個(gè)要插入的元素, 其他位置依次賦值原n長度List的元素. 這樣時(shí)間復(fù)雜度應(yīng)當(dāng)是O(m+n).

還有, 在前面的實(shí)現(xiàn)中, 我們可以看到有對ensureCapacityInternal(int) 的調(diào)用. 這個(gè)保證數(shù)組容量的實(shí)現(xiàn)主要在:

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
  // 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);
}

大家知道由于效率原因, ArrayList容量增長不是正好按照要求的容量minCapacity來設(shè)計(jì)的, 新容量計(jì)算的主要邏輯是: 如果要求容量比當(dāng)前容量的1.5倍大, 就按照要求容量重新分配空間; 否則按當(dāng)前容量1.5倍增加. 當(dāng)然不能超出Integer.MAX_VALUE了. oldCapacity + (oldCapacity >> 1) 實(shí)際就是當(dāng)前容量1.5倍, 等同于(int) (oldCapacity * 1.5), 但因這段不涉及浮點(diǎn)運(yùn)算只是移位, 顯然效率高不少.

所以如果ArrayList一個(gè)一個(gè)add元素的話, 容量是在不夠的時(shí)候1.5倍增長的. 關(guān)于1.5這個(gè)數(shù)字, 或許是覺得2倍增長太快了吧. 也或許有實(shí)驗(yàn)數(shù)據(jù)的驗(yàn)證支撐.

Java有哪些集合類

Java中的集合主要分為四類：1、List列表：有序的，可重復(fù)的；2、Queue隊(duì)列：有序，可重復(fù)的；3、Set集合：不可重復(fù)；4、Map映射：無序，鍵唯一，值不唯一。

關(guān)于怎么在Java中實(shí)現(xiàn)一個(gè)ArrayList.add方法就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。