xiaoyh 的个人博客

一个只会敲代码的咸鱼

0%

面试 —— Java 容器

发表于 更新于 分类于

容器包括 Collection 和 Map 两种，Collection 存储对象的集合，而 Map 存储着键值对的集合。

Collection（接口）

Collection 下也包括 List 和 Set 两种：

List（接口）

List 是非常常用的数据类型，是有序的的 Collection。这里的有序指的是存入与取出的顺序一样，而不是指排序。

一共有三个实现类：ArrayList、Vector、LinkedList。

ArrayList

ArrayList 是最常用的 List 实现类，内部是通过数组实现的。

创建 ArrayList 时，会创建一个数组用于存放元素，这个初始数组的大小叫做默认初始容量。ArrayList 的默认初始容量是 10 。

当数组元素的数量要超过容量时，就需要扩容。扩容的方法是创建一个当前容量的 1.5 倍的新数组，然后将原数组的数据复制到新数组中。这个 1.5 也叫做扩容因子。

1
2
3
4
// ArrayList 源码
// 加上自己的一半，就是 1.5 倍
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

因为 ArrayList 的本质就是数组，所以查找很快，插入删除很慢。

Vector

Vector 与 ArrayList 一样也是通过数组实现的，不过它是线程安全的（通过加 synchronized 关键字，也就是上锁）。

Vector 的默认初始容量也为 10，但是扩容因子为 2 。

LinkedList

LinkedList 是用带头尾指针的双向链表实现的，很适合在头部和尾部做插入和删除，也就是作为栈、队列和双向队列，不适合随机查找。

CopyOnWriteArrayList

这是一个不常用的 List 的实现类，但是是线程安全的。

CopyOnWriteArrayList 将读写分离：写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。

写操作需要加锁，防止并发写入时导致写入数据丢失。

写操作结束之后需要把原始数组的引用指向新的复制数组。

优点：在写操作的同时允许读操作，大大提高了读操作的性能。

缺点：

  • 由于需要复制数组，会占用两倍于容量的内存
  • 读操作不能读取实时性的数据，因为部分写操作的数据还未同步

因此 CopyOnWriteArrayList 适合读多写少，对内存占用和实时性要求不高的场景。

Set（接口）

Set 即数学意义上的集合，其元素不可重复且无序（存入和取出的顺序不一定相同）。

Set 都是基于 Map 实现的。

HashSet

HashSet 是通过 HashMap 实现的（所以详情看 HashMap），所有 key 都映射到 HashSet 的一个名为 PRESENT 的 Object 全局常量对象。

相同的对象通过同样的哈希算法会映射到数组上的同一个索引，通过此特性可以实现去重的功能。

TreeSet

TreeSet 是基于 TreeMap 实现的（所以详情），在 Set 的基础上加入了可排序的特性（不是有序，TreeSet 仍然不能保证存入和取出的顺序相同），即存入的元素可以按照规定的顺序排放。

因为是基于红黑树，所以 TreeSet 的效率要比 HashSet 慢。

LinkedHashSet

LinkedHashSet 是通过 LinkedHashMap 来实现（所以详情看 LinkedHashMap）。

LinkedHashSet 在 HashSet 的基础上额外维护一个双向链表，记录了元素的插入顺序，在 Set 的基础之上实现了有序（即元素插入与取出的顺序相同）的特性。

Queue（接口）

即数据结构中的队列，这是一个不太常用的接口。

LinkedList（队列）

LinkedList 也继承了它，因为其可以作为队列的实现。

PriorityQueue

PriorityQueue 即优先队列，是通过堆实现的，默认是小顶堆。优先队列会一直保证优先级最大的元素在队头。

虽然堆的逻辑结构是一棵完全二叉树，但是它的物理结构仍然是数组。

其默认初始容量为 11。当数组元素的数量要超过容量时也会扩容，但是当目前的容量小于 64 的时候，新数组的大小是两倍的原数组的大小 + 2；当大于等于 64 的时候，扩容因子与 ArrayList 一样为 1.5 。

1
2
3
4
5
// PriorityQueue 源码
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                  (oldCapacity + 2) :
                                  (oldCapacity >> 1));

对于优先队列的入队与出队，实际上就是往堆里插入元素和删除头节点，都需要操作完后调整堆，因此都是 O(logn) 的时间复杂度。

Map（接口）

即键值对的集合，在需要维护映射关系的时候使用。key 不能重复，且不保证有序性。

HashMap（重点）

HashMap 是最常用的 Map 实现类，内部是通过哈希表实现的。

哈希表的本质也是数组，其默认初始容量为 16 ，扩容因子是 2 即扩容后容量翻倍。除此之外，还有一个负载因子 0.75，意思是当 HashMap 的元素个数超过容量的 75% 时开始扩容，而不是从即将装满时开始（从这里可看出，“即将装满”加载因子为 1）。

HashMap 的数组实际上是 Map.Entry 的数组，Entry 是 Map 的内部接口，是对键值对的抽象。

当 HashMap 添加一组键值对（key, value）时，会先取出 key 的 hashcode ，然后把 hashcode 与自己的右移 16 位做异或，其结果作为第一步的 hash 值（我称之为 hash1）。若 key 为 null，则直接为 0 。

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么作为第一步的 hash 值呢？因为这时候的 hash 值还是有可能超出数组的容量，比如 Integer 的 hashcode 就是自己的数值大小，那么至少在 65535 以内，这个 hash 值都是自己本身（与 0 异或），显然这个 hash 的数据范围还是太大。

第二步，取出当前 HashMap 的容量也就是数组的长度 n，将 n - 1 与 hash 做与运算即对 n 取模得到最终的 hash 值（我称之为 hash2)，这样直接将 hash 值的范围缩到数组的范围之内。

这也是为什么默认初始容量设为 16，扩容因子是 2 的原因，因为要保证 HashMap 的容量是 2 的幂，这样与 n - 1 做与运算才等价于对 n 取模，提高哈希算法的效率。

所以也可以总结出 HashMap 的 hash 算法为：hashcode ^ (hashcode >>> 16) & (n - 1) 。

当 key 的 hash 值最终还是碰撞了的话，就采用拉链法即拉一条链表，解决碰撞问题。

哈希洪水攻击

对于往哈希表连续插入 n 个数据：

  • 如果这些元素的键（Key）极少发生碰撞，这项任务就只需 O(n) 的时间。

  • 如果这些键频繁发生碰撞，这项任务就需要 O(n²) 的时间。

针对哈希表的最坏情况，只要了解哈希表的哈希算法，就可以强行构造一系列相同键值的数据，然后发送到服务器，让服务器把所有资源都浪费在处理这个最差情况上。

Java 的 hashcode 算法众所周知，所以 Java 的 HashMap 存在着很大的被攻击的风险。不过在 JDK1.8 之后，HashMap 添加了红黑树的设计。

以 7 为边界点，当碰撞的节点个数超过 7 的时候，如果容量小于 64 ，则扩容，否则转化为红黑树。当碰撞的节点个数低于 7 的时候，又会转换回链表。

红黑树优化了 HashMap 的插入效率，将最坏情况的时间复杂度降低至 O(nlogn)，有效地避免了哈希洪水攻击。

不过，在扩容的时候，因为有可能导致 key 的 hash2 改变（因为 n 变大了），所以在拷贝原数组时，还需要遍历每个节点链表，查看其 hash2 的值是否改变，然后把所有发生改变的节点组成一个链表或者一棵红黑树，转移到新的位置上。

HashMap 常见问题

为什么要对 key 的 hashcode 做异或操作

首先绝大多数情况下，HashMap 的容量都小于 2 的 16 次方即 65536。那么在这一情景下如果直接将 hashcode 对容量做取模运算，大于 65536 的 hashcode 其高位特征就无法体现出来。为了保有低位与高位的特征，因此将 hashcode 与其高 16 位做异或操作。

之所以用 ^ 是因为它会使得结果更加均匀（真值表结果 2 个 0，2 个 1），用 & 或者 | 会导致结果偏向 0 或 1（真值表结果 0 与 1 个数不相等）

为什么负载因子是 0.75

扩容因子过大会造成哈希桶中的链表长度过大，当发生碰撞时的开销就更高；若过小，那么哈希表中元素个数还不多时就会扩容，虽然 crud 效率增加了但也会造成空间资源的浪费。

在理想情况下，当以 0.75 作为负载因子时，哈希桶中节点个数遵循平均值为 0.5 的泊松分布，哈希桶中元素为 7 个的概率已不到一百万分之一，也就意味着当负载因子为 0.75 时哈希桶中链表长度几乎不可能超过 7 。

当链表节点个数超过 7 时一定换转换成红黑树吗

不一定，在 HashMap 中的树化方法 treeifyBin 中的开头有：

1
2
3
4
5
6
final void treeifyBin(Node<K,V>[] tab, int hash) {
    // ...
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // ...
}

在 HashMap 中有一个 MIN_TREEIFY_CAPACITY 最小树化容量，大小为 64 。这意味着，若当前 HashMap 的容量小于 64 ，链表节点个数超过 8 时不会树化而是进行扩容。

HashMap 的扩容细节

HashMap 的扩容是通过 resize 方法实现的，这个方法的作用是对 HashMap 做初始化（若未初始化）或者扩容。

扩容时，HashMap 会创建两倍于原数组大小的数组，然后遍历其内部的数组，并将所有节点的 hash 值重新计算。不过由于每次扩容只扩容为原来的两倍，所以对于同一个哈希桶中的元素在对新容量取模的时候也只会产生两个结果，要么留在原地，要么去新位置。

比如 1, 33, 65, 97, … 在容量为 32 的时候都是放在同一个桶中（索引为 1），当扩容后，有的数字还是留在原地，但有的数字会放在索引为 33 的桶中。除此之外不会再有其他的地方。

正是根据此特性，HashMap 的扩容实现是维护了两条有头尾指针的单链表，然后在遍历某个桶的链表时依据 hash 值是否发生变化来分别尾插至不同的链表，最后再将这两条链表置于新数组上。

在 JDK1.8 以后哈希桶中可能有红黑树，对红黑树的扩容得维护两条双向链表以及两个变量记录这两条链表的长度。当红黑树遍历完后，新链表的长度若小于 7 就解树化转换成普通的链表，否则就把该双向链表调整为红黑树。

HashMap 的初始容量不是 2 的幂会如何

可以通过 HashMap 的构造方法指定 HashMap 的初始容量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public HashMap(int initialCapacity, float loadFactor) {
    // ...
    this.threshold = tableSizeFor(initialCapacity);
}

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

根据如上代码，HashMap 会判断初始容量是否为 2 的幂，如果不是，就把它通过位运算变成离它最近的 2 的幂

为什么用红黑树而不是 AVL 树

红黑树对子树的高度差异要求没有 AVL 树严格，因此其查找效率较 AVL 树低，但红黑树正是通过牺牲了对高度的要求来换取增删节点时的旋转次数的降低，因此对于插入删除操作而言，红黑树的效率更高。所以在插入删除较多的情景应该采用红黑树。

TreeMap

基于红黑树实现，为 Map 添加了可排序的功能（红黑树的中序遍历）

这个规定的顺序不一定是顺序或者逆序，可以按照自己的需求去添加比较器的规则。比较器返回负数、零、正数分别对应于作为比较元素的左边的元素小于、等于、大于右边的元素。

因为红黑树无论插入还是查找都是O(logn)，所以效率较其他的 Map 实现低（其他的 Map 是哈希表）

LinkedHashMap

LinkedHashMap 在 HashMap 的基础之上，加入了双向链表，用来维护元素插入的顺序，为 Map 添加了有序性。

LinkedHashMap 的 Entry 较父类的多了两个指针：before，after，分别指向在其之前和之后插入的节点。

LinkedHashMap 由于继承自 HashMap，所以其底层实现仍然是数组。默认初始容量、加载因子与扩容因子与 HashMap 的一致。

LinkedHashMap 和 LRU 算法

LRU 即最近最少使用，是一种常用的缓存淘汰算法，淘汰掉最近最少用到的缓存。

LinkedHashMap 的特性，让其很适合做 LRU 算法。

当把标志位 accessOrder 置为 true 时，表示双向链表中的元素按照访问的先后顺序排列，LinkedHashMap 会在调用 get 方法访问节点时，将该节点置于双向链表尾部，这样在头部的节点自然就是最近最少使用的节点了。

HashTable

和 HashMap 类似，但它是线程安全的，也是采用 synchronized 关键字。

其默认初始容量为 11，加载因子为 0.75，扩容因子为 2 倍 + 1 。

它是遗留类，不应该去使用它，而是使用 ConcurrentHashMap 来支持线程安全，ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。

ConcurrentHashMap

ConcurrentHashMap 在 JDK1.8 之后放弃了 Segment 这种臃肿的实现，而采用了 CAS + synchronized 的方式。

比如 ConcurrentHashMap 的初始化在第一次执行 put 操作时才进行。其中的核心就是 U.compareAndSwapInt 方法，通过 CAS 来保证有且仅有一个线程能够进入数组初始化的执行体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // 已有线程在初始化，让出 CPU 
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2); // 0.75 的负载因子
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

ConcurrentHashMap 的扩容是支持多线程并发扩容的，所以扩容效率很高。扩容的核心就在于将旧的 table 数组中的数据迁移到新的数组中来，之所以能并发扩容就在于 ConcurrentHashMap 将现有的数据分成了几部分，每个线程领一个自己的部分。这个部分的长度 stride 至少为 16 ，取决于 CPU 的个数以及扩容前的容量。

以一个长度 32 的 ConcurrentHashMap 扩容到 64 为例。对于扩容的单个线程来说，每次复制都是从尾部开始，一个哈希桶复制完毕后会在这个位置放置一个ForwardingNode 节点，表明这个节点已经处理过了。

一个线程刚开始扩容时会通过 CAS 操作将 transferIndex = 16; i = 31; bound = 16; 其中 i 表示当前线程的起始位置，bound 表示线程的结束为主。transferIndex 决定了下一个线程的起始位置。因此第一个线程从 31 开始遍历，第二个从 15 开始遍历。每当开始迁移一个桶中的元素的时候，线程会锁住当前桶。假设这时候正好有 get 请求过来仍旧在旧的列表中访问，如果是插入、修改、删除、合并、compute 等操作时遇到 ForwardingNode，当前线程会加入扩容大军帮忙一起扩容，扩容结束后再做元素的更新操作。

扩容结束后，会再从尾到头检查一遍，因为有可能靠头部的线程迁移完了后面的线程还未迁移完毕。

WeakHashMap

WeakHashMap 的 Entry 继承自 WeakReference，被 WeakReference 关联的对象在下一次垃圾回收时会被回收。

WeakHashMap 主要用来实现缓存，通过使用 WeakHashMap 来引用缓存对象，由 JVM 对这部分缓存进行回收。