首页 > 其他分享 >ArrayList

ArrayList

时间:2023-11-10 11:48:57浏览次数:44  
标签:index 遍历 int ArrayList elementData list

ArrayList的底层是动态数组,它的容量能动态增长。

索引存取元素,有序,可重复,允许多个null

1、ArrayList初始容量

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData;

// 无参构造器,初始化为空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 传入初始容量,根据容量初始化
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);
    }
}
// 根据传入集合做初始化,若集合为空,则为空,还要对得到的数组判断是否为对象数组类型
public ArrayList(Collection<? extends E> 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;
    }
}

2、扩容

ArrayList扩容的本质就是计算出新的扩容数组的size后实例化,并将原有数组内容复制到新数组中去。默认情况下,新的容量会是原容量的1.5倍

// list结构变化的次数(影响迭代器)
protected transient int modCount = 0; 
// 一些JVM需要保存数组头信息,申请更大的数组可能会OOM
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

// 第一次添加元素,size=0
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保容量足够
    elementData[size++] = e; // 末尾插入元素
    return true;
}
// 对容量判断,不足则扩容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 若使用无参构造器初始化,则容量为默认10和需要的最小容量之间的最大值(第一次添加变为10)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity; // 若使用带参构造器初始化,不管是否为空,都取需要的最小容量,即第一次添加为1
}

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);  // 1.5倍
    if (newCapacity - minCapacity < 0) // 1.5倍不够,则取需要的最小容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 最大的数组容量不满足,最大可取Integer.MAX_VALUE
        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;
}

3、删除元素

安全的删除元素:使用迭代器

使用for删除,会导致ConcurrentModificationException

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("1111");
        list.add("2222");
        list.add("3333");
        list.add("4444");
        list.add("5555");

        for (String str : list){
            if (str == "2222"){
                list.remove(str);
            }
        }

        for (String str : list){
            System.out.println(str);
        }
    }
}
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at file.Test.main(Test.java:15)

Process finished with exit code 1

反编译后代码为

import java.util.ArrayList;
import java.util.Iterator;

public class Test {
   public static void main(String[] var0) {
      ArrayList var1 = new ArrayList();
      var1.add("1111");
      var1.add("2222");
      var1.add("3333");
      var1.add("4444");
      var1.add("5555");
      Iterator var2 = var1.iterator();

      String var3;
      while(var2.hasNext()) {
         var3 = (String)var2.next();
         if(var3 == "2222") {
            var1.remove(var3); // 迭代器中调用了list的remove方法
         }
      }

      var2 = var1.iterator();
      while(var2.hasNext()) {
         var3 = (String)var2.next();
         System.out.println(var3);
      }
   }
}

ArrayList的remove方法:

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
}

迭代器的变动次数modCount

 private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;  // 初始化时为当前list的变动次数

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification(); // 先判断modCount
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
     
     	final void checkForComodification() {
            if (modCount != expectedModCount)  // list调用remove后已经加1,不一致
                throw new ConcurrentModificationException();
        }
     // ...
 }

4、迭代器

Iterator

Iterator模式用同一种逻辑来遍历集合。它可以把访问逻辑从不同类型的集合类中抽象出来,不需要了解集合内部实现便可以遍历集合元素,统一使用 Iterator 提供的接口去遍历。它的特点是更加安全,因为它可以保证,在当前遍历的集合元素被更改的时候,就会抛出 ConcurrentModificationException 异常

主要有三个方法:hasNext()、next()和remove()

**ListIterator **

ListIterator 是 Iterator的增强版。

  • ListIterator遍历可以是逆向的,因为有previous()和hasPrevious()方法,而Iterator不可以。
  • ListIterator有add()方法,可以向List添加对象,而Iterator却不能。
  • ListIterator可以定位当前的索引位置,因为有nextIndex()和previousIndex()方法,而Iterator不可以。
  • ListIterator可以实现对象的修改,set()方法可以实现。Iierator仅能遍历,不能修改。
  • ListIterator只能用于遍历List及其子类,Iterator可用来遍历所有集合

5、fail fast

fast-fail是Java集合的一种错误机制。当多个线程对同一个集合进行操作时,就有可能会产生fast-fail事件。例如:当线程a正通过iterator遍历集合时,另一个线程b修改了集合的内容,此时modCount(记录集合操作过程的修改次数)会加1,不等于expectedModCount,那么线程a访问集合的时候,就会抛出ConcurrentModificationException,产生fast-fail事件。边遍历边修改集合也会产生fast-fail事件(上面例子)。

解决方法:

  • 使用Colletions.synchronizedList方法或在修改集合内容的地方加上synchronized。这样的话,增删集合内容的同步锁会阻塞遍历操作,影响性能。
  • 使用CopyOnWriteArrayList来替换ArrayList。在对CopyOnWriteArrayList进行修改操作的时候,会拷贝一个新的数组,对新的数组进行操作,操作完成后再把引用移到新的数组(每写一个就要复制一次,很耗时,推荐读多写少的场景)

6、CopyOnWrite

Copy-On-Write,写时复制。当我们往容器添加元素时,不直接往容器添加,而是先将当前容器进行复制,复制出一个新的容器,然后往新的容器添加元素,添加完元素之后,再将原容器的引用指向新容器。这样做的好处就是可以对CopyOnWrite容器进行并发的读而不需要加锁,因为当前容器不会被修改

缺点:

  • 内存占用问题。由于CopyOnWrite的写时复制机制,在进行写操作的时候,内存里会同时驻扎两个对象的内存。
  • CopyOnWrite容器不能保证数据的实时一致性,可能读取到旧数据。

CopyOnWriteArrayList

CopyOnWriteArrayList中add方法添加的时候是需要加锁的,保证同步,避免了多线程写的时候复制出多个副本。读的时候不需要加锁,如果读的时候有其他线程正在向CopyOnWriteArrayList添加数据,还是可以读到旧的数据。

CopyOnWrite并发容器用于读多写少的并发场景。

优点

读操作性能很高,因为无需任何同步措施,比较适用于读多写少的并发场景。Java的list在遍历时,若中途有别的线程对list容器进行修改,则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想,遍历和修改操作分别作用在不同的list容器,所以在使用迭代器进行遍历时候,也就不会抛出ConcurrentModificationException异常了。

缺点

一是内存占用问题,毕竟每次执行写操作都要将原容器拷贝一份,数据量大时,对内存压力较大,可能会引起频繁GC;

二是无法保证实时性,Vector对于读写操作均加锁同步,可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因,写和读分别作用在新老不同容器上,在写操作执行过程中,读不会阻塞但读取到的却是老容器的数据

7、fail safe

采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。

原理:由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发Concurrent Modification Exception。

缺点:基于拷贝内容的优点是避免了Concurrent Modification Exception,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的

8、让集合不能被修改

Collections包下的unmodifiableMap/unmodifiableList/unmodifiableSet方法,通过这个方法返回的集合,是不可以修改的。如果修改的话,会抛出 java.lang.UnsupportedOperationException异常

List<String> list = new ArrayList<>();
list.add("1111");
list.add("2222");

List list1 = Collections.unmodifiableList(list);

list1.remove(1);

报错:
    Exception in thread "main" java.lang.UnsupportedOperationException
	at java.util.Collections$UnmodifiableList.remove(Collections.java:1319)
	at file.Test.main(Test.java:18)
public static <T> List<T> unmodifiableList(List<? extends T> list) {
    return (list instanceof RandomAccess ?
            new UnmodifiableRandomAccessList<>(list) :
            new UnmodifiableList<>(list));
}

9、ArrayList、Vector、LinkedList

ArrayList与Vector:

  • ArrayList在内存不够时扩容为原来的1.5倍,Vector是扩容为原来的2倍。

  • Vector属于线程安全级别的,但是大多数情况下不使用Vector,因为操作Vector效率比较低。

ArrayList与LinkedList:

  • ArrayList基于动态数组实现,LinkedList基于链表实现
  • 对于随机index访问的get和set方法,ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素;LinkedList要移动指针遍历每个元素直到找到为止
  • 新增和删除元素,LinkedList的速度要优于ArrayList。因为ArrayList在新增和删除元素时,可能扩容和复制数组;LinkedList实例化对象需要时间外,只需要修改指针即可

10、ArrayDeque

ArrayDeque实现了双端队列,内部使用循环数组实现,默认大小为16。它的特点有:

  1. 在两端添加、删除元素的效率较高
  2. 根据元素内容查找和删除的效率比较低。
  3. 没有索引位置的概念,不能根据索引位置进行操作。

ArrayDeque和LinkedList都实现了Deque接口,如果只需要从两端进行操作,ArrayDeque效率更高一些。如果同时需要根据索引位置进行操作,或者经常需要在中间进行插入和删除(LinkedList有相应的 api,如add(int index, E e)),则应该选LinkedList。

ArrayDeque和LinkedList都是线程不安全的,可以使用Collections工具类中synchronizedXxx()转换成线程同步

11、ConcurrentLinkedQueue

非阻塞队列。高效的并发队列,使用链表实现。可以看做一个线程安全的 LinkedList,通过 CAS 操作实现。

如果对队列加锁的成本较高则适合使用无锁的 ConcurrentLinkedQueue 来替代。适合在对性能要求相对较高,同时有多个线程对队列进行读写的场景

对于非阻塞队列,一般情况下建议使用offer(插入队尾)、poll(获取并移除队头)和peek(获取队头)三个方法,不建议使用add和remove方法。因为使用offer、poll和peek三个方法可以通过返回值判断操作成功与否,而使用add和remove方法却不能达到这样的效果(失败抛异常)

12、阻塞队列

阻塞队列是java.util.concurrent包下重要的数据结构,BlockingQueue提供了线程安全的队列访问方式:当阻塞队列进行插入数据时,如果队列已满,线程将会阻塞等待直到队列非满;从阻塞队列取数据时,如果队列已空,线程将会阻塞等待直到队列非空。并发包下很多高级同步类的实现都是基于BlockingQueue实现的。BlockingQueue 适合用于作为数据共享的通道。

使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队和出队用不同的锁)等方式来实现。

阻塞队列和一般的队列的区别就在于:

  • 多线程支持,多个线程可以安全的访问队列

  • 阻塞操作,当队列为空的时候,消费线程会阻塞等待队列不为空;当队列满了的时候,生产线程就会阻塞直到队列不满

标签:index,遍历,int,ArrayList,elementData,list
From: https://www.cnblogs.com/datamining-bio/p/17823718.html

相关文章

  • 线程安全集合(JDK1.5之前和之后)、CopyOnWriteArrayList、CopyOnWriteArraySet
    JDK1.5之前JDK1.5之前:Collections.synchronizedList JDK1.5之后CopyOnWriteArrayList   CopyOnWriteArraySet    ......
  • ArrayList的contains()方法的性能问题及优化方法
    背景今天定位一个接口耗时问题,通过日志定位到在数据库查询完毕后,中间一段逻辑耗时很长有十几秒的样子,发现是循环中使用ArraysList中的contains方法,当循环数量级变得很大时,执行时间变得不可控。代码示例//有5万个门店List<Store>storeList=storeMapper.se......
  • 详解Java ArrayList
    ArrayList简介ArrayList是List接口的实现类,底层基于数组实现,容量可根据需要动态增加,相当于动态数组。ArrayList继承于AbstractList,并且还实现了Cloneable、Serializable、RandomAccess接口。List:表明是列表数据结构,可以通过下标对元素进行添加删除或查找。Serializable:表示可......
  • JUC高并发容器-CopyOnWriteArrayList
    CopyOnWriteArrayListJUC高并发容器线程安全的同步容器类什么是高并发容器?CopyOnWriteArrayListJUC高并发容器线程安全的同步容器类  Java同步容器类通过Synchronized(内置锁)来实现同步的容器,比如Vector、HashTable以及SynchronizedList等容器。线程安全的同步容器类主要有Vec......
  • ArrayList
    概述Resizable-arrayimplementationofthe<tt>List</tt>interface.可变大小的数组(实现了List接口);Implementsalloptionallistoperations,andpermitsallelements,includingnull.实现了List的所有操作,允许所有的元素(包括null);<p>The<tt>si......
  • 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倍,并且将原来的元素重新计算哈希值,再散列到新......