Java知識(shí)點(diǎn)總結(jié)（Java容器-ArrayList）

xzavier 發(fā)布于2019-08-15 17:54 / 1805人閱讀

摘要：知識(shí)點(diǎn)總結(jié)容器知識(shí)點(diǎn)總結(jié)容器底層實(shí)現(xiàn)是數(shù)組，訪問元素效率高查詢快，插入修改刪除元素慢與相比，它效率高，但線程不安全。

Java知識(shí)點(diǎn)總結(jié)（Java容器-ArrayList）

@(Java知識(shí)點(diǎn)總結(jié))[Java, Java容器, JavaCollection, JavaList]

ArrayList

底層實(shí)現(xiàn)是數(shù)組，訪問元素效率高 (查詢快，插入、修改、刪除元素慢)

與LinkedList相比，它效率高，但線程不安全。

ArrayList數(shù)組是一個(gè)可變數(shù)組，可以存取包括null在內(nèi)的所有元素

每個(gè)ArrayList實(shí)例都有一個(gè)容量，該容量是指用來存儲(chǔ)列表元素的數(shù)組的大小

隨著向ArrayList中不斷增加元素，其容量自動(dòng)增長

在添加大量元素前，應(yīng)用程序也可以使用ensureCapacity操作來增加ArrayList實(shí)例的容量，這樣可以減少遞增式再分配的數(shù)量。

所以如果我們明確所插入元素的多少，最好指定一個(gè)初始容量值，避免過多進(jìn)行擴(kuò)容操作而浪費(fèi)時(shí)間、效率

源碼分析 底層使用數(shù)組實(shí)現(xiàn)

transient  Object[] elementData;

構(gòu)造方法

private  static final int DEFAULT_CAPACITY = 10;
private  static final Object[] EMPTY_ELEMENTDATA = {};
private  static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA  = {};
transient  Object[] elementData;
private  int size;
 
// 構(gòu)造一個(gè)空列表
public  ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;
    }
 
// 構(gòu)造一個(gè)指定初始容量的空列表
public  ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
 
 
// 構(gòu)造一個(gè)指定Collection元素的列表，這些元素按照Connection元素的迭代返回順序進(jìn)行排列
public  ArrayList(Collection c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

存儲(chǔ)

// 在列表的指定位置的元素用element替代，并且返回該位置原來的元素
public  E set(int index, E element) {
        rangeCheck(index); // 檢查數(shù)組容量，拋出：IndexOutOfBoundsException
 
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
 
// 在列表的尾部添加指定元素
public  boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 數(shù)組擴(kuò)容
        elementData[size++] = e;
        return true;
    }
 
// 在列表的指定位置添加元素
public  void add(int index, E element) {
        rangeCheckForAdd(index);
 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
 
        // src:源數(shù)組,srcPro:源數(shù)組中的起始位置
        // dest:目標(biāo)數(shù)組，destPost:目標(biāo)數(shù)組的起始位置，length:要復(fù)制的數(shù)組元素?cái)?shù)量
              // 將當(dāng)前位于該位置的元素以及所有后續(xù)元素后移一個(gè)位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 用element替換index位置的元素
        elementData[index] = element;
        size++;
    }
 
//  在列表的尾部添加Connection中的元素，元素順序按照Connection迭代器返回的順序
public  boolean addAll(Collection c) {
        Object[] a = c.toArray();  // 轉(zhuǎn)化為一個(gè)數(shù)組
 
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
 
        // Increments modCount!!
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
 
//  在列表的指定位置添加Connection中的元素，元素順序按照Connection迭代器返回的順序
public  boolean addAll(int index, Collection c) {
        rangeCheckForAdd(index);
 
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
 
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
 
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

讀取

// 移除此列表指定位置上的元素
public  E remove(int index) {
        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;
    }
 
// 移除此列表中的某個(gè)元素
public  boolean remove(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;
    }
 
private  void fastRemove(int index) {
        modCount++;
        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
    }

數(shù)組擴(kuò)容

每當(dāng)向數(shù)組中添加元素時(shí)，都需要去檢查添加元素后元素的個(gè)數(shù)是否超出當(dāng)前數(shù)組的長度，如果超出，數(shù)組將會(huì)進(jìn)行擴(kuò)容，以滿足添加數(shù)據(jù)的需求。

public  void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA )      
            ? 0 : DEFAULT_CAPACITY;
 
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
 
private  void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
 
        ensureExplicitCapacity(minCapacity);
    }
 
private  void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 
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);
    }
 
private  static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

手寫ArrayList

public  class MyArrayList /*implements List*/{
  private transient Object[] elementData;
  private int size; //元素個(gè)數(shù)
  
  public MyArrayList(){
    this(10);
  }
 
  public MyArrayList(int initialCapacity) {
    if (initialCapacity<0) {
      try {
        throw new Exception();
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    elementData = new  Object[initialCapacity];
  }
  
  public int size() {
    return size;
  }
  
  public boolean isEmpty(){
    return size == 0;
  }
  //根據(jù)index刪掉對象
  public void remove(int index) throws Exception {
    rangeCheck(index);
    int numMoved = size-index-1;
    if (numMoved > 0) {
      System.arraycopy(elementData, index+1, elementData, index, numMoved);
    }
    elementData[--size] = null;
  }
  //刪掉對象
  public boolean remove(Object obj) throws Exception {
    for (int i = 0; i < size; i++) {
      if (get(i).equals(obj)) {
        remove(i);
      }
      return true;
    }
    return true;
  }
  //修改元素
  public Object  set(int  index , Object obj ) throws Exception{
    rangeCheck(index);
    Object oldValue = elementData[index];
    elementData[index] = obj;
    return oldValue;
  }
  //在指定位置插入元素
  public void add(int index,Object obj) throws Exception {
    rangeCheck(index);
    ensureCapacity();
    System.arraycopy(elementData, index, elementData, index+1, size-index);
    elementData[index] = obj;
    size ++;
  }
  public void add(Object object) {
    ensureCapacity();
    /*elementData[size] = object;
    size ++;*/
    elementData[size++] = object; //先賦值，后自增
  }
  
  public Object get(int  index) throws Exception {
    rangeCheck(index);
    return elementData[index];
  }
  public void rangeCheck(int index) throws Exception {
    if (index<0 || index >=size) {
      throw new Exception();
    }
  }
  //擴(kuò)容
  public  void  ensureCapacity() {
    //數(shù)組擴(kuò)容和內(nèi)容拷貝
    if (size==elementData.length) {
      //elementData = new  Object[size*2+1]; 這么寫原來數(shù)組里的內(nèi)容丟失
      Object[] newArray = new  Object[size*2+1];
      //拷貝數(shù)組里的內(nèi)容
      /*for (int i = 0; i < newArray.length; i++) {
        newArray[i] = elementData[i];
      }*/
      System.arraycopy(elementData, 0, newArray, 0, elementData.length);
      elementData = newArray;
    }
  }
  // 測試
  public static void main(String[] args) {
    MyArrayList myArrayList = new MyArrayList(3);
    myArrayList.add("111");
    myArrayList.add("222");
    myArrayList.add("333");
    myArrayList.add("444");
    myArrayList.add("555");
    
    try {
      myArrayList.remove(2);
      myArrayList.add(3, "新值");
      myArrayList.set(1, "修改");
    } catch (Exception e1) {
      // TODO Auto-generated catch block
      e1.printStackTrace();
    }
    System.out.println(myArrayList.size());
    for (int i = 0; i < myArrayList.size(); i++) {
      try {
        System.out.println(myArrayList.get(i));
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
  }
}