Java集合总结

List

允许重复的元素

允许插入多个null元素

有序（元素插入顺序与输出顺序相同）

根据元素的索引访问元素

常见实现类ArrayList，LinkedList，CopyOnWriteArrayList,Vector,Stack

ArrayList

底层数组实现，无参构造器默认实现容量为10的空数组

查找直接由位置索引

public E get(int index) {
        rangeCheck(index);

        return elementData(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++;
    }

删除存在数组复制

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);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

ArrayList扩容，数组大小超过设定容量时自动扩容至1.5倍大小

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //扩容至1.5倍大小
        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:
        //System.arraycopy针对已存在的源数组和目的数组进行拷贝，Arrays.copyOf拷贝需创建新的目的数组，底层调用System.arraycopy
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

LinkedList

底层为双向链表实现

CopyOnWriteArrayList

Vector

Stack

Set

不允许重复的元素，

允许插入1个null元素

常见实现类HashSet,LinkHashSet和TreeSet

HashSet

HashSet特性：

1. 基于HashMap实现，无序容器，侧重在存储数据的唯一性
2. 允许存在null值
3. 非线程安全实现
4. HashSet迭代遵循fail-fast机制

类成员变量，插入元素作为map的key对象，value对象保持不变为Object

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

无参构造函数

public HashSet() {
        map = new HashMap<>();
    }

HashSet查找，插入，删除操作均借助HashMap实现

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

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

HashSet线程安全实现

Set s = Collections.synchronizedSet(new HashSet(...));

LinkedHashSet

特点：

1. 继承于HashSet，基于LinkedHashMap实现
2. 有序容器，由LinkedHashMap实现迭代顺序于元素插入顺序一致
3. 非线程安全实现
4. LinkedHashSet迭代遵循fail-fast机制

//无参数构造函数默认调用HashSet构造函数
public LinkedHashSet() {
        super(16, .75f, true);
    }

此构造函数使用LinkedHashMap实现，保证元素FIFO

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

TreeSet

TreeSet特点：

1. 基于TreeMap实现，由TreeMap保证有序
2. 增删查操作时间复杂度为log(n)
3. 非线程安全
4. 迭代遵循fail-fast机制，即迭代器创建以后TreeSet结构被修改会触发ConcurrentModificationException异常
5. 不允许null值对象

成员变量，TreeSet内部基于TreeMap实现

private transient NavigableMap<E,Object> m;

//值对象固定为Object
private static final Object PRESENT = new Object();

//无参构造器
public TreeSet() {
        this(new TreeMap<E,Object>());
    }

通过包装器实现线程安全的TreeSet

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

TreeSet排序方式比较

1.基本数据类型

2.引用类数据类型（如自定义对象）

方式一：引用类对象实现Comparable接口，重写Compareto方法
方式二：自定义比较器类，并且要让其实现Comparator接口
，通过以下构造方法指定使用自定义比较器类

public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

迭代器：

//升序迭代器
public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }
//降序迭代器
public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }

Map

Map并非collection的子接口或者实现类

每个Entry都持有两个对象，键对象和值对象，Map可能会持有相同的值对象但键对象唯一

TreeMap通过Comparator或者Comparable 维护排序顺序

HashMap

特性：

1. 非线程安全
2. 键对象允许1个null值，值对象允许多个null值
3. 父类是AbstractMap
4. 无序容器

HashTable

特性：

1. 不允许null值
2. 线程安全
3. Hashtable的父类是Dictionary
4. 无序容器

LinkedHashMap

特性：

1. 非线程安全
2. 有序容器，内部维护链接全部Entry双向指针实现迭代顺序与Entry插入顺序一致

LinkedHashMap的Node继承于HashMap的Node同时增加头尾指针：

static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

LinkedHashMap有序性实现

TreeMap

特性：

1. 基于红黑树实现
2. 有序容器，根据key对象实现Comparable接口或者是比较器Comparator排序
3. 增删查改时间复杂度为log(n)
4. 非线程安全实现

TreeMap的put方法

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

其中compare方法

final int compare(Object k1, Object k2) {
        //comparator为TreeMap的成员变量
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

线程安全实现：

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

fail-fast机制

即快速失败机制，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，此时程序会抛出 ConcurrentModificationException异常，从而产生fail-fast机制。

//如在ArrayList内部实现的迭代器中，当调用方法next或者remove时会首先检查modCount == expectedModCount（创建迭代器时由modCount赋值）

final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }