Java回顾系列1：java集合重拾之旅

一. 集合分类

集合类型	简点描述
Set	无序、不可重复的集合
List	有序、重复的集合
Queue	队列集合
Map	具有映射关系的集合

Java集合.png

二. 常用的List

(A). ArrayList分析

面试的时候总被问，ArrayList底层是有什么实现的？它为什么查询，修改快。 插入，删除慢呢？

1. ArrayList是以数组实现的

transient Object[] elementData; // 非私有以简化嵌套类访问

2. ArrayList 默认第一次插入元素时创建大小为10的数组

 private static final int DEFAULT_CAPACITY = 10;//默认初始容量。

3.ArrayList的插入 add(E e) / add(int index, E e)

public void add(int index, E element) {
    //检查是否指针越界
    rangeCheckForAdd(index);
    //确保内部能力
    ensureCapacityInternal(size + 1);  // 增量modCount ! !
    System.arraycopy(elementData, index, elementData, index + 1,   size - index);
    elementData[index] = element;
    size++;
 }

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

    //确保明确的能力
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
    //扩展 
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩展为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩为1.5倍还不满足需求，直接扩为需求值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //minCapacity通常接近于size，所以这是一个胜利
    elementData = Arrays.copyOf(elementData, newCapacity);
}

4. ArrayList的删除 remove(int index) / remove(Object o)

public E remove(int index) {
    rangeCheck(index);//检查是否越界
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0){
         // 把后面的往前移
      System.arraycopy(elementData, index+1, elementData, index, numMoved);
    }
     // 把最后的置null
   elementData[--size] = null; // clear to let GC do its work
   return oldValue;
}

5.ArrayList 查找,修改

public E set(int index, E element) {
    rangeCheck(index);//检查是否越界
    E oldValue = elementData(index);
    elementData[index] = element; //新的值 替换 老的
    return oldValue;
}
public E get(int index) {
    rangeCheck(index);//检查是否越界
    return elementData(index);
}

6.ArrayList总结

数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用System.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。

按数组下标访问元素—get(i)/set(i,e) 的性能很高，这是数组的基本优势。

直接在数组末尾加入元素—add(e)的性能也高，但如果按下标插入、删除元素—add(i,e), remove(i), remove(e)，则要用System.arraycopy()来移动部分受影响的元素，性能就变差了，这是基本劣势。

(B). LinkedList分析

1. LinkedList使用双向链表实现，内部提供了一个内部类 “Node<E>”。

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

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element; 当前Item
            this.next = next; 上一个
            this.prev = prev; 下一个
        }
    }

LinkedList.jpg

(C). 一些学习链接

源码分析网上有很多，也各有千秋。我把自己看的文章比较好的贴出来，感谢这些作者的总结，更深层次的了解java集合。

1. HashMap分析总结：
   https://www.jianshu.com/p/e5c8a814c0ca
   https://www.jianshu.com/p/8324a34577a0

2. Java集合这些类大体应用场景：https://zhuanlan.zhihu.com/p/118656578