Java漫游笔记-08-集合

什么是集合

在 Java 中，集合表示一组对象，这些对象也称为集合的元素。

使用集合框架的好处

通过 API 文档，我们不难发现，其实在 JDK 1.0 的时候，只包含了很少的集合类（例如：Vector ，Stack ，Array ，Hashtable ），
然而，集合的应用场景非常广泛，因此，在 JDK 1.2 的时候由大牛 Josh Bloch 设计并实现的集合框架便应运而生了。
使用 JDK 提供的集合框架，主要好处如下:

• 减少开发成本，不用开发者再造“轮子”。
• JDK 提供的集合类都经过了良好的测试，在代码质量和性能上都有所保证。
• 提供了一套接口标准，为不同开发者提供了一种“共同的语言”。

集合框架的层次结构

Java 的集合框架主要有两大接口： Collection 和 Map 。

• Collection 用于存放一组对象（多个单对象），Map 用于存放键值对。
• Collection 中常用的有 List 和 Set 。
  • List 允许放入相同的对象，而 Set 不能。
  • List 接口常用的实现类有：ArrayList 、LinkedList 、Vector 和 Stack 。
  • Set 接口常用的实现类有： HashSet 、TreeSet 。
• Map 接口常用的实现类有：HashMap 、TreeMap 。

两大接口的层次结构：

• java.util.Collection
  • java.util.Set
  • java.util.SortedSet
  • java.util.NavigableSet
  • java.util.Queue
  • java.util.concurrent.BlockingQueue
  • java.util.concurrent.TransferQueue
  • java.util.Deque
  • java.util.concurrent.BlockingDeque
• java.util.Map
  • java.util.SortedMap
  • java.util.NavigableMap
  • java.util.concurrent.ConcurrentMap
  • java.util.concurrent.ConcurrentNavigableMap

集合框架接口层次结构：

集合框架类层次结构：

主要的接口和实现类

Interface	Hash Table	Resizable Array	Balanced Tree	Linked List	Hash Table + Linked List
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Deque		ArrayDeque		LinkedList
Map	HashMap		TreeMap		LinkedHashMap

List

List 是有序的集合，这个有序不是指集合里面的元素是按值排序的，而是指这些元素存储的位置是有序的。更确切地讲，用户可以把元素添加到指定的位置。

ArrayList

ArrayList 是一个动态数组，默认是空的，相当于 {}。
add 操作会自动扩充容量，默认容量为 10 。
当 ArrayList 的容量即将超出限制时，会自动扩充：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

简单来说，就是扩大为当前容量的 1.5 倍。
其中：minCapacity 为当前容量 + 1 ，最大容量为 Integer.MAX_VALUE 。
从实现的代码可以知道，扩容的时候，需要将现有的元素复制到新数组中。因此，当元素很多的时候，这个复制操作是很昂贵的。
因此，在添加大量元素前，建议使用 ensureCapacity() 方法来增加 ArrayList 的容量，以减少递增式扩容的开销。

add(E) 和 add(int, E) 的主要区别在于， add(int, E) 需要把 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++;
}

remove(int) 不需要通过遍历来查找对象，因此，性能会比 remove(Object) 要好。
但是，不管怎么样，都需要通过 System.arraycopy() 来移动受影响的元素。

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

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

对应 ArrayList 而言，由于它使用数组实现，节约空间，并且可以通过索引高效地获取元素（get(int) / set(int, E)），其主要缺点在于，增删操作性能较差。

LinkedList

LinkedList 是一个双向链表。
链表没有容量限制，但双向链表的实现需要占用更多的空间，也需要额外的链表指针操作。

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;
        this.next = next;
        this.prev = prev;
    }
}

add 操作相对 ArrayList 就简单很多，不用考虑复制数组的问题，只需要修改前后节点的引用即可：

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

get 操作则比较麻烦，需要遍历，不过 Josh Bloch 也做了一点优化：

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

Map

Map 以键-值对的方式存放元素，也有人称之为：映射表。
一个 Map 中不能包含有重复的键，每个键最多只能映射到一个值。

至于 Map 为什么没有继承自 Collection （能不能把 Map 视为键-值对的集合，或者视为用键作为索引的值的集合）？
官方给出的解释是：

我们认为映射（mappings）不是集合（collections），集合也不是映射。因此，Map 继承 Collection 接口没有意义，反之亦然。
如果 Map 是一种 Collection ，那么它的元素是什么呢？唯一合理的答案是“键-值对”，但是，这样一来就只能提供一种非常有限的（没什么用的）映射抽象。你不能按键取值，也不能仅仅依据键来删除元素（因为不知道这个键映射的值）。
如果 Collection 继承自 Map ，这又会引发另一个问题：什么是键？没有令人满意的答案。这样的设计会被迫出现一个不自然的接口。
事实上，可以将 Map 看作是 Collection ，这体现在 Map 提供了三种（键、值、键-值对） Collection 视图（允许以键集 KeySet 、值集合 values 或键-值映射关系集 EntrySet 的形式查看某个 Map 的内容）……

HashMap

对于 HashMap 的理解，重点在于理解它的结构和插入操作。
HashMap 基于数组实现，数组中存放链表或者是红黑树（在 JDK 1.8 中，如果链表长度超过阀值[8]，则会把链表转换成红黑树）。而这些链表以及红黑树又有人称之为桶（bucket）。

大概是长成这个样子的：

核心代码：

// 数组
transient Node<K,V>[] table;

// 链表节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    // some code

}

// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        
        // some code

插入元素时，首先会先对 key 对象进行 hash 操作，然后根据 hash 值定位到具体的桶。
如果 hash 相等，并且 key 相同，则覆盖旧值，并返回旧值。
如果 hash 相等，但是 key 不同，就产生了所谓的“ Hash 冲突”。
解决 Hash 冲突通常有两种方法：开放地址法和链表法。

• 开放地址法会通过一个探测算法，当某个桶位已经被占据的情况下继续查找下一个可以使用的桶位。
• 链表法则会将相同 hash 值的对象组织成一个链表放在 hash 值对应的桶位。

HashMap 的实现采用的就是链表法：

// hash 操作
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {
               boolean evict)
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        // 如果链表数组为空，进行初始化
        n = (tab = resize()).length;
    // 获取对象的存储位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果为空，则插入新节点
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 如果 hash 相等并且 key 相同，则覆盖旧值，并返回旧值
            e = p;
        else if (p instanceof TreeNode)
            // 如果是树节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                // 将新插入的对象与桶中的所有对象进行比较
                if ((e = p.next) == null) {
                    // 如果对象不存在，那么会新增一个节点
                    //也就是说 hash 冲突后，桶里存储的不是单个对象，而是一个 单向链表
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 如果链表长度超过阀值，则会把链表转换成红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            // 更新 hash 值和 key 值均相同的节点 value 值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 并返回旧值
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        // 桶数量超过阀值时，会成倍扩容数组
        resize();
    afterNodeInsertion(evict);
    return null;
}

其实不管是 put 操作还是 get 操作，首先要做的就是定位，也就是找到对象存储的地址。
因此，既要考虑计算的性能，又要尽量避免冲突。
HashMap 的做法是：

i = (n - 1) & hash

这种实现假定哈希函数能够将元素离散地分布在各桶之间，因为只有这样才可为 get/put 之类的操作提供稳定的性能。

关于 HashMap 的性能，影响的参数有两个：初始容量 和 加载因子 。

• 容量是指 HashMap 中能够填充的桶的最大数量，初始容量即创建时的容量（默认为 16 ）。
• 加载因子可以理解为填充比（默认为 0.75f ），是一个阀值，当 HashMap 中桶的数量大于加载因子与容量的乘积时（0.75f * 16），就要对该 HashMap 进行 resize 操作。

不难看出：
如果把加载因子设置得高一些，就可以节约空间，但同时又会增加查询成本。
如果初始容量设置太小，又会导致 resize 操作，因此，如果需要自定义参数，应考虑到需要存储的对象数量。

TreeMap

TreeMap 是一个基于红黑树（Red-Black tree）的 NavigableMap 实现，支持按 key 排序。
可以通过 firstKey() ，lastKey() 取得最大最小的 key 。
还可以通过 subMap(K fromKey, K toKey) ，tailMap(K fromKey) 获得子集视图。

TreeMap 的 put 操作会从根节点开始判断，基于 compare 的值来决定元素放在树的左边还是右边，如果找到相等的 key ，那么就直接替换为新值，如果一直找不到，则创建一个新的 Entry 对象。

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

TreeMap 的 containsKey、get、put 和 remove 操作时间开销为：log(n) 。

Set

Set 是一个不包含重复元素的集合。
为什么先学习 Map ？
是因为 Set 的子类的几乎都是基于特定的 Map 实现的。
前面我们可以看到 Map 的键集视图 KeySet 就是一个 Set 。

HashSet

HashSet 的内部实现是 HashMap ，使用 key 保存元素，而 value 则统一使用一个常量填充。

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

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

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

TreeSet

TreeSet 的内部实现是 TreeMap ，类似的，也是使用 key 保存元素，而 value 则统一使用一个常量填充。

private transient NavigableMap<E,Object> m;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

public TreeSet() {
    this(new TreeMap<E,Object>());
}

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

Deque

Deque 是 “double ended queue（双端队列）” 的缩写，通常读为 “deck” 。Deque 继承自 Queue ，支持 FIFO（先进先出）操作，也可用作 LIFO（后进先出）堆栈，并且 API 文档中建议我们优先使用此接口而不是使用遗留 Stack 类。

ArrayDeque

ArrayDeque 基于循环数组实现。没有容量限制，可以按需扩展。
用作堆栈时快于 Stack ，在用作队列时快于 LinkedList 。

transient Object[] elements;

// 第一个元素的索引
transient int head;

// 下一个要插入的元素索引
transient int tail;

public ArrayDeque() {
    elements = new Object[16];
}

LinkedList

LinkedList 以双向链表实现，既是 List ，也是 Queue 。
它是唯一一个允许放入 null 的 Queue 。

transient Node<E> first;

transient Node<E> last;

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;
        this.next = next;
        this.prev = prev;
    }
}

遍历操作

集合

Iterator

Iterator 是集合的迭代器。
需要注意的是，它的光标位于两个元素之间，因此：
调用 Iterator.next() 前，一般先判断 Iterator.hasNext() 。
而调用 Iterator.remove() 前，则需要先调用 Iterator.next() 。
可以这么理解：每一次调用 Iterator.next() 都会 “消耗掉” 一个元素（和 InputStream.read() 类似）。

ArrayList<String> aList = new ArrayList<>(); // JDK 1.7 菱形语法
aList.add("a");
aList.add("b");
aList.add("c");
Iterator<String> iterator = aList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

对于 List 还有更强大的 ListIterator 可以使用。
Iterator 只能进行正向的遍历，而 ListIterator 则允许按任一方向遍历，并且，还支持 add 、set 操作：

ArrayList<String> aList = new ArrayList<>();
aList.add("a");
aList.add("b");
aList.add("c");

ListIterator<String> listIterator = aList.listIterator(); // [a, b, c] and cursor = 0

listIterator.add("d"); // [d, a, b, c] and cursor = 1

while (listIterator.hasNext()) {
    System.out.println("forward：" + listIterator.next());
} // cursor = 4

listIterator.set("e"); // [d, a, b, e] and cursor = 4

while (listIterator.hasPrevious()) {
    System.out.println("backward：" + listIterator.previous());
} // cursor = 0

Enumeration

在 JDK 1.2 以前，还没有 Iterator 接口，需要使用 Enumeration 进行枚举：

Vector<String> aVector = new Vector<>();
aVector.add("a");
aVector.add("b");
aVector.add("c");
for (Enumeration<String> e = aVector.elements(); e.hasMoreElements();) {
    System.out.println(e.nextElement());
}

相对于 Enumeration ，Iterator 更安全。
因为 Iterator 对集合进行遍历时，会阻止其它线程对当前集合进行结构性的修改（例如：add、remove操作，会抛出 ConcurrentModificationException ），也就是所谓的 “快速失败（fail-fast）” 。
并且，Iterator 允许从集合中删除元素，方法名也更短。

foreach

由于 Collection 接口继承自 Iterable 接口，因此它的子类都支持 “foreach” 语句：

ArrayList<String> aList = new ArrayList<>();
aList.add("a");
aList.add("b");
aList.add("c");
for (String string : aList) {
    System.out.println(string);
}

Map

至于 Map 的遍历，一般是先获取 Map 的集合视图再进行遍历：

HashMap<String, String> map = new HashMap<String, String>();
map.put("a", "apple");
map.put("b", "banana");

// 键值视图
Set<Entry<String, String>> entrySet = map.entrySet();
for (Entry<String, String> entry : entrySet) {
    System.out.println("key=" + entry.getKey() + ", value="
            * entry.getValue());
}

工具类

Collections

Collections 类封装了对集合操作的各种静态方法和常量：

• addAll()
• binarySearch()
• fill()
• sort()
• checkedXxx()
• synchronizedXxx()
• unmodifiableXxx()

Arrays

Arrays 类包含用来操作数组（比如排序和搜索）的各种方法：

• binarySearch()
• copyOf()
• copyOfRange()
• fill()
• sort()
• parallelSort()
• parallelPrefix() // JDK 1.8
• setAll() // JDK 1.8
• parallelSetAll() // JDK 1.8
• spliterator() // JDK 1.8
• stream() // JDK 1.8

与 Collection 的 toArray() 方法相对，Arrays 类提供了 asList() 方法：

List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
String[] array = stooges.toArray(new String[0]);

并发编程

Java 集合框架中大部分的类都是非线程安全的，对于集合的并发编程，要么自己通过锁来控制它们的读写操作，要么使用 Java 自身提供的线程安全的集合类来解决。

以 List 为例，ArrayList 的实现不是线程安全的，而古老的 Vector 是线程安全的。
但是， Vector 的锁的粒度很大（它的方法基本上都加了 synchronized ），每次读写操作都会把列表中的所有元素锁住，产生互斥，这种开销是非常大的。
为了解决这个问题，Java 提供了一种 CopyOnWrite 机制：使得读操作始终能够并发执行，而写操作则是先拷贝一份数组出来修改，等修改完成后，再将它赋给内部的数组引用。

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

CopyOnWrite 机制对 “读多写少” 的场景是非常适用的，但是如果需要频繁的写操作，可能还不如自己直接加锁处理。

对于 Map ，Java 并没有提供 CopyOnWriteHashMap ，而是使用 “锁分段” 技术实现了 ConcurrentHashMap 。
其主要原理就是：首先将容器中的数据进行分区，分成一个个的片段（ Segment ，默认大小为 16），然后再给每一段数据配一把锁，当一个线程访问其中一个段数据的时候，只会占用当前片段的锁，而其他段的数据也就能被其他线程所访问。
这样一来，可以减少锁的竞争，并且内在的拷贝操作也不用占用太大的内存。
本质上就是为了减小锁的粒度。

除此之外， java.util.concurrent 包还提供了很多在并发编程中常用的工具类。
例如：

• CopyOnWriteArrayList // 并发优化的 ArrayList
• CopyOnWriteArraySet // 并发优化的 ArraySet
• ConcurrentHashMap // 并发优化的 HashMap
• ConcurrentSkipListMap // 并发优化的 SortedMap
• ConcurrentLinkedQueue // 并发优化的 Queue
• LinkedBlockingQueue // 并发优化的 BlockingQueue
• ArrayBlockingQueue // 并发优化的 BlockingQueue

这里暂时不再展开，后续再做研究。

更多内容

Guava

Guava 是 Google 的出品的一个类库，包含：集合 [collections] 、缓存 [caching] 、原生类型支持 [primitives support] 、并发库 [concurrency libraries] 、通用注解 [common annotations] 、字符串处理 [string processing] 、I/O 等内容。

其对集合框架的增强和扩展算是 Guava 最成熟和流行的部分之一。
在这里，只列举几个小例子，更多内容，可以到项目主页上去深入了解、学习。

// 能够推断范型的静态工厂方法
List<TypeThatsTooLongForItsOwnGood> list = Lists.newArrayList();
Map<KeyType, LongishValueType> map = Maps.newLinkedHashMap();

// 不可修改的集合
ImmutableSet digits = ImmutableSet.of("zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine");

// 按照字符串长度分组
Function<String, Integer> lengthFunction = new Function<String, Integer>() {
    public Integer apply(String string) {
        return string.length();
    }
};
// Multimap：在 Map 的 value 里面放多个元素
ImmutableListMultimap<Integer, String> digitsByLength= Multimaps.index(digits, lengthFunction);
/**  digitsByLength maps:*  3 => {"one", "two", "six"}*  4 => {"zero", "four", "five", "nine"}*  5 => {"three", "seven", "eight"}*/
*  digitsByLength maps:
*  3 => {"one", "two", "six"}
*  4 => {"zero", "four", "five", "nine"}
*  5 => {"three", "seven", "eight"}
*/

谣言

另外，网上还有一些文章在传：“ JDK 1.7 在语法层面上支持集合”，看上去挺美的。
然而，实际情况却是：这个语言特性目前仍未实现！
也许在后续的 JDK 版本（Java 9+ ？）中会实现，但是，以下代码在目前可用的 JDK 版本中无法编译通过的：

// 以下代码无法编译通过
final List<Integer> piDigits = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9];
final Set<Integer> primes = { 2, 7, 31, 127, 8191, 131071, 524287 };
final Map<Integer, String> platonicSolids = { 4 : "tetrahedron",
    6 : "cube", 8 : "octahedron", 12 : "dodecahedron", 20 : "icosahedron"
};

总结

对于集合框架的使用，最关键的是要明确应用场景。
不妨考虑以下几个问题：

• 是否使用数组就可以满足需求？
• 是 Collection ？还是 Map ？
• 是否允许存储相同的对象？
• 是否需要存储 null ？
• 是否需要对集合中对象进行排序？
• 是否需要进行有序的迭代？
• 是更关注写操作（ add/put/remove ）的效率？还是读操作（ get/contains ）的效率？
• 是否需要保证线程安全？

参考文档

• Java Tutorials：https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html
• Java SE API Documentation：http://docs.oracle.com/javase/8/docs/api/index.html