国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Java ArrayList.add 的實(shí)現(xiàn)

raledong / 3439人閱讀

摘要:是平時(shí)相當(dāng)常用的實(shí)現(xiàn)其中的實(shí)現(xiàn)比較直接有時(shí)候也使用把元素插入到指定的上在中的實(shí)現(xiàn)是略有差別需要保證當(dāng)前數(shù)組容量夠用然后把從處一直到尾部的數(shù)組元素都向后挪一位最后把要插入的元素賦給數(shù)組的處一直以來我都認(rèn)為這個(gè)方法它的實(shí)現(xiàn)是調(diào)用底層的直接方便

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

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return true (as specified by {@link Collection#add})
 */
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è)長(zhǎng)度為n的ArrayList中, 復(fù)雜度應(yīng)當(dāng)是O(m*n), 或者O(m*(m+n)), 所以, 如果m和n都不小的話, 效率確實(shí)是不高的.

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

還有, 在前面的實(shí)現(xiàn)中, 我們可以看到有對(duì)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容量增長(zhǎng)不是正好按照要求的容量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倍增長(zhǎng)的. 關(guān)于1.5這個(gè)數(shù)字, 或許是覺得2倍增長(zhǎng)太快了吧. 也或許有實(shí)驗(yàn)數(shù)據(jù)的驗(yàn)證支撐.

關(guān)于這段代碼中出現(xiàn)的Arrays.copyOf這個(gè)方法, 實(shí)現(xiàn)的是重新分配一段數(shù)組, 把elementData賦值給新分配的空間, 如果新分配的空間大, 則后面賦值null, 如果分配空間比當(dāng)前數(shù)組小則截?cái)? 底層還是調(diào)用的System.arraycopy.

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/72033.html

相關(guān)文章

  • JAVA 集合框架

    摘要:接口下面包含等。但是接口并沒有繼承接口,因此無法迭代。分離出接口是迭代器模式。但是接口又提供了接口以后將轉(zhuǎn)換成集合來迭代。的增強(qiáng)循環(huán)也只適用于那些繼承了接口的。 Iterator接口是Collection接口的父接口。Collection接口下面包含List,Set,Queue等。 Map接口與Collection接口同級(jí)。但是Map接口并沒有繼承Iterator接口,因此無法迭代。 ...

    galaxy_robot 評(píng)論0 收藏0
  • 深入了解Java集合中ArrayList

    摘要:實(shí)現(xiàn)了接口,所以包含的基本方法新增,刪除,插入等都實(shí)現(xiàn)了。線程安全問題在多線程情況下有線程進(jìn)行修改時(shí),是線程不安全的。線程安全性問題,取決于如何應(yīng)用。反映的是當(dāng)前數(shù)組中存了多少數(shù)據(jù),而則反映的是內(nèi)部數(shù)組的容量。 什么是ArrayList ArrayList 是一個(gè)可擴(kuò)容數(shù)組Resizable-array,它實(shí)現(xiàn)了List接口的所有方法。 從對(duì)ArrayList的簡(jiǎn)單描述中我們可以得出...

    zeyu 評(píng)論0 收藏0
  • Java 中初始化 List 集合 6 種方式!

    摘要:是開發(fā)中經(jīng)常會(huì)使用的集合,你們知道有哪些方式可以初始化一個(gè)嗎這其中不缺乏一些坑,今天棧長(zhǎng)我給大家一一普及一下。好了,今天棧長(zhǎng)就給大家介紹到這里了,這種,你知道幾種另外,也有類似的初始化的方法,大家有興趣的可以試一下。 List 是 Java 開發(fā)中經(jīng)常會(huì)使用的集合,你們知道有哪些方式可以初始化一個(gè) List 嗎?這其中不缺乏一些坑,今天棧長(zhǎng)我給大家一一普及一下。 1、常規(guī)方式 List...

    Binguner 評(píng)論0 收藏0
  • java集合

    摘要:主要用于遍歷集合中的元素,對(duì)象也被稱為迭代器。使用迭代過程中,不可修改集合元素迭代器采用快速失敗機(jī)制。一旦迭代過程中檢測(cè)到該集合已經(jīng)被修改,程序立即出發(fā)異常,而不是顯示修改后的結(jié)果,避免了共享資源而引發(fā)的潛在問題。 集合類和數(shù)組不一樣,數(shù)組元素既可以是基本類型的值,也可以是對(duì)象(實(shí)際上保存的是對(duì)象的引用變量);而集合里只能保存對(duì)象(實(shí)際上只是保存對(duì)象的引用變量,但通常習(xí)慣上認(rèn)為集...

    JinB 評(píng)論0 收藏0
  • java-list-map-set 學(xué)習(xí)記錄

    摘要:集合類類型解釋的父類集集合中的元素不按特定方式排序,并且沒有重復(fù)對(duì)象。他的有些實(shí)現(xiàn)類能對(duì)集合中的鍵對(duì)象進(jìn)行排序。 集合類 2017-07-10 22:24:57 blog site https://github.com/Fiz1994 類型解釋: Collection : Set,List 的父類 Set(集):集合中的元素不按特定方式排序,并且沒有重復(fù)對(duì)象。他的有些實(shí)現(xiàn)類能對(duì)集合中的...

    stackvoid 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

raledong

|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<