Java集合总结

共计 4446 个字符，预计需要花费 12 分钟才能阅读完成。

有序集合，允许重复的元素，允许插入多个 null 元素，根据元素的索引访问元素

底层数组实现，无参构造器默认实现容量为 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);
    }

底层为双向链表实现

不包含重复元素的集合，最多包含一个 null 元素

特性：

基于 HashMap 实现，无序容器，侧重在存储数据的唯一性
允许存在 null 值
非线程安全实现
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，基于 LinkedHashMap 实现
有序容器，由 LinkedHashMap 实现迭代顺序于元素插入顺序一致
非线程安全实现
LinkedHashSet 迭代遵循 fail-fast 机制

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

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

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

特点：

基于 TreeMap 实现，由 TreeMap 保证有序
增删查操作时间复杂度为 log(n)
非线程安全
迭代遵循 fail-fast 机制
不允许 null 值对象

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

private transient NavigableMap<E,Object> m;

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

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

迭代器：

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

Map 并非 collection 的子接口或者实现类，每个 Entry 都持有两个对象，键对象和值对象，Map 可能会持有相同的值对象但键对象唯一

特性：

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

特性：

不允许 null 值
线程安全
Hashtable 的父类是 Dictionary
无序容器

特性：

非线程安全
有序容器，内部维护链接全部 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);
        }
    }

特性：

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

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);
    }

基本数据类型包装类，String 类等默认实现 Comparable 接口，可直接作为 key 对象
自定义对象：
1. 实现 Comparable 接口，重写 Compareto 方法
2. 自定义比较器类，并且要让其实现 Comparator 接口，通过以下构造方法指定使用自定义比较器类

线程安全包装类

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

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


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

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

// 如在 ArrayList 内部实现的迭代器中，当调用方法 next 或者 remove 时会首先检查 modCount == expectedModCount（创建迭代器时由 modCount 赋值）final void checkForComodification() {if (modCount != expectedModCount)
                throw new ConcurrentModificationException();}

List

ArrayList

LinkedList

Vector

Stack

Set

HashSet

LinkedHashSet

TreeSet

Map

HashMap

HashTable

LinkedHashMap

TreeMap

集合类线程安全实现

fail-fast 机制

Just My Socks（注册教程内含优惠码）