Java 常用集合

1. ArrayList

基于动态数组实现，可以插入空数据，支持随机访问。
ArrayList在调用 add() 方法的时候

• 首先进行扩容校验。如果容量不够时，需要使用 grow() 方法进行扩容，每次扩容大小是原数组的 1.5 倍。
• 将插入的值放到尾部。

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

如果是在指定位置添加数据的话

• 也是首先扩容校验。
• 接着对数据进行复制，目的是把 index 位置空出来放本次插入的数据，并将后面的数据向后移动一个位置。

 public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //复制，向后移动
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

那么删除数据也是一样的思路

将 index+1 后面的元素都复制到 index 位置上，然后将数组大小减一，该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。

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

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

Vector

Vector 底层数据结构和 ArrayList 类似,也是一个动态数组存放数据。不过是在 add() 方法的时候使用 synchronized 进行同步写数据,开销比较大

与 ArrayList 的比较
Vector 是同步的，因此开销就比 ArrayList 要大，访问速度更慢。
Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍。

CopyOnWriteArrayList

特点是：读写分离
写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。

适用场景
CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

但是 CopyOnWriteArrayList 有其缺陷：

内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

LinkedList

基于双向链表实现，使用 Node 存储链表节点信息

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每个节点存储了 prev 和 next 指针：

image.png

新增

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
     /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

从以上可以看出插入数据都是移动指针，改变前驱指针和后继指针的指向，当然删除数据也是一样的。

查找

 public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

查找方法，利用了双向链表的特性，如果index离链表头比较近，就从节点头部遍历。否则就从节点尾部开始遍历。
也就是索引值大于链表大小的一半，那么将从尾结点开始遍历
这样的效率是非常低的，特别是当 index 越接近 size 的中间值时。

总结：

• LinkedList 插入，删除都是移动指针效率很高。
• 查找需要进行遍历查询，效率较低。

HashMap

HashMap 底层是基于数组和链表实现的。其中有两个重要的参数：

• 容量
• 负载因子
  容量的默认大小是 16，负载因子是 0.75，当 HashMap 的 size > 16*0.75 时就会发生扩容(容量和负载因子都可以自由调整)。

put 方法

首先会将传入的 Key 做 hash 运算计算出 hashcode,然后根据数组长度取模计算出在数组中的 index 下标。