集合学习笔记——Collection 全家桶

Collection是我们日常开发中使用频率非常高的集合，它的主要实现有List和Set,区别是List是有序的，元素可以重复;Set是无序的，元素不可以重复，我们简单看下继承关系：

1. List的实现类主要线程不安全的ArrayList和LinkedList以及线程安全的CopyOnWriteArrayList;
2. Set的实现类主要有线程不安全的HashSet和TreeSet以及线程安全的CopyOnWriteArraySet。

个人觉得，以上集合组件类其实并不难，所以我不打算分析源码，其中HashSet和TreeSet底层使用分别是HashMap和TreeMap, 所以只要看下之前的文章就比较容易理解了。

1.ArrayList VS LinkedList

ArrayList:

1. 底层是通过数组(内存地址连续)实现的，直接可以通过下标找到目标元素，时间复杂度是O(1),而LinkedList需要移动指针遍历每个元素，时间复杂度是O(N),所以 Arraylist查找元素的速度比Linkedlist快.
2. Arraylist在新增和删除元素时，可能扩容和复制数组。而Linkedlist实例化对象只需要修改指针即可.
3. Arraylist 可能会造成一定空间的浪费，因为它要预先开辟空间
4. 默认的初始容量是10个，每次扩容为原来的1.5倍(当数组满了才会扩容，不像HashMap有扩容因子)

LinkedList:

1. 底层是通过线性表(链表)(内存空间不连续)来实现的，是一个双向链表
2. LinkedList不支持高效的随机访问，它需要移动指针遍历每个元素
3. 没有初始容量，没有扩容机制

时间复杂度对比：

总体来说：ArrayList查询速度快，LinkedList插入删除速度快。

使用场景：

1. 如果应用程序对数据有较多的随机访问，ArrayList性能要优于LinkedList；
2. 如果应用程序有更多的插入或者删除操作，较少的随机访问，LinkedList性能要优于ArrayList；
3. 不过ArrayList的插入，删除操作也不一定比LinkedList慢，如果在ArrayList靠近末尾的地方插入，那么ArrayList只需要移动较少的数据（或者无需移动数据)，此时二者耗时几乎差不多(LinkedList是双向链表，可以快速定位头尾部的节点)

2.HashSet VS TreeSet

HashSet 和 TreeSet 都是元素不能重复的集合，其中TreeSet具有排序的功能。

HashSet源码分析：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;
 
    /**
     *
     * HashSet底层用的就是HashMap，只不过只使用了HashMap的key
     */
    private transient HashMap<E,Object> map;
 
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
 
    /**
     * 无参构造器：内部创建一个HashMap
     */
    public HashSet() {
        map = new HashMap<>();
    }
 
    /**
     * 参数是集合
     */
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/0.75f) + 1, 16));
        addAll(c);
    }
 
    /**
     * 指定容量的构造器，这个容量将传递给HashMap
     */
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
 
    /**
     * add元素，发现它确实是添加到了HashMap中
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
 
    //.....省略其他代码
}
复制代码

不难发现，HashSet底层使用的就是HashMap,只不过是只使用了HashMap的key,根据HashMap的特点，key如果相同，则旧值覆盖新值，所以达到去重的效果。

TreeSet源码分析:

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * 内存真正存储元素的组件：TreeMap, 只不过是只使用了key
     */
    private transient NavigableMap<E,Object> m;
 
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
 
    /**
     * 空参数构造器：其内部创建了TreeMap, 但是只使用TreeMap的key
     */
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
 
    /**
     * 可以传入一个比较器，这个比较器将交给TreeMap
     */
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
 
    /**
     * 添加元素：将添加到TreeMap中
     */
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
  }  
复制代码

不难发现，TreeSet底层使用的是TreeMap,只不过是只使用了TreeMap的key,根据TreeMap的特点，默认是按照自然排序(key必须要实现Comparable接口),或者指定比较器Comparator，自定义比较规则。

3.线程安全的CopyOnWriteArrayList

CopyOnWriteArraySet 底层使用的也是CopyOnWriteArrayList

先简单总结下它的底层原理：

1. CopyOnWriteArrayList内部也是通过数组来实现的，在向CopyOnWriteArrayList添加元素时，会复制一个新的数组，写操作在新数组上进行，读操作在原数组上进行(写时复制的思想)
2. 写操作会加锁，防止并发写入造成数据丢失的问题
3. 写操作结束后会把原数组指向新数组
4. CopyOnWriteArrayList允许在进行写操作的同时来读取数据，大大提高了读的性能，因此适合读多写少的场景(写多读少的话，会大量复制数组，非常耗费内存)，但是CopyOnWriteArrayList可能读到的数据不是最新的数据，所以不适合实时性要求高的场景(数据不一致的问题)。

只能保证最终一致，不能保证实时一致

我们看下源码：

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;
 
    /** 
     * 通过 ReentrantLock 来保证写时的线程安全
     */
    final transient ReentrantLock lock = new ReentrantLock();
 
    /** 
     * 底层仍然是使用数组来存储数据
     */
    private transient volatile Object[] array;
  
 
    /**
     * 读取数据，没有加锁，直接读就可以
     */
    public E get(int index) {
        return get(getArray(), index);
    }
    
    private E get(Object[] a, int index) {
        return (E) a[index];
    }
 
    /**
     * 添加元素（写）
     * 
     * 1.首先加锁
     * 2.获取原数组
     * 3.根据原数据复制一个新的数组
     * 4.然后对新数组进行写操作（这中间读的话，仍然读的是原数组)
     * 5.将新数组赋给原数组
     */
    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();
        }
    }
 
     /**
     * 删除元素（写）：和 add一样
     * 
     * 1.首先加锁
     * 2.获取原数组
     * 3.根据原数据复制一个新的数组
     * 4.然后对新数组进行写操作（这中间读的话，仍然读的是原数组)
     * 5.将新数组赋给原数组
     */
    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
 } 
复制代码

源码并不复杂，就是写时复制的思想，我们简单用一张图来展示下：

好了，关于Collection集合下常用的组件就分析到这里吧，对比Map，这些就显得比较简单了，源码也很容易理解。