Java 集合类

Collections 框架图

List 框架图

Set 框架图

Map 框架图

Queue 框架图

HashMap

并发下的 HashMap 会有哪些安全问题？

这里我只是简单的说了写覆盖跟不可重复读（联想到数据库了），面试官就放我过了。

添加元素时头插还是尾插？

1.7 头插，1.8 尾插。

数组长度为什么必须是 2 的指数幂

减少哈希冲突，均匀分布元素。

1）通过将 Key 的 hash 值与 length-1 进行 & 运算，实现了当前 Key 的定位，2 的幂次方可以减少冲突（碰撞）的次数，提高 HashMap 查询效率；

2）如果 length 为 2 的次幂，则 length-1 转化为二进制必定是 11111…… 的形式，在于 h 的二进制与操作效率会非常的快，而且空间不浪费；如果 length 不是 2 的次幂，比如 length 为 15，则 length-1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

如何扩容的

(1) 初始扩容因子

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

为什么是 0.75 这个值呢？

这是因为对于使用链表法的哈希表来说，查找一个元素的平均时间是 O(1+n)，这里的 n 指的是遍历链表的长度，因此加载因子越大，对空间的利用就越充分，这就意味着链表的长度越长，查找效率也就越低。如果设置的加载因子太小，那么哈希表的数据将过于稀疏，对空间造成严重浪费。

(2) 何时扩容

首次 put 的时候，如果 table 为空，会执行扩容：

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

在 put 方法中，size++ 之后的值如果大于 threshold，那么也会执行 resize 方法。

if (++size > threshold)
    resize();

(3) 扩容扩多少

首次扩容：

newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

非首次扩容，新的容量和新的 threshold 都是翻一倍：

newCap = oldCap << 1;
newThr = oldThr << 1;

(4) 为何扩容

为了避免散列表性能下降。碰撞越来越严重。越来越多的链表。速度越来越慢。

元素如何迁移

创建新的数组

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

遍历旧数组

for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e;
    if ((e = oldTab[j]) != null) {
        // ...
    }
}

如果 e.next 不为空，即数组里面只存储了这一个元素

newTab[e.hash & (newCap - 1)] = e;

如果 e 是 TreeNode

((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

如果 e 有 next，维持原来的顺序，挂到新的数组上

原来的元素在重新计算 hash 之后，会放到两个数组的坑里面。

// (e.hash & oldCap) == 0 的属于 loHead
newTab[j] = loHead;
// 否则属于 hiHead
newTab[j + oldCap] = hiHead;

头插法设计思路

JDK1.7是考虑新增数据大多数是热点数据，所以考虑放在链表头位置，也就是数组中，这样可以提高查询效率，但这种方式会出现插入数据是逆序的。在JDK1.8开始hashmap链表在节点长度达到8之后会变成红黑树，这样一来在数组后节点长度不断增加时，遍历一次的次数就会少很多，相比头插法而言，尾插法操作额外的遍历消耗已经小很多了。

也有很多人说避免多线程情况下hashmap扩容时的死循环问题，我个人觉得避免死循环的关键不在尾插法的改变，而是扩容时，用了首尾两个指针来避免死循环。这个我会在后面的多线程中讲到hashmap扩容导致死循环的问题。

get 方法如何实现的

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

首先使用 (n - 1) & key.hash 定位到这个 key 应该落到 table 的哪一个桶里面，其中 n 是指 table 的长度。
然后看这个桶里面的 first 元素是否是目标值，如果是，直接返回。
否则看 first 是否属于 TreeNode，如果是 TreeNode，则调用 getTreeNode 方法；否则沿着 e.next 往下遍历，并依次检查条件 key.hash == k.hash 并且 key.equals(k)。

红黑树

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) pow(0.5, k) / factorial(k)). The first values are:

根据泊松分布实验发现，假设hashmap长度length为16，假设放入12（0.75*16）个数据到hashmap中，链表中存放8个节点的概率仅为0.00000006，而链表中存放1~7节点的概率为：

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006

红黑树 VS AVL

红黑树的平衡性并不如 AVL 树，它维持的只是一种大致上的平衡，并不严格保证左右子树的高度差不超过 l 。这导致在相同节点数的情况下，红黑树的高度可能更高，也就是说，平均查找次数会高于相同情况下的 AVL 树。在插入时，红黑树和AVL 树都能在至多两次旋转内恢复平衡。在删除时，由于红黑树只追求大致上的平衡，因此红黑树能在至多三次旋转内恢复平衡，而追求绝对平衡的 AVL 树，则至多需要 O(logn）次旋转。 AVL 树在插入与删除肘，将向上回溯确定是否需要旋转，这个回溯的时间成本最差可能为 O(logn），而红黑树每次向上回溯的步长为 2 ，回溯成本降低。面对频繁的插入和删除，红黑树更为合适；面对低频修改、大量查询时，AVL 树将更为合适。

key、Value 可否为 null

并发问题

(1) 数据丢失

新添加的元素直接放在 slot 槽上，如果两个线程同时执行到这里，那么一个线程的赋值就会被另一个覆盖掉：

Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);

(2) 循环死链

whilte (null != e) {
    Entry<K, V> next = e.next;
    e.next = newTable[5883];
    newTable[5883] = e;
    e = next;
}

TreeMap

如何保证有序

TreeMap 底层是红黑树结构，而红黑树本质是一颗二叉查找树。如下是 put 方法的部分细节即可：

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

LinkedHashMap

特点

循环双向链表
key 和 value 都允许为空
key 重复会覆盖
有序的
LinkedHashMap 是非线程安全的

Entry

LinkedHashMap 的 Entry<K,V> 继承了 HashMap.Node<K,V> 的数据结构，并且新增了 before，after 来维护链表插入/访问顺序。head 存储第一个头结点，tail 存储尾结点，accessOrder=true 链表维护访问顺序，false 链表维护插入顺序。这个访问顺序指的是按照最近被访问的Entry的顺序进行排序（从最近最少访问到最近最多访问）。基于这点可以简单实现一个采用**LRU（Least Recently Used）**策略的缓存。

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

get

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

ConcurrentHashMap

jdk1.8 之前，ConcurrentHashMap 采用分段锁（Segment），对不同段的 Entry 进行操作互不影响；
jdk1.8 之后，ConcurrentHashMap 直接使用Node数组+链表+红黑树，通过 synchronized 和 CAS 来保证并发的可靠性。

插入流程

在插入的時候，有多个地方用到了 synchronized，以 putVal 举例子，在发现想要插入的这个槽的 Node<K, V> 不为空的时候，就会去 synchronized (node) ，去锁住这个槽的链表的第一个 Node<K, V> 节点。

扩容流程

JDK7 获取集合大小流程

JDK8 获取集合大小流程

并发量较小，优先使用 CAS 直接更新 baseCount
更新 baseCount 冲突，则会认为进入到比较激烈的竞争状态，通过启用 counterCells 减少竞争，通过 CAS 的方式把总数更新情况记录在 counterCells 对应的位置上
如果更新 counterCells 上的某个位置出现了多次失败，则会通过扩容 counterCells 的方式减少冲突
当 counterCells 处在扩容期间时，会尝试更新 baseCount 值

对于元素总数的统计，逻辑就非常简单了，只需要让 baseCount 加上各 counterCells 内的数据，就可以得出哈希内的元素总数，整个过程不需要借助锁。

// 记录了元素总数值，CAS 更新这个值
private transient volatile long baseCount;
// 计数器
static final class CounterCell {}
// 竞争激烈，线程会把总数更新情况存放到这个数组中
// 竞争进一步加剧，会通过扩容减少竞争
private transient volatile CounterCell[] counterCells;

ArrayList

初始容量

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

new ArrayList() 时拥有的是一个空数组，在第一次 add 的时候，才会创建一个长度为 10 的数组。

如何扩容

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

扩容后新的数组长度为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍
然后使用 Arrays.copyOf 静态方法将旧数组里面的内容全部拷贝到新的数组里面

放满了会发生什么

抛出 OOM 异常：

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

多线程使用

数组越界异常
元素值覆盖和为空问题

elementData[size++] = e

transient

transient Object[] elementData;

ArrayList在序列化的时候会调用writeObject，直接将size和element写入ObjectOutputStream；反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。

为什么不直接用elementData来序列化，而采用上诉的方式来实现序列化呢？原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

fail-fast 机制

fail-fast 机制是一种对集合遍历操作时的错误检测机制，在遍历中途出现意料之外的修改时，通过 unchecked 异常暴力地反馈出来。这种机制经常出现在多线程环境下，当前线程会维护一个计数比较器，即 expectedModCount，记录已经修改的次数。在进入遍历前, 会把实时修改次数 modCount 赋值给 expectedModCount ,如果这两个数据不相等，则抛出异常。java.util 下的所有集合类都是 fail-fast，而 concurrent 包中的集合类都是 fail-safe 。

(1) masterList 集合元素个数的增加、删除，均会导致子列表的遍历、增加、删除，进而产生 fail-fast 机制。

List masterList = new ArrayList();
masterList.add("one");
masterList.add("two");
masterList.add("three");
masterList.add("cour");
masterList.add("five");

List branchList = masterList.subList(0, 3);

// 下面三行代码，会导致 branchList 操作会出现 ConcurrentModificationException 异常
masterList.remove(O);
masterList.add("ten");
masterList.clear();

(2) foreach 遍历，产生 fail-fast 异常

List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add("three");

for (String s : list) {
    if ("one".equals(s)) {
        list.remove(s);
    }
}

CopyOnWriteArrayList

底层数据结构

final transient ReentrantLock lock = new ReentrantLock();

private transient volatile Object[] array;

// 内部只能通过 getArray() 访问 array
final Object[] getArray() {
    return array;
}

添加元素

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

读取元素

private E get(Object[] a, int index) {
    return (E) a[index];
}

public E get(int index) {
    return get(getArray(), index);
}

参考

Java集合之LinkedHashMap实现与原理