ArrayList详解

ゝ一纸荒年。 2023-10-05 19:44 40阅读 0赞

**目录**

一、概述

1、概述

2、基于数组实现，查询快，增删慢

3、没有同步锁，多线程不安全：

4、自动扩容，使用方便

二、“查询快，增删慢”，咋办？

LinkedList：查询慢，增删快，线程不安全

三、“线程不安全”，咋办？

1、概述

2、办法一：使用Vector（不推荐）

3、办法二：Collections.synchronizedList()（不推荐）

4、办法三：CopyOnWriteArrayList比Vector（推荐）

--------------------

# 一、概述 #

## 1、概述 ##

*  基于数组实现，查询快，增删慢；
 *  没有同步锁，多线程不安全；
 *  自动扩容，使用方便；

## 2、基于数组实现，查询快，增删慢 ##

ArrayList底层基于数组实现，元素连续存储，便于随机查找和遍历操作，但是如果要在中间添加或删除一个元素，需要将后面的所有元素进行移动，因此不适合从中间添加和删除操作，这些特性来自于数组；

## 3、没有同步锁，多线程不安全： ##

线程不安全但是效率高，可在单线程中使用；

// 举例add()方法：
    	// 此方法需要几步完成，但没有同步锁，多线程不安全
    	public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

## 4、自动扩容，使用方便 ##

/**
         * 元素每次超出容量都会扩展为原来的1.5倍，每次都会复制（Arrays.copyOf()）之前的元素到新的数组
         * 效率较低，最好初始化一个较为合适的长度，减少扩容次数
         */
    	// 无参构造，赋值一个空数组，当添加第一个元素的时候初始化容量为10
        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;
            }
        }

# 二、“查询快，增删慢”，咋办？ #

### LinkedList：查询慢，增删快，线程不安全 ###

LinkedList底层基于**双向链表**实现，对其内部元素进行增加或删除时，只需要修改上一个节点和下一个节点的指向即可，改动少，效率高，适合增删，但是当进行随机访问时需要从头遍历到该元素，因此查询速度慢；同样，LinkedList多线程不安全；

# 三、“线程不安全”，咋办？ #

## 1、概述 ##

* 1、使用List<String> list = new Vector<>();，这个答案对，但是一个很笨拙的答案；（不推荐）
    * 2、让ArrayList变得安全：List<String> list = Collections.synchronizedList(new ArrayList<>());（不推荐）
    * 3、JUC的解决方案：List<String> list = new CopyOnWriteArrayList<>();

## 2、办法一：使用Vector（不推荐） ##

// 加锁了，线程安全但效率低了
    	public void add(int index, E element) {
            insertElementAt(element, index);
        }
    	public synchronized void insertElementAt(E obj, int index) {
            modCount++;
            if (index > elementCount) {
                throw new ArrayIndexOutOfBoundsException(index
                                                         + " > " + elementCount);
            }
            ensureCapacityHelper(elementCount + 1);
            System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
            elementData[index] = obj;
            elementCount++;
        }

## 3、办法二：Collections.synchronizedList()（不推荐） ##

方法加synchronized锁，效率低；

List<String> list = Collections.synchronizedList(new ArrayList<>());

## 4、办法三：CopyOnWriteArrayList比Vector（推荐） ##

Vector的add方法加了synchronized，执行效率低；CopyOnWriteArrayList的add方法用的是lock锁；

CopyOnWrite写时复制：是一种读写分离的思想；

实现思想：当我们向集合中添加一个元素时，并不直接向Object\[ \]数组中直接添加，而是将Object\[ \]数组拷贝一个新的数组，向新的数组中添加元素，最后将原数组的引用指向新的数组。这样做的好处是可以实现并发的读，且不需要加锁，这样就实现了读和写使用的是不同的容器，实现读写分离思想；

List<String> list = new CopyOnWriteArrayList<>();

public boolean add(E e) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] elements = getArray();
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len + 1);
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally {
                lock.unlock();
            }
        }