首页 > 其他分享 >ArrayList

ArrayList

时间:2023-10-30 15:58:45浏览次数:36  
标签:java ArrayList list util add minCapacity

概述

  Resizable-array implementation of the <tt>List</tt> interface.  可变大小的数组(实现了List接口);

  Implements all optional list operations, and permits all elements, including null.  实现了List的所有操作,允许所有的元素(包括null);

  

  <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>, <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant time.  

    size、isEmpty、get、set、iterator、listIterator操作需要 O(1)时间;

  The <tt>add</tt> operation runs in <i>amortized constant time</i>, that is, adding n elements requires O(n) time.  

    add操作 添加n个元素,需要O(n);

  

  <p>An application can increase the capacity of an<tt>ArrayList</tt> instance before adding a large number of elements using the <tt>ensureCapacity</tt> operation.  

    在添加大数量的元素前,会使用ensureCapacity确保ArrayList容量;

 

  Note that this implementation is not synchronized.  ArrayList的实现是非同步的;

  If multiple threads access an <tt>ArrayList</tt> instance concurrently, and at least one of the threads modifies the list structurally, it <i>must</i> be synchronized externally.

    如果多个线程并发访问ArrayList,必须在外部进行同步;

 

  A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.  

    结构修改:添加、删除元素、数组重置大小;  (多于多线程并发 需要进行同步操作)

  If no such object exists, the list should be "wrapped" using the {@link Collections#synchronizedList Collections.synchronizedList} method.  

    可以使用 Collections.synchronizedList 实现同步;

 

  The iterators returned by this class's {@link #iterator() iterator} and {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:

    iterator、listIterator 方法是fail-fast;    
  if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own {@link ListIterator#remove() remove}

  or {@linkListIterator#add(Object) add} methods, the iterator will throw a {@link ConcurrentModificationException}.

    如果创建了iterator,调用iterator的remove、add将会抛出ConcurrentModificationException(实际用的是子类的java.util.ArrayList.Itr)

链路

add

// java.util.ArrayList.add(E)
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    // java.util.ArrayList.ensureCapacityInternal
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    // java.util.ArrayList.calculateCapacity
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    // java.util.ArrayList.ensureExplicitCapacity
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;                                                     // modCount递增

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)                       // 容量不足,扩容
            grow(minCapacity);
    }
    
    // java.util.ArrayList.grow
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);             // 新容量 = 旧容量 + 旧容量/2
        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);          // 将元素旧数据 copy到 新数组中
    }

  

 

同步ArrayList(Collections.synchronizedList(new ArrayList<>());)

链路

add(E e)

// java.util.Collections.synchronizedList(java.util.List<T>)
    public static <T> List<T> synchronizedList(List<T> list) {
        return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<>(list) :          // ArrayList实现了RandomAccess
                new SynchronizedList<>(list));
    }

    // java.util.Collections.SynchronizedRandomAccessList.SynchronizedRandomAccessList(java.util.List<E>)
    SynchronizedRandomAccessList(List<E> list) {
        super(list);
    }

    // java.util.Collections.SynchronizedList.SynchronizedList(java.util.List<E>)
    SynchronizedList(List<E> list) {
        super(list);
        this.list = list;
    }
    
    // java.util.Collections.SynchronizedCollection.add             // SynchronizedRandomAccessList继承了SynchronizedList,SynchronizedList继承了SynchronizedCollection,调用的是SynchronizedCollection的add
    public boolean add(E e) {
        synchronized (mutex) {return c.add(e);}
    }

  

 

 

  

  

   

标签:java,ArrayList,list,util,add,minCapacity
From: https://www.cnblogs.com/anpeiyong/p/17798046.html

相关文章

  • 06ArrayList源码分析
    ArrayList一、ArrayList集合的底层原理--扩容机制利用空参创建的集合,在底层创建一个默认长度为零的一个数组。添加第一个元素时,底层会创建一个新的长度为10的数组。存满时候,会扩容1.5倍。如果一次添加多个元素,1.5倍放不下,则创建数组的长度以实际为准。如:添加100......
  • 用HashMap创建jString,ArrayList的键值对用entrySet遍历
    用HashMap创建jString,ArrayList的键值对用entrySet遍历package随机点名器;importjava.util.*;publicclassTest1{publicstaticvoidmain(String[]args){HashMap<String,ArrayList<String>>m=newHashMap<>();ArrayList<String>......
  • 学习一下Java的ArrayList和contains函数和扩容机制
    起因在Leetcode上做题写了两种暴力解法,但是执行效率上不太一样。时间上差很远,内存虽然差不多但是前者击败30%,后者击败94%。这两种解法区别是用一条ArrayList还是两条来存数据,所以contains虽然执行次数一样但是检测的长度上不一样,而且ArrayList的扩容次数也不一样,所以学习一下。......
  • 将数组转换为ArrayList
    内容来自DOChttps://q.houxu6.top/?s=将数组转换为ArrayList给定一个类型为Element[]的数组:Element[]array={newElement(1),newElement(2),newElement(3)};如何将这个数组转换为类型为ArrayList<Element>的对象?ArrayList<Element>arrayList=???;将数组转......
  • hashmap,arrayList,concurrentHashMap扩容机制
    HashMap1.7和1.8扩容机制在Java1.7中,HashMap的扩容机制是当容量超过负载因子与数组长度的乘积时就会进行扩容。默认负载因子为0.75,即当数组长度为n时,当元素个数size超过n*0.75时就会扩容。扩容时,数组长度会变为原来的2倍,并且将原来的元素重新计算哈希值,再散列到新......
  • arraylist扩容原理
    ArrayList是Java中的动态数组,其扩容原理是在元素数量超过当前数组容量时,创建一个更大容量的新数组,并将所有元素从旧数组复制到新数组。下面是ArrayList扩容的基本原理:初始容量:当你创建一个ArrayList对象时,它会有一个初始容量,通常为10。这个容量可以根据需要进行调整。元素添加:当你......
  • ArrayList线程安全问题分析
    测试代码:importjava.util.ArrayList;publicclassTestThreadSafe{staticfinalintLOOP_NUM=10;publicstaticvoidmain(String[]args)throwsInterruptedException{ThreadSafeSubClasstest=newThreadSafeSubClass();test.method1(......
  • 循环增删 ArrayList ,小心有坑
    编程过程中常常需要使用到集合,比如:ArrayList,当我们在for循环增删的时候,一不小心就会踩坑。如下代码List<String>arrayList1=newArrayList<String>();arrayList1.add("1");arrayList1.add("2");for(Strings:arrayList1){if("1".equals(s)){......
  • ArrayList 介绍
       ......
  • ArrayList的线程安全问题简述,以及如何优化
    问题:创建一个ArrayList,然后创建两个线程,每个线程for循环1000次向公共的List里面添加数据,在一个线程读取List当前的大小之后,另一个线程可能已经对List进行了修改。这样就可能导致数据的不一致性,例如一个线程读取到的List大小已经被另一个线程修改了,因此,在这个案例中,最终的列表大小......