JAVA中的集合类

445 07-15

ArrayList

ArrayList 线程不安全的案例

当 new 一个 ArrayList 时，底层是一数组

ArrayList arrayList = new ArrayList<>();

构建了一个初始容量为 10 的空 List

ArrayList.java

package java.util;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

		/**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

如果容量不够就进行扩容(再增加原值的一半的容量)，然后将之前的数据拷贝到新的数组中

ArrayList.java

package java.util;

		private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

  /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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);
    }

ArrayList 线程不安全

ArrayList.java 的 add 方法并没有加锁

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return true (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

例子：

java.util.ConcurrentModificationException 异常

package pers.codingfanlt.arraylist;

import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

public class ArrayListDemo {

    public static void main(String[] args) {

        List list = new ArrayList<>();

        // 30 个线程同时操作一个 ArrayList，将出现 java.util.ConcurrentModificationException 异常
        for (int i = 0; i < 30; i++) {
            new Thread(() -> {
                list.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(list);
            }, String.valueOf(i)).start();
        }
    }
}

执行结果：

[2ab8adfa, e427f069, eec43eec, 344cca39]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d]
[2ab8adfa, e427f069, eec43eec, 344cca39]
[2ab8adfa, e427f069, eec43eec, 344cca39]
[2ab8adfa, e427f069, eec43eec, 344cca39]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c, 367246b8, d83aff80]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c, 367246b8, d83aff80, 7f43d424]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c, 367246b8, d83aff80, 7f43d424, 3519cb55, 45fd86b8, 911bf126]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c, 367246b8, d83aff80, 7f43d424, 3519cb55]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c, 367246b8, d83aff80, 7f43d424, 3519cb55, 45fd86b8, 911bf126, daccc65a]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c, 367246b8, d83aff80, 7f43d424, 3519cb55, 45fd86b8, 911bf126, daccc65a, 8ea895f3]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c, 367246b8, d83aff80, 7f43d424, 3519cb55, 45fd86b8, 911bf126, daccc65a, 8ea895f3, 8ba51452]
[2ab8adfa, e427f069, eec43eec, 344cca39, 28d11c4d, d9c3ab1f, c21173fa, 11c992fe, d32732c5, 96d72751, c7027c49, e19c61df, bc4e782d, 04ae6336, becb5b94, 9d107985, 6f2f7b72, e34d676c, 367246b8, d83aff80, 7f43d424, 3519cb55, 45fd86b8, 911bf126, daccc65a, 8ea895f3, 8ba51452, 1f334071, 599f54ef, 7bb23384]
Exception in thread "17" Exception in thread "15" Exception in thread "19" Exception in thread "27" Exception in thread "0" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)
	at java.lang.String.valueOf(String.java:2994)
	at java.io.PrintStream.println(PrintStream.java:821)
	at pers.codingfanlt.arraylist.ArrayListDemo.lambda$main$0(ArrayListDemo.java:22)
	at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)
	at java.lang.String.valueOf(String.java:2994)
	at java.io.PrintStream.println(PrintStream.java:821)
	at pers.codingfanlt.arraylist.ArrayListDemo.lambda$main$0(ArrayListDemo.java:22)
	at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)
	at java.lang.String.valueOf(String.java:2994)
	at java.io.PrintStream.println(PrintStream.java:821)
	at pers.codingfanlt.arraylist.ArrayListDemo.lambda$main$0(ArrayListDemo.java:22)
	at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)
	at java.lang.String.valueOf(String.java:2994)
	at java.io.PrintStream.println(PrintStream.java:821)
	at pers.codingfanlt.arraylist.ArrayListDemo.lambda$main$0(ArrayListDemo.java:22)
	at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)
	at java.lang.String.valueOf(String.java:2994)
	at java.io.PrintStream.println(PrintStream.java:821)
	at pers.codingfanlt.arraylist.ArrayListDemo.lambda$main$0(ArrayListDemo.java:22)
	at java.lang.Thread.run(Thread.java:748)

Process finished with exit code 0

原因

并发争抢修改导致

一个线程正在写，另一个线程争抢，导致数据不一致，并发修改异常

~~方法没有加锁~~

解决方案（优化建议）：

使用 Vector 类代替 ArrayList （并发性低）

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

使用 Collections 辅助工具类

java.util.Collections

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

使用 CopyOnWriteArrayList

java.util.concurrent.CopyOnWriteArrayList;

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

CopyOnWriteArrayList 使用了写时复制技术（读写分离的思想）

CopyOnWriteArrayList.java 底层代码：

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    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();
        }
    }

　在向 List 中新增时使用了写时复制技术

Collection 是一个接口

Collections 是一个类

HashSet

底层数据结构：HashMap

初始容量为 16 负载因子为 0.75

package java.util;

		/**
     * Constructs a new, empty set; the backing HashMap instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

HashMap 使用 key-value 存储，HashSet 只有一个参数（key），value 为名为 PRESENT 的 Object类型常量（Value 是恒定的）

原因：

 package java.util;

		// Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

		/**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element e to this set if
     * this set contains no element e2 such that
     * (e==null ? e2==null : e.equals(e2)).
     * If this set already contains the element, the call leaves the set
     * unchanged and returns false.
     *
     * @param e element to be added to this set
     * @return true if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

HashSet 线程不安全

例子：

package pers.codingfanlt.hashset;

import java.util.HashSet;
import java.util.Set;
import java.util.UUID;

public class HashSetDemo {
    public static void main(String[] args) {
        Set set = new HashSet<>();

        // 30 个线程同时操作一个 HashSet，将出现 java.util.ConcurrentModificationException 异常
        for (int i = 0; i < 30; i++) {
            new Thread(() -> {
                set.add(UUID.randomUUID().toString().substring(0, 8));
                System.out.println(set);
            }, String.valueOf(i)).start();
        }
    }
}

执行结果：

[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 3053cc3e, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, 5e032bf8, a3ca1f01, 3053cc3e, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, 5e032bf8, a3ca1f01, 3053cc3e, 9f718fb9, 8ea6f14e, b3243de5, 1174b7f5, 7b0edf4f]
[d0892cf0, 32491403, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 41f60e72, b1f26f4b, 563845f4, 5e032bf8, 3053cc3e, 8ea6f14e, 7b0edf4f]
[f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 41f60e72, b1f26f4b, 563845f4, 5e032bf8, 3053cc3e, 8ea6f14e, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, d5bfaa2f, 1174b7f5, 1c1e4a0d, 41f60e72, b1f26f4b, 563845f4, 5e032bf8, 3053cc3e, 6ffb368e, 8ea6f14e, 7b0edf4f, bddf73cc]
[f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, d5bfaa2f, 1174b7f5, 1c1e4a0d, 41f60e72, b1f26f4b, 563845f4, 5e032bf8, 3053cc3e, 8ea6f14e, 7b0edf4f, bddf73cc]
[f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, d5bfaa2f, 1174b7f5, 1c1e4a0d, 41f60e72, b1f26f4b, b5edb57b, 563845f4, 5e032bf8, 3053cc3e, c1f67dc7, 6ffb368e, 8ea6f14e, 7b0edf4f, bddf73cc]
[f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, d5bfaa2f, 1174b7f5, 1c1e4a0d, 41f60e72, b1f26f4b, 563845f4, 5e032bf8, 3053cc3e, 8ea6f14e, 7b0edf4f]
[f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, d5bfaa2f, 1174b7f5, 1c1e4a0d, 41f60e72, b1f26f4b, b5edb57b, 563845f4, 5e032bf8, 3053cc3e, c1f67dc7, ad504183, 6ffb368e, 8ea6f14e, 7b0edf4f, bddf73cc]
[71682659, f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, d5bfaa2f, 1174b7f5, 1c1e4a0d, 41f60e72, b1f26f4b, b5edb57b, 563845f4, 5e032bf8, 3053cc3e, c1f67dc7, ad504183, 6ffb368e, 8ea6f14e, 7b0edf4f, bddf73cc]Exception in thread "20" 
[f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, d5bfaa2f, 1174b7f5, 41f60e72, b1f26f4b, 563845f4, 5e032bf8, 3053cc3e, 8ea6f14e, 7b0edf4f]
[71682659, 32491403, b3243de5, d5bfaa2f, b1f26f4b, 5e032bf8, 26f6df67, 3053cc3e, ad504183, 21c77e69, 8ea6f14e, 7b0edf4f, f8daf983, d0892cf0, 05697225, 2381ec1f, a3ca1f01, 9f718fb9, 1174b7f5, 1c1e4a0d, 41f60e72, b5edb57b, 563845f4, c1f67dc7, 6ffb368e, bddf73cc]
Exception in thread "27" [71682659, 32491403, b3243de5, d5bfaa2f, b1f26f4b, 5e032bf8, 26f6df67, 3053cc3e, ad504183, 21c77e69, 8ea6f14e, 7b0edf4f, f8daf983, d0892cf0, 05697225, 2381ec1f, a3ca1f01, 9f718fb9, 1174b7f5, f7038a4e, 1c1e4a0d, 41f60e72, b5edb57b, 563845f4, c1f67dc7, 6ffb368e, bddf73cc]
[71682659, 32491403, b3243de5, d5bfaa2f, b1f26f4b, 5e032bf8, 26f6df67, 98604e8b, 3053cc3e, ad504183, 21c77e69, 8ea6f14e, 7b0edf4f, f8daf983, d0892cf0, 05697225, 2381ec1f, a3ca1f01, 9f718fb9, 1174b7f5, f7038a4e, 1c1e4a0d, 41f60e72, b5edb57b, 563845f4, c1f67dc7, 6ffb368e, bddf73cc]
[d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 41f60e72, b1f26f4b, 563845f4, 5e032bf8, 3053cc3e, 8ea6f14e, 7b0edf4f]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[71682659, 32491403, b3243de5, d5bfaa2f, b1f26f4b, 5e032bf8, 26f6df67, 98604e8b, 3053cc3e, ad504183, 21c77e69, 8ea6f14e, 7b0edf4f, f8daf983, d0892cf0, 05697225, 2381ec1f, a3ca1f01, 9f718fb9, 1174b7f5, f7038a4e, 1c1e4a0d, 41f60e72, b5edb57b, 563845f4, c1f67dc7, 91416abf, 6ffb368e, bddf73cc]
[41f60e72, d0892cf0, 32491403, 563845f4, a3ca1f01, 9f718fb9, b3243de5, 1174b7f5, 7b0edf4f]
[71682659, f8daf983, d0892cf0, 32491403, 2381ec1f, a3ca1f01, 9f718fb9, b3243de5, d5bfaa2f, 1174b7f5, 1c1e4a0d, 41f60e72, b1f26f4b, b5edb57b, 563845f4, 5e032bf8, 26f6df67, 3053cc3e, c1f67dc7, ad504183, 6ffb368e, 8ea6f14e, 7b0edf4f, bddf73cc]
java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)[71682659, 32491403, b3243de5, d5bfaa2f, b1f26f4b, 5e032bf8, 26f6df67, 98604e8b, 3053cc3e, ad504183, 21c77e69, 8ea6f14e, 7b0edf4f, d184ccd9, f8daf983, d0892cf0, 05697225, 2381ec1f, a3ca1f01, 9f718fb9, 1174b7f5, f7038a4e, 1c1e4a0d, 41f60e72, b5edb57b, 563845f4, c1f67dc7, 91416abf, 6ffb368e, bddf73cc]
	at java.util.HashMap$KeyIterator.next(HashMap.java:1469)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)

	at java.lang.String.valueOf(String.java:2994)
	at java.io.PrintStream.println(PrintStream.java:821)
	at pers.codingfanlt.hashset.HashSetDemo.lambda$main$0(HashSetDemo.java:15)
	at java.lang.Thread.run(Thread.java:748)
java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)
	at java.util.HashMap$KeyIterator.next(HashMap.java:1469)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)
	at java.lang.String.valueOf(String.java:2994)
	at java.io.PrintStream.println(PrintStream.java:821)
	at pers.codingfanlt.hashset.HashSetDemo.lambda$main$0(HashSetDemo.java:15)
	at java.lang.Thread.run(Thread.java:748)

Process finished with exit code 0

解决

使用 Collections

Set<String> set = Collections.synchronizedSet(new HashSet<>());

使用 CopyOnWriteArraySet

Set<String> set = new CopyOnWriteArraySet();

CopyOnWriteArraySet 底层还是一个 CopyOnWriteArrayList

package java.util.concurrent;

		/**
     * Creates an empty set.
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList();
    }

HashMap

HashMap 线程不安全

例子：

package pers.codingfanlt.map;

import java.util.HashMap;
import java.util.Map;
import java.util.UUID;

public class MapDemo {
    public static void main(String[] args) {
        Map map = new HashMap<>();
        // 30 个线程同时操作一个 HashMap，将出现 java.util.ConcurrentModificationException 异常
        for (int i = 0; i < 30; i++) {
            new Thread(() -> {
                map.put(Thread.currentThread().getName(), UUID.randomUUID().toString().substring(0, 8));
                System.out.println(map);
            }, String.valueOf(i)).start();
        }
    }
}

执行结果：

解决

使用 Collections

Map<String, String> map = Collections.synchronizedMap(new HashMap<>());

使用 ConcurrentHashMap

Map<String, String> map = new ConcurrentHashMap<>();

java开发实习工程师http://www.gtalent.cn/exam/interview/jdAgwJtErNal1znK

标签： JAVA JAVA上机题