Java面经——Java集合

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 3.6k 阅读时长 ≈ 7 分钟

HashMap详解

一 映射

1. hash

在取模运算之前，先将hashcode进行一次hash。该函数的作用是通过异或将hashcode的高位和低位混合，使得低位的随机性增大，让数据元素更加均衡的分布，减少碰撞。

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

2. 取模

然后进行取模：hash & (length - 1)

为什么是 & ？： 当length是2的n次方时，hash % length 等于 hash & (length - 1)。

二 底层实现

JDK8之前：数组 + 链表。

JDK8：数据 + 链表/红黑树。当链表长度大于阈值（默认为8）且数组长度不小于64时，会转为红黑树。

三 扩容机制

hashmap的默认容量capacity为16，当其中的元素数量超过阈值threshold（容量*负载因子）后，会触发扩容。

每次扩容都是原来的容量的两倍，这使得容量始终为2的幂次方（即使通过构造函数指定非 2 的幂值，HashMap 也会自动调整为最近的 2 的幂）。

如果旧容量已经达到 HashMap 支持的最大容量 MAXIMUM_CAPACITY（2^30），就不会扩容，同时将阈值设为 Integer.MAX_VALUE（2^31-1），这样就不会再触发扩容。

如果容量小于16，会自动设为16。

扩容时，会创建一个新数组，将旧数组的每个元素重新计算hash后，填入新数组。

由于hashmap的容量始终为2的幂次方，映射函数为hash & (length - 1)，因此会产生这样一个性质：那么一个元素在扩容被转移时，要么留在原位置（index = oldIndex），要么迁移到原位置+旧容量（index = oldIndex + oldCap）。在jdk8中，元素转移时利用了这个性质，直接利用 (e.hash & oldCap) == 0 判断（即判断哈希值在旧容量的最高位是否为0），如果成立则index = oldIndex，否则index = oldIndex + oldCap。

四 线程不安全

1. 并发下扩容死循环（jdk8前）

对于链表中元素的转移，在jdk8前使用的是头插法，即假如原来的一个桶中的元素是1->3->7，那么转移后结果是7->3->1（假如还在一个桶中）。而jdk8后使用的是尾插法，这样元素的顺序并不会改变。

在jdk7时，假设初始链表为 Entry1 → Entry2，两个线程同时扩容：

  1. 线程 1 迁移 Entry1 到新数组，此时 Entry1.next = null，但未完成迁移就被挂起。
  2. 线程 2 完成整个链表的迁移，新链表顺序变为 Entry2 → Entry1（头插法）。
  3. 线程 1 恢复后继续迁移，此时它看到的链表已被线程 2 修改，导致 Entry1.next = Entry2，而 Entry2.next = Entry1，形成环形链表 Entry1 ⇄ Entry2。

2. 多线程put导致元素丢失

两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。

  1. 不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入1操作。

  2. 随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。

还有一种情况是这两个线程同时 put 操作导致 size 的值不正确，进而导致数据覆盖的问题：

  1. 线程 1 执行 if(++size > threshold) 判断时，假设获得 size 的值为 10，由于时间片耗尽挂起。
  2. 线程 2 也执行 if(++size > threshold) 判断，获得 size 的值也为 10，并将元素插入到该桶位中，并将 size 的值更新为 11。
  3. 随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。
  4. 线程 1、2 都执行了一次 put 操作，但是 size 的值只增加了 1，也就导致实际上只有一个元素被添加到了 HashMap 中。

3. put 和 get 并发时会导致 get 到 null

  1. 线程 1 执行 put 时，因为元素个数超出阈值而导致出现扩容
  2. 线程 1 执行完 table = newTab
  3. 线程 2 此时执行 get，由于元素还没有转移完成，get到null

CurrentHashMap详解

一 底层实现

JDK1.7：分段的数组 + 链表。ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。一般分为16段，因此最大并发数为16。

JDK1.8：Node数组 + 链表/红黑树。不再使用段的概念，而是使用 CAS + Synchronized保证并发安全。锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

二 ConcurrentHashMap 能保证复合操作的原子性吗？

ConcurrentHashMap 是线程安全的，意味着它可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况。但是，这并不意味着它可以保证所有的复合操作都是原子性的。

例如先判断某个键是否存在containsKey(key)，然后根据结果进行插入或更新put(key, value)。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。

那如何保证 ConcurrentHashMap 复合操作的原子性呢？

ConcurrentHashMap 提供了一些原子性的复合操作，如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge等。这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中。

三 ConcurrentHashMap 为什么 key 和 value 不能为 null？

ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性。null 是一个特殊的值，表示没有对象或没有引用。如果你用 null 作为键，那么你就无法区分这个键是否存在于 ConcurrentHashMap 中，还是根本没有这个键。同样，如果你用 null 作为值，那么你就无法区分这个值是否是真正存储在 ConcurrentHashMap 中的，还是因为找不到对应的键而返回的。

与此形成对比的是，HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。如果传入 null 作为参数，就会返回 hash 值为 0 的位置的值。单线程环境下，不存在一个线程操作该 HashMap 时，其他的线程将该 HashMap 修改的情况，所以可以通过 contains(key)来做判断是否存在这个键值对，从而做相应的处理，也就不存在二义性问题。

也就是说，多线程下无法正确判定键值对是否存在（存在其他线程修改的情况），单线程是可以的（不存在其他线程修改的情况）。或者是单线程下可以容忍歧义，而多线程下无法容忍。

CopyOnWriteArrayList详解

在JDK1.5之前，实现线程安全的List为Vector，但是Vector是一个增删改查都要加synchronized锁的老旧集合，已经被淘汰。在JDK1.5中，引入了一个新的线程安全的List——CopyOnWriteArrayList。

CopyOnWriteArrayList的读取操作是完全不需要加锁的，同时写操作也不会阻塞读操作，只有写写互斥，极大地提高了性能。

CopyOnWriteArrayList线程安全的核心在于其采用了 写时复制（Copy-On-Write） 的策略，当需要修改（ add，set、remove 等操作） CopyOnWriteArrayList 的内容时，不会直接修改原数组，而是会先创建底层数组的副本，对副本数组进行修改，修改完之后再将修改后的数组赋值回去，这样就可以保证写操作不会影响读操作了。

不过，写时复制机制并不是银弹，其依然存在一些缺点，下面列举几点：

  1. 内存占用：每次写操作都需要复制一份原始数据，会占用额外的内存空间，在数据量比较大的情况下，可能会导致内存资源不足。
  2. 写操作开销：每一次写操作都需要复制一份原始数据，然后再进行修改和替换，所以写操作的开销相对较大，在写入比较频繁的场景下，性能可能会受到影响。
  3. 数据一致性问题：修改操作不会立即反映到最终结果中，还需要等待复制完成，这可能会导致一定的数据一致性问题。
  4. ……