ArrayList , Vector 数组集结

 - set() / get(),直接操作下标指针, - set() / get(),直接操作下标指针,需要哪些全局变量和函数,添加一个元素到集合尾部,二、有关List使用注意事项,不能使用其修改集合相关的方法

图片 5

ArrayList , Vector 数组群集,arraylistvector

ArrayList 的一部分认知:

■ 类定义

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  • 继续 AbstractList,达成了
    List,它是三个数组成代表队列,提供了连带的拉长、删除、修改、遍历等作用
  • 贯彻 RandmoAccess
    接口,达成高效随机访谈:通过成分的序号火速得到成分对象
  • 兑现 Cloneable 接口,重写 clone(),能被克隆(浅拷贝)
  • 福寿年高 java.io.Serializable 接口,援助系列化

■ 全局变量

/**
  * The array buffer into which the elements of the ArrayList are stored.
  * The capacity of the ArrayList is the length of this array buffer. Any
  * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
  * DEFAULT_CAPACITY when the first element is added.
  * ArrayList底层实现为动态数组; 对象在存储时不需要维持,java的serialzation提供了持久化
  * 机制,我们不想此对象被序列化,所以使用 transient
  */
private transient Object[] elementData;

/**
  * The size of the ArrayList (the number of elements it contains).
  * 数组长度 :注意区分长度(当前数组已有的元素数量)和容量(当前数组可以拥有的元素数量)的概念
  * @serial
  */
private int size;
/**
  * The maximum size of array to allocate.Some VMs reserve some header words in an array.
  * Attempts to allocate larger arrays may result in OutOfMemoryError: 
  * Requested array size exceeds VM limit
  * 数组所能允许的最大长度;如果超出就会报`内存溢出异常` -- 可怕后果就是宕机
  */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

 

■ 构造器

/**
  * Constructs an empty list with the specified initial capacity.
  * 创建一个指定容量的空列表
  * @param  initialCapacity  the initial capacity of the list
  * @throws IllegalArgumentException if the specified initial capacity is negative
  */
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    this.elementData = new Object[initialCapacity];
}

/**
  * Constructs an empty list with an initial capacity of ten.
  * 默认容量为10
  */
public ArrayList() {
    this(10);
}

/**
  * Constructs a list containing the elements of the specified collection,
  * in the order they are returned by the collection's iterator.
  * 接受一个Collection对象直接转换为ArrayList
  * @param c the collection whose elements are to be placed into this list
  * @throws NullPointerException if the specified collection is null 万恶的空指针异常
  */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();//获取底层动态数组
    size = elementData.length;//获取底层动态数组的长度
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

 

■首要措施

 - add()

  • 从源码上看,ArrayList 一般在尾巴部分插入成分,支持动态扩大容积
  • 不推荐使用频仍插入/删除是因为在施行add()/remove() 会调用特别耗费时间的
    System.arraycopy(),频仍插入/删除场景请选择 LinkedList

/**
  * Appends the specified element to the end of this list.
  * 使用尾插入法,新增元素插入到数组末尾
  *  由于错误检测机制使用的是抛异常,所以直接返回true
  * @param e element to be appended to this list
  * @return <tt>true</tt> (as specified by {@link Collection#add})
  */
public boolean add(E e) {
    //调整容量,修改elementData数组的指向; 当数组长度加1超过原容量时,会自动扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!! add属于结构性修改
    elementData[size++] = e;//尾部插入,长度+1
    return true;
}

/**
  * 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) {
    //下标边界校验,不符合规则 抛出 `IndexOutOfBoundsException` 
    rangeCheckForAdd(index);
    //调整容量,修改elementData数组的指向; 当数组长度加1超过原容量时,会自动扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //注意是在原数组上进行位移操作,下标为 index+1 的元素统一往后移动一位
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;//当前下标赋值
    size++;//数组长度+1
}

  - ensureCapacity() : 扩容,1.8 有个暗中同意值的决断

//1.8 有个默认值的判断
public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
}


private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

 - set() / get(): 直接操作下标指针

/**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        rangeCheck(index);  //检测插入的位置是否越界

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

/**
 * Returns the element at the specified position in this list.
 * 
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

 - remove(): 移除其实和add差不离,也是用的是 System.arrayCopy(…)

/**
  * Removes the element at the specified position in this list.
  * Shifts any subsequent elements to the left (subtracts one from their indices).
  * 
  * 移除指定下标元素,同时大于该下标的所有数组元素统一左移一位
  * 
  * @param index the index of the element to be removed
  * @return the element that was removed from the list 返回原数组元素
  * @throws IndexOutOfBoundsException {@inheritDoc}
  */
public E remove(int index) {
    rangeCheck(index);//下标边界校验
    E oldValue = elementData(index);//获取当前坐标元素
    fastRemove(int index);//这里我修改了一下源码,改成直接用fastRemove方法,逻辑不变
    return oldValue;//返回原数组元素
}

/**
  * Removes the first occurrence of the specified element from this list,if it is present.
  * If the list does not contain the element, it is unchanged.
  * More formally, removes the element with the lowest index <tt>i</tt> such that
  * <tt>(o==null?get(i)==null:o.equals(get(i)))</tt> (if such an element exists).
  * Returns <tt>true</tt> if this list contained the specified element
  * (or equivalently, if this list changed as a result of the call).
  * 直接移除某个元素:
  *     当该元素不存在,不会发生任何变化
  *     当该元素存在且成功移除时,返回true,否则false
  *     当有重复元素时,只删除第一次出现的同名元素 :
  *        例如只移除第一次出现的null(即下标最小时出现的null)
  * @param o element to be removed from this list, if present
  * @return <tt>true</tt> if this list contained the specified element
  */
public boolean remove(Object o) {
    //按元素移除时都需要按顺序遍历找到该值,当数组长度过长时,相当耗时
    if (o == null) {//ArrayList允许null,需要额外进行null的处理(只处理第一次出现的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;
}

 - 封装 fastRemove()

/*
     * Private remove method that skips bounds checking and does not return the value removed.
     * 私有方法,除去下标边界校验以及不返回移除操作的结果
     */
    private void fastRemove(int index) {
        modCount++;//remove操作属于结构性改动,modCount计数+1
        int numMoved = size - index - 1;//需要左移的长度
        if (numMoved > 0)
            //大于该下标的所有数组元素统一左移一位
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // Let gc do its work 长度-1,同时加快gc
    }

■ 遍历、排序

/**
 * Created by meizi on 2017/7/31.
 * List<数据类型> 排序、遍历
 */
public class ListSortTest {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<Integer>();
        nums.add(3);
        nums.add(5);
        nums.add(1);
        nums.add(0);

        // 遍历及删除的操作
        /*Iterator<Integer> iterator = nums.iterator();
        while (iterator.hasNext()) {
            Integer num = iterator.next();
            if(num.equals(5)) {
                System.out.println("被删除元素:" + num);
                iterator.remove();  //可删除
            }
        }
        System.out.println(nums);*/

        //工具类(Collections) 进行排序
        /*Collections.sort(nums);   //底层为数组对象的排序,再通过ListIterator进行遍历比较,取替
        System.out.println(nums);*/

        //②自定义排序方式
        /*nums.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(o1 > o2) {
                    return 1;
                } else if (o1 < o2) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        System.out.println(nums);*/

        //遍历 since 1.8
        Iterator<Integer> iterator = nums.iterator();
        iterator.forEachRemaining(obj -> System.out.print(obj));   //使用lambda 表达式

        /**
         * Objects 展示对象各种方法,equals, toString, hash, toString
         */
        /*default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
        }*/
    }

}

 

■ list 与 Array 的改造难题

  • Object[] toArray(); 或者会产生 ClassCastException
  • <T> T[] toArray(T[] contents) — 调用 toArray(T[]
    contents) 能不奇怪重返 T[]

public class ListAndArray {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("java");
        list.add("C++");
        String[] strings = list.toArray(new String[list.size()]);  //使用泛型可避免类型转换的异常,因为java不支持向下转换
        System.out.println(strings[0]);
    }
}

 

■ 关于Vector 就不详细介绍了,因为官方也并不推荐使用: (JDK 1.0)

 

, Vector 数组集合,arraylistvector
ArrayList的部分认识: ■ 类定义 public class ArrayListE extends
AbstractListE implements ListE, RandomAccess, Cloneable,…

■ 类定义

2.3.5 两个toArray方法

  • 1

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
  • 2

public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

如果toArray()需要向下转型(例如将Object[]退换为的Integer[]),则需求选用第2种方法,传入三个子类数组(如下代码段)。不然间接运用第1种办法。由于java不帮忙向下转型,第1种艺术会抛java.lang.ClassCastException至极。

public static Integer[] toArray(ArrayList<Integer> arrayList) {
    Integer[] newArrayList = (Integer[])arrayList.toArray(new Integer[0]);
    return newArrayList;
}

跟arrayList大约,唯一不一样vector是线程安全的。扩大容积2倍

/**
  * Removes the element at the specified position in this list.
  * Shifts any subsequent elements to the left (subtracts one from their indices).
  * 
  * 移除指定下标元素,同时大于该下标的所有数组元素统一左移一位
  * 
  * @param index the index of the element to be removed
  * @return the element that was removed from the list 返回原数组元素
  * @throws IndexOutOfBoundsException {@inheritDoc}
  */
public E remove(int index) {
    rangeCheck(index);//下标边界校验
    E oldValue = elementData(index);//获取当前坐标元素
    fastRemove(int index);//这里我修改了一下源码,改成直接用fastRemove方法,逻辑不变
    return oldValue;//返回原数组元素
}

/**
  * Removes the first occurrence of the specified element from this list,if it is present.
  * If the list does not contain the element, it is unchanged.
  * More formally, removes the element with the lowest index <tt>i</tt> such that
  * <tt>(o==null?get(i)==null:o.equals(get(i)))</tt> (if such an element exists).
  * Returns <tt>true</tt> if this list contained the specified element
  * (or equivalently, if this list changed as a result of the call).
  * 直接移除某个元素:
  *     当该元素不存在,不会发生任何变化
  *     当该元素存在且成功移除时,返回true,否则false
  *     当有重复元素时,只删除第一次出现的同名元素 :
  *        例如只移除第一次出现的null(即下标最小时出现的null)
  * @param o element to be removed from this list, if present
  * @return <tt>true</tt> if this list contained the specified element
  */
public boolean remove(Object o) {
    //按元素移除时都需要按顺序遍历找到该值,当数组长度过长时,相当耗时
    if (o == null) {//ArrayList允许null,需要额外进行null的处理(只处理第一次出现的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;
}

2.ArrayList的数据结构

图片 1

  1. 矢量队列,功效等效于ArrayList,线程安全
  2. 官方不引入应用该类,非线程安全推荐 ArrayList,线程安全推荐
    CopyOnWriteList
  3. 区分于arraylist, 全体办法都以 synchronized 修饰的,所以是线程安全

2.1 类定义

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable,
java.io.Serializable

  • 此起彼落AbstractList:完毕了List,对List中至关心爱慕要操作的兑现,包罗add,remove等
  • 贯彻 RandmoAccess
    接口:辅助高效随机访谈,即经过元素的序号快捷获得成分对象
  • 兑现Cloneable:重写clone(),能被克隆(浅拷贝)
  • 落实Serializable:补助种类化

5、使用集结转数组的主意,必须采纳toArray(T[]
array),传入是项目同样的数组(大小最好是和list.size()一致,否则在转变进程需重新分配内部存款和储蓄器空间,并回到新数组地址)。

 

2.5.1 modCount与Fail-Fast机制

modCount记录数组被涂改的次数,作为线程不安全的集合类的成员变量,重要用在迭代器以及种类化writeObject()等情景。由下面迭代器代码能够观察,每趟获得成分从前都会检查当前modCount与该迭代器对象起初化时的modCount是不是一样,即便差异等,则抛出十分。这正是Fail-Fast机制。对于线程不安全的会集类,通过modCount域快捷检查群集内容是还是不是有浮动。JDK为了提示开荒者将非线程安全的类使用到出现的情景下时,抛出八个十分,尽早开掘代码中的难点。当然,这种体制并不一定有效。首先,jdk1.7中收回了modCount的volatitle修饰符,失去了逐一线程直接对modCount的可知性。
注意:
在利用迭代器对象时,是能够修改数据的。即一下代码是合法的。

while (iterator.hasNext()) {    
  if(iterator.next().equals("c")) {        
    iterator.remove("c");    
  }
}

public boolean hasNext() {
            return cursor < limit;
        }

由来在于:hasNext()方法并不曾选择modCount实行判断,而是相比下二个成分的地点与数组总省长度。

    private void writeObject(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();

private class Itr implements Iterator<E> {
        // The "limit" of this iterator. This is the size of the list at the time the
        // iterator was created. Adding & removing elements will invalidate the iteration
        // anyway (and cause next() to throw) so saving this value will guarantee that the
        // value of hasNext() remains stable and won't flap between true and false when elements
        // are added and removed from the list.
        protected int limit = ArrayList.this.size;

        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor < limit;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        ……
}

4、在subList场景中,要低度注意对原集合成分个数的修改,会导致子列表的遍历、扩张、删除均发生ConcurrentModificationException至极,
如:

/**
  * The array buffer into which the elements of the ArrayList are stored.
  * The capacity of the ArrayList is the length of this array buffer. Any
  * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
  * DEFAULT_CAPACITY when the first element is added.
  * ArrayList底层实现为动态数组; 对象在存储时不需要维持,java的serialzation提供了持久化
  * 机制,我们不想此对象被序列化,所以使用 transient
  */
private transient Object[] elementData;

/**
  * The size of the ArrayList (the number of elements it contains).
  * 数组长度 :注意区分长度(当前数组已有的元素数量)和容量(当前数组可以拥有的元素数量)的概念
  * @serial
  */
private int size;
/**
  * The maximum size of array to allocate.Some VMs reserve some header words in an array.
  * Attempts to allocate larger arrays may result in OutOfMemoryError: 
  * Requested array size exceeds VM limit
  * 数组所能允许的最大长度;如果超出就会报`内存溢出异常` -- 可怕后果就是宕机
  */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

2.3.4 writeObject()方法

    private void writeObject(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();

这里不间接利用s.writeObject(elementData)的格局,是因为思考到数组有一部分空暇的上空没有须要系列化。

4、数据结构:数组情势 private transient Object[] elementData;

■ 构造器

2.3.3 sort()方法

    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

留意:ArrayList的排序采取的是折半插入排序。

     * Sorts the specified portion of the specified array using a binary
     * insertion sort.  This is the best method for sorting small numbers
     * of elements.  It requires O(n log n) compares, but O(n^2) data
     * movement (worst case).
* @param a the array in which a range is to be sorted
     * @param lo the index of the first element in the range to be sorted
     * @param hi the index after the last element in the range to be sorted
     * @param start the index of the first element in the range that is
     *        not already known to be sorted ({@code lo <= start <= hi})
     */
    @SuppressWarnings({"fallthrough", "rawtypes", "unchecked"})
    private static void binarySort(Object[] a, int lo, int hi, int start) {
        assert lo <= start && start <= hi;
        if (start == lo)
            start++;
        for ( ; start < hi; start++) {
            Comparable pivot = (Comparable) a[start];

            // Set left (and right) to the index where a[start] (pivot) belongs
            int left = lo;
            int right = start;
            assert left <= right;
            /*
             * Invariants:
             *   pivot >= all in [lo, left).
             *   pivot <  all in [right, start).
             */
            while (left < right) {
                int mid = (left + right) >>> 1;
                if (pivot.compareTo(a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            /*
             * The invariants still hold: pivot >= all in [lo, left) and
             * pivot < all in [left, start), so pivot belongs at left.  Note
             * that if there are elements equal to pivot, left points to the
             * first slot after them -- that's why this sort is stable.
             * Slide elements over to make room for pivot.
             */
            int n = start - left;  // The number of elements to move
            // Switch is just an optimization for arraycopy in default case
            switch (n) {
                case 2:  a[left + 2] = a[left + 1];
                case 1:  a[left + 1] = a[left];
                         break;
                default: System.arraycopy(a, left, a, left + 1, n);
            }
            a[left] = pivot;
        }
    }

抱有钦定地方的操作都是从头开头遍历实行的

■ 关于Vector 就不详细介绍了,因为官方也并不引入应用: (JDK 1.0)

2.3 主要的函数

双向链表达成,成分时有序的,输出顺序与输入顺序一致

  1. 非线程安全的动态数组(Array进级版),协助动态扩大容积
  2. 兑现 List
    接口、底层使用数组保存全部因素,其操作基本上是对数组的操作,允许null值
  3. 达成了 RandmoAccess 接口,提供了放肆会见效果
  4. 线程安全可知Vector,实时同步
  5. 适用于访问频仍场景,频仍插入或删除场景请接纳linkedList

2.5 其它

图片 2

ArrayList 的部分认知:

2.3.2 remove()方法

删除内定地方的成分

   public E remove(int index) {
        if (index >= size)//检查下标是否合法
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        modCount++;//修改modCount
        E oldValue = (E) 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;
    }

一、List接口框架图

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

2.3.1 add方法

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

增进二个因素到集中尾巴部分,首先对数组大小进行检讨,要求扩大体积的开始展览扩大容积,然后将成分增添到尾巴部分下标所在地方,并将size加1。

private void ensureCapacityInternal(int minCapacity) {
      // 如果数组为空,则选择DEFAULT_CAPACITY与当前需要的总容量的较大者,作为扩容的参数
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //若需要的容量比数组的长度还大,则需要进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    // 新的参考容量为旧容量的1.5倍(向上取整),和hashmap的2倍不一样
    //等同于 (int)Math.floor(oldCapacity*1.5) 
    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;
    }

2、达成接口:List, Deque, Cloneable, java.io.塞里alizable

 - set() / get(): 直接操作下标指针

2.4 内部类

图片 3

ArrayList的里边类

  • 静态内部类:ArrayListSpliterator可分割的迭代器,用于互动遍历集合。(jdk1.8才有)

静态内部类的利用景况是: 1
当外界类需若是用个中类,而个中类无需外界类的财富,况且当中类能够独自创制的时候,会思考选拔静态内部类。2
里面类与外界类关系紧凑的,且不借助于外界类实例的,都得以使用静态内部类。
举例builder格局中的builder类;hashmap的static class
HashMapEntry<K,V>类。

  • private迭代器:Itr和ListItr
  • private SubList:集结的子集

2,父亲和儿子list做的非结构性修改(non-structural
changes)都会默转潜移到相互:所谓的“非结构性修改”,是指不涉及到list的高低改造的更改。相反,结构性修改,指改造了list大小的修改。

 

1.什么是ArrayList

  • 使用动态数组Object[]封存成分,允许null值
  • 达成List接口,允许利用下标操作成分
  • 非线程安全,线程安全参见Vector
  • 适用于频仍看望的景观,不合适频仍插入大概去除(参见LinkedList)
  • 扶助批量操作

图片 4

■ 遍历、排序

2.5.2 System.arrayCopy() Arrays.copyOf()的区别

1 public static native void arraycopy(Object src, int srcPos,Object
dest, int destPos, int length);
参数依次对应该为:源数组,源数组copy的前奏地点,指标数组,指标数组寄放的胚胎地方,须求copy的数主管度

2 public static <T,U> T[] copyOf(U[] original, int
newLength, Class<? extends T[]> newType)
参数依次对应该为:源数组,新数首席推行官度,新数组成分类型

事实上,
Arrays.copyOf()里面只怕通过调用System.arrayCopy()完毕最后的数组成分拷贝。所以,Arrays.copyOf()实际上是受限的System.arrayCopy()
有别于首要为:

  • 1
    System方法需求传入新的数组,Arrays方法毫无(会在中间团结新建八个数组并赶回)。
  • 2 System方法未有重回值,Arrays方法重回新的数组

三、Vector

■重要方法

2.2 重要的全局变量

能够惦念一下,要是让我们来统一筹算ArrayList,须要哪些全局变量和函数?

  • Object[] 数组,用来寄放在成分
  • size:数组瓜月素个数
  • MaxSize:数组的最大尺寸
  • add方法(考虑扩大体量),get方法,remove方法(思索减容),size()方法,isEmpty()方法

jdk的落到实处,全局变量满含:

>//Default initial capacity.
    private static final int DEFAULT_CAPACITY = 10;
//Shared empty array instance used for empty instances.
    private static final Object[] EMPTY_ELEMENTDATA = {};
// 存放元素的数组,空的ArrayList,即elementData = EMPTY_ELEMENTDATA,在添加第一个元素时,会扩容到DEFAULT_CAPACITY 。transient 标记序列化时不需要序列化该字段。
    transient Object[] elementData;
// 元素个数size
    private int size;
//父类AbstractList中的成员变量,记录集合被修改的次数,用于迭代时的异常检查(下文会详细讲解)
  protected transient int modCount = 0;

图片 5