Java容器的常见问题

记录Java容器中的常见概念和原理

基础容器

ArrayList(动态数组)、LinkedList(带头结点的双向链表)

ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

默认初始容量为 10；
扩容机制：添加元素前，先检查是否需要扩容，一般扩为源数组的 1.5 倍 + 1；
边界检查（即检查 ArrayList 的 Size）：涉及到 index 的操作；
调整数组容量（减少容量）：将底层数组的容量调整为当前列表保存的实际元素的大小；
在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理；
LinkedList
LinkedList 不但实现了List接口，还实现了Dequeue接口。因此，LinkedList不但可以当做List来用，还可以当做Stack(push、pop、peek)，Queue(offer、poll、peek)来使用。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;

    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
   }
}

ArrayList与LinkedList比较

ArrayList是基于数组的实现，LinkedList是基于带头结点的双向循环链表的实现；
ArrayList支持随机访问，LinkedList不支持；
LinkedList可作队列和栈使用，实现了Dequeue接口，而ArrayList没有；
ArrayList 寻址效率较高，插入/删除效率较低；LinkedList插入/删除效率较高，寻址效率较低

Fast-fail机制

Fail-Fast 是 Java 集合的一种错误检测机制，为了防止在某个线程在对Collection进行迭代时，其他线程对该Collection进行结构上的修改。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险，抛出 ConcurrentModificationException 异常。

Set (HashSet，LinkedHashSet，TreeSet)

Set不包含重复的元素，这是Set最大的特点，也是使用Set最主要的原因。常用到的Set实现有 HashSet，LinkedHashSet 和 TreeSet。一般地，如果需要一个访问快速的Set，你应该使用HashSet；当你需要一个排序的Set，你应该使用TreeSet；当你需要记录下插入时的顺序时，你应该使用LinedHashSet。

HashSet：委托给HashMap进行实现，实现了Set接口
HashSet是采用hash表来实现的，其中的元素没有按顺序排列，add()、remove()以及contains()等方法都是复杂度为O(1)的方法。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    static final long serialVersionUID = -5024744406713321676L;

    // 底层支持，HashMap可以代表一个HashMap，也可以代表一个LinkedHashMap
    private transient HashMap<E,Object> map;

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

LinkedHashSet：是HashSet的子类，被委托给HashMap的子类LinkedHashMap进行实现，实现了Set接口
LinkedHashSet继承于HashSet，利用下面的HashSet构造函数即可，注意到，其为包访问权限，专门供LinkedHashSet的构造函数调用。LinkedHashSet性能介于HashSet和TreeSet之间，是HashSet的子类，也是一个hash表，但是同时维护了一个双链表来记录插入的顺序，基本方法的复杂度为O(1)。
TreeSet：委托给TreeMap(TreeMap实现了NavigableSet接口)进行实现，实现了NavigableSet接口(扩展的 SortedSet)
TreeSet是采用树结构实现(红黑树算法)，元素是按顺序进行排列，但是add()、remove()以及contains()等方法都是复杂度为O(log (n))的方法，它还提供了一些方法来处理排序的set，如first()、 last()、 headSet()和 tailSet()等。此外，TreeSet不同于HashSet和LinkedHashSet，其所存储的元素必须是可排序的(元素实现Comparable接口或者传入Comparator)，并且不能存放null值。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;   // 底层支持

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

    // 默认构造函数
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

Map(HashMap, LinkedHashMap, TreeMap)

HashMap

对NULL键的特别处理
- HashMap 中可以保存键为NULL的键值对，且该键值对是唯一的。若再次向其中添加键为NULL的键值对，将覆盖其原值。此外，如果HashMap中存在键为NULL的键值对，那么一定在第一个桶中。
HashMap 中的哈希策略
- 使用 hash() 方法用于对Key的hashCode进行重新计算，以防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是 2 的倍数，通过右移可以使低位的数据尽量的不同，从而使Key的hash值的分布尽量均匀；
- 使用 indexFor() 方法进行取余运算，以使Entry对象的插入位置尽量分布均匀
HashMap 的底层数组长度为何总是2的n次方？
- 构造函数及扩容策略
```
// HashMap 的容量必须是2的幂次方，超过 initialCapacity 的最小 2^n
int capacity = 1;
while (capacity < initialCapacity)
  capacity <<= 1;
```
*当底层数组的length为2的n次方时，h&(length - 1) 就相当于对length取模，而且速度比直接取模快得多，这是HashMap在速度上的一个优化
初始容量16，两倍扩容，先添加再检查
LinkedHashMap：HashMap + 带头结点的双向循环链表

TreeMap：红黑树的实现

排序二叉树 Vs. 红黑树
排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插入节点集本身是大到小排列）；或所有节点只有右节点（如果插入节点集本身是小到大排列）。在这种情况下，排序二叉树就变成了普通链表，其检索效率就会很差。
红黑树
为了改变排序二叉树存在的不足，Rudolf Bayer 与 1972 年发明了另一种改进后的排序二叉树：红黑树，他将这种排序二叉树称为“对称二叉 B 树”，而红黑树这个名字则由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。
红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型地，JDK 提供的集合类 TreeMap 本身就是一个红黑树的实现。红黑树在原有的排序二叉树增加了如下几个要求:
- 性质 1：每个节点要么是红色，要么是黑色；
- 性质 2：根节点永远是黑色的；
- 性质 3：所有的叶节点都是空节点（即 null），并且是黑色的；
- 性质 4：每个红色节点的两个子节点都是黑色（从每个叶子到根的路径上不会有两个连续的红色节点）；
- 性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
红黑树的性质
上面的性质3中指出:红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用null来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。根据性质 5，红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）”。性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。
假如有一棵黑色高度为 3 的红黑树：从根节点到叶节点的最短路径长度是 2，该路径上全是黑色节点（黑节点 - 黑节点 - 黑节点）。最长路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点 - 红节点 - 黑节点 - 红节点 - 黑节点），性质 4 保证绝不可能插入更多的红色节点。由此可见，红黑树中最长路径就是一条红黑交替的路径。由此我们可以得出结论：对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1，最长路径长度为 2 * (N-1)。
红黑树的查找、插入与删除操作
由于红黑树只是一个特殊的排序二叉树，因此对红黑树上的只读操作与普通排序二叉树上的只读操作完全相同，只是红黑树保持了大致平衡，因此检索性能比排序二叉树要好很多。但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插入操作和删除操作都需要进行一定的维护，以保证插入节点、删除节点后的树依然是红黑树。
红黑树和平衡二叉树
我们知道，在AVL树中，任何节点的两个子树的最大高度差为1，所以它也被称为高度平衡树；而红黑树并不追求完全平衡，它只要求大致地达到平衡要求，降低了对旋转的要求，从而提高了性能。实际上，由于红黑树的设计，任何不平衡都会在三次旋转之内解决。
红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构，能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
红黑树并不是真正的平衡二叉树，但在实际应用中，红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
排序二叉树的深度直接影响了检索的性能，正如前面指出，当插入节点本身就是由小到大排列时，排序二叉树将变成一个链表，这种排序二叉树的检索性能最低：N 个节点的二叉树深度就是 N-1。
红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高，这样保证红黑树在最坏情况下都是高效的，不会出现普通排序二叉树的情况。

节点