List容器

发表于 | 分类于

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

Collection

Collection

Collection主要分为三类：Set，List，Queue。

Set是无序存储，而且不会存储重复的元素。

Queue是一个队列，只能从一端插入元素，从另一端取出元素。

Map

Map存储的是键值对。

List

ArrayList

ArrayList的底层实现是一个数组，其访问速度比较快，但是插入删除速度比较慢。

1
2
//transient表示这个成员不可以被序列化
transient Object[] elementData;

扩容

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

1
2
3
4
5
6
7
8
9
10
11
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);
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
public E remove(int index) {
    //检查index是否合法
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //需要将index+1后面的位置都往前移动
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

Vector

它的实现与 ArrayList 类似，但是使用了 synchronized 进行同步,是线程安全的。

1
2
3
4
5
6
7
8
9
10
11
12
13
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

扩容

Vector 的构造函数可以传入 capacityIncrement 参数，它的作用是在扩容时使容量 capacity 增长 capacityIncrement。如果这个参数的值小于等于 0，扩容时每次都令 capacity 为原来的两倍。

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

与ArrayList不同

  • 加了synchronized关键字，是线程安全的。
  • Vector 每次扩容请求其大小的 2 倍（也可以通过构造函数设置增长的容量），而 ArrayList 是 1.5 倍。

但是，一般来说，在面对多线程的情况，我们也很少使用Vector，因为效率比较低。

CopyOnWriteArrayList

CopyOnWriteArrayList也是基于写时复制以及读写分离的思想。

当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。对CopyOnWrite容器进行并发的读的时候，不需要加锁，因为当前容器不会添加任何元素。

CopyOnWriteArrayList内部维护了一个数组，而且是volatile的。

1
2
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

get

1
2
3
4
5
6
7
8
9
10
11
12
13
public E get(int index) {
    return get(getArray(), index);
}
/**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
final Object[] getArray() {
    return array;
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

实现非常简单，因为根据写时复制，读取数据的时候数据不会修改，所以肯定是线程安全的。

add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
	//1. 使用Lock,保证写线程在同一时刻只有一个
    lock.lock();
    try {
		//2. 获取旧数组引用
        Object[] elements = getArray();
        int len = elements.length;
		//3. 创建新的数组，并将旧数组的数据复制到新数组中
        Object[] newElements = Arrays.copyOf(elements, len + 1);
		//4. 往新数组中添加新的数据	        
		newElements[len] = e;
		//5. 将旧数组引用指向新的数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
  • 需要添加lock，避免出现多个线程写数据。
  • 将旧数组拷贝，对新数组进行写操作，操作完成将数组引用指向新数据。
  • 实际上核心就是读写其实是在两个不同的容器中，所以就可以进行同时读写。

与读写锁区别

COW与读写锁都使用了读写分离的思想，都可以同时多个线程读。

但是COW读写线程是可以同时的。

缺点

  • 数据一致性问题。COW实际上会有读延迟情况的发生。所以，假如对数据实时一致性很高，最好不使用COW。
  • 内存问题。COW每次写数据都需要重新拷贝一个数组，假如高并发写或者对象比较大，会造成频繁GC。COW其实是不适用于高并发频繁写的场景。

LinkedList

基于双向链表实现。

linkedList

Set

Set的核心概念就是集合内所有元素不重复。

HashSet

基于HashMap实现,。

1
2
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

意思就是HashSet的集合其实就是HashMap的key的集合，然后HashMap的val默认都是PRESENT。HashMap的定义即是key不重复的集合。使用HashMap实现，这样HashSet就不需要再实现一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//遍历的是HashMap的key
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public void clear() {
    map.clear();
}

LinkedHashSet

LinkedHashSet会根据add，remove这些操作的顺序在遍历时返回固定的集合顺序。

TreeSet

基于TreeMap实现。

TreeSet即是一组有次序的集合，如果没有指定排序规则Comparator，则会按照自然排序。

Java容器

CopyOnWriteArrayList