Java面试——不安全的集合类

TIP

Java 中有许多的集合，常用的有List，Set，Queue，Map。其中 List，Set，Queue都是Collection（集合），List<String>中<>的内容表示其中元素的类型，是泛型的一种使用。不能直接使用简单数据类型做泛型的原因：集合类（比如Set）在进行各种 "操作" ( 如contains()) 时都会调用元素本身提供的 "方法" ( 如hashCode() 和 equals())，而不是由集合类自身去实现这些 "方法"。这就要求如果某人想要用这个集合执行某些 "操作"，那就必须在要加入集合的元素中实现相应的 "方法"。

fail-fast 机制是 java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast事件。例如：当某一个线程A通过 iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生 fail-fast事件。

# 一、ArrayList 不安全阐述

List（列表）相当于数组。长度可变，元素存放有一定的顺序，下标从0开始。在JDK中，List作为接口，本身已经声明好了所有的方法（比如add(), contains()......），所以不管是选择 ArrayList还是 LinkedList，完成各种操作的时候依然是使用 List中已经声明过的这一套方法，对使用者来说没有区别。二者只是内部实现逻辑不同，所以在不同的应用场景下会有不同的效率。

【1】ArrayList<> 底层通过数组实现数据的存储。初始的大小为10，超过默认值时，通过 Arrays 进行扩容，如下：允许存空元素，有专门保存容量的 capacity属性

//elementData 需要扩容的数组对象 ， newCapacity 扩容的大小 int 类型
elementData = Arrays.copyOf(elementData, newCapacity);

1
2

【2】ArrayList 线程不安全的例子如下：

public class Test {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i=1;i<3000;i++){
            new Thread(){
                @Override
                public void run(){
                    list.add(UUID.randomUUID().toString().substring(0,7));
                    System.out.println(list);
                }
            }.start();
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

【3】故障现象：java.util.ConcurrentModificationException

【4】导致原因：因并发无锁导致数据修改异常。

【5】解决方案：
① Vector 是线程安全的，可以解决上面的问题。但是性能会急剧下降（不建议使用）。
② 使用Collections工具类 Collections.synchronizedList(new ArrayList<>()); 解决上述问题。
③ new CopyOnWriteArrayList<>()：写时复制，CopeOnWrite 容器既写时复制的容器。往一个容器添加元素的时候，不直接往当前容器 Object[] 添加，而是先将当前容器 object[] 进行 copy，复制出一个新的容器 Object[] newElements，然后往新的容器中添加元素，添加完元素之后，再将原容器的引用指向新容器 setArray(newElements); 这样做的好处是可以对 CopeOnWrite 容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以 CopeOnWrite 容器也是一种读写分离的思想，读和写不同的容器。底层源码如下：

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();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 扩展一：Arrays.asList 遇到的问题

使用Arrays.asList()方法时把一个数组转化成 List列表，对得到的 List列表进行 add()和 remove()操作, 会导致 java.lang.UnsupportedOperationException异常。

【1】查看 Arrays.asList 源码

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

1
2
3

【2】查看此 ArrayList结构：add 和 remove 方法继承自 AbstractList

private static class ArrayList<E> extends AbstractList<E> {
        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }
}

1
2
3
4
5

【3】在查看 AbstractList结构：add 和 remove 方法直接返回 UnSupportedOperationException

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {

    public boolean add(E e) {
        add(size(), e);
        return true;
    }

    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

   public E remove(int index) {
        throw new UnsupportedOperationException();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

所以说 Arrays.asList 返回的 List 是一个不可变长度的列表，此列表不再具备原 List 的很多特性，因此慎用 Arrays.asList 方法。

下面代码输出是什么？

public static void main(String[] args) {
    int[] data = {1,2,3,4};
    List list = Arrays.asList(data);
    System.out.println(list.size());
}

1
2
3
4
5

由上面 asList 源码我们可以看到返回的 Arrays的内部类 ArrayList 构造方法接收的是一个类型为 T 的数组，而基本类型是不能作为泛型参数的，所以这里参数 a只能接收引用类型，自然为了编译通过编译器就把上面的 int[] 数组当做了一个引用参数，所以 size 为 1，要想修改这个问题很简单，将 int[] 换成 Integer[] 即可。所以原始类型不能作为 Arrays.asList 方法的参数，否则会被当做一个参数。

# 扩展二：ArrayList 的 subList的注意事项

《阿里巴巴Java开发手册》泰山版中是这样描述的：

使用起来很简单，也很好理解，不过还是有以下几点要注意，否则会造成程序错误或者异常：
【1】修改原集合元素的值，会影响子集合；
【2】修改原集合的结构，会引起 ConcurrentModificationException异常；

看下它的源码：

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

1
2
3
4

可以看到，它调用了 SubList类的构造函数，该构造函数的源码如下图所示：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        ......
    private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;

        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }
......

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以看出，SubList类是 ArrayList的内部类，该构造函数中也并没有重新创建一个新的 ArrayList，所以修改原集合或者子集合的元素的值，是会相互影响的。

# 二、Set 不安全阐述

Set 与 List 是相同的，都是线程不安全的，都会出现 ConcurrentModificationException 异常，解决办法常见的有两种：

【1】Collections.synchronizedSet(new HashSet<>()); 通过工具类中的同步代码块可以解决此问题，但性能会受影响。

【2】new CopyOnWriteArraySet<>() 和 List 相同，通过写时复制即可高效解决此问题。底层通过 CopyOnWriteArrayList 实现：

public CopyOnWriteArraySet() {
    al = new CopyOnWriteArrayList<E>();
}

1
2
3

扩展： hashSet 的底层是怎么实现的：底层其实是一个 hashMap，源代码如下：

public HashSet() {
    map = new HashMap<>();
}

1
2
3

我们的疑惑是，Map 不应该存放的是两个值么，而 Set 存储的都是一个值呀，其实是因为 Map 中的 Key 与 Set 具有相同的特性。因此 Set 的值都存储在 Map 中的 key 中，而 value 存储一个固定的 Object 常量。源代码如下：

//存储的 value 值
private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

1
2
3
4
5

# 三、Map 不安全阐述

Map 与 List/Set 是相同的，都是线程不安全的，都会出现 ConcurrentModificationException 异常，解决办法常见的有三种：

【1】Collections.synchronizedMap(new HashMap<>()); 通过工具类中的同步代码块可以解决此问题，但性能会受影响。

【2】HashTable： HashTable 容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。

【3】new ConcurrentHashMap<>(); 推荐使用，此方法创建的 Map 是线程安全的。而 JDK1.7 之前的 ConcurrentHashMap 使用分段锁机制实现，JDK1.8 则使用数组+链表+红黑树数据结构和CAS原子操作实现 ConcurrentHashMap；

具体可以查看：连接

← Java面试——写一个生产者与消费者 Java面试——搜索 →