Interview
Java 基础知识

集合基础

ArrayList 和 Array（数组）的区别？

ArrayList 内部基于动态数组实现，比 Array（静态数组） 使用起来更加灵活：

  • ArrayList 创建时不需要指定大小，而 Array 创建时必须指定大小。
  • ArrayList 会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。
  • ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。
  • ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。
  • ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add()、remove()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。

ArrayList 与 LinkedList 区别

  • 两者都不保证线程安全
  • ArrayList 底层是 Object 数组；LinkedList 底层是双向链表数据结构
  • 插入和删除的时间复杂度
  • ArrayList 支持随机元素访问，LinkedList 不支持
  • 内存空间占用：ArrayList 的空间浪费主要在 List 列表的结尾会预留一定的容量空间；而 LinkedList 的空间花费则体现在每个元素需要存放前后指针

ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

  • ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
  • ArrayDeque 不支持存储 null 数据，但 LinkedList 支持。
  • ArrayDeque 是在 JDK1.6 才被引入的，而 LinkedList 早在 JDK1.2 时就已经存在。
  • ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

这里列举其相关的一些要点：

  • PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
  • PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
  • PriorityQueue 是非线程安全的，且不支持存储 null 和 non-comparable 的对象。
  • PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

集合源码分析

ArrayList 扩容机制

初始化：构造函数默认分配一个空数组，当插入第一个数据时，数组容量默认 10

扩容：新数组的容量是就数组容量的 1.5 倍（newCapacity = oldCapacity + (oldCapacity >> 1)）

如果对已有的 ArrayList 进行大规模扩容，使用 ensureCapacity(int minCapacity) 方法手动扩容能减少自动扩容次数，提高性能。

LinkedList

LinkedList 为什么不能实现 RandomAccess 接口？LinkedList 底层数据结构是链表，不支持快速访问

HashMap 数组 + 链表/红黑树

HashMap 为了减少冲突，需要重写 hashCode() 以及 equals()，JDK1.8 的 hash 方法相比于 1.7 减少了扰动次数

数组长度默认为 16，加载因子 0.75，阀值为 16 * 0.75 = 12，当数组存储的键值对数量达到阀值， HashMap 就会触发扩容机制。在扩容过程中，数组的大小通常会增加到原来的两倍，然后HashMap会重新计算所有现存键的哈希值，以确定它们在新数组中的位置

链表长度阀值为 8

  • 当数组长度 < 64，链表长度大于 8 时
    • 数组扩容，长度翻倍
  • 当数组长度 >= 64，链表长度大于 8 时
    • 链表转红黑树

如果在扩容后某个索引位置上的红黑树节点数少于阈值（默认为 6），它会被转换回链表。

HashMap 存在并发问题

  • 数据不一致：同时增删由于没有同步措施，可能会导致一些更新操作丢失；
  • 数据丢失：并发插入数据，数据覆盖导致数据丢失；
  • 死循环：多线程扩容时，元素重新散列到新的桶位时，链表上的元素如果被反转并且多个线程交错运行，形成环形链表。

解法

  • 通过 Collections.synchronizedMap() 方法包装的 HashMap

    Map<K, V> map = Collections.synchronizedMap(new HashMap<K, V>());

  • ConcurrentHashMap，使用分段锁的概念，不同部分数据允许多个写操作同时进行

    ConcurrentMap<K, V> concurrentMap = new ConcurrentHashMap<K, V>();

ConcurrentHashMap

JDK1.7

Segment + HashEntry 数组 + 链表

Segment 默认长度是 16，即支持 16 个线程并发（默认初始化后不能改变）

put 方法获取给定索引的 Segment

  • 通过 (hash >>> segmentShift) & segmentMask 计算 Segment 的 index
  • 判断 Segment[index] 是否为空，空则初始化
    • 创建一个与 Segment[0] 的容量和负载因子一样的 HashEntry
    • 再次判断 Segment[index] 是否为空
      • 使用自旋 + CAS 将创建的 HashEntry 初始化 Segment[index]
  • 返回 Segment[index]

put 方法插入值

  • 通过 tryLock() 获取锁，获取不到则使用 scanAndLockForPut(key, hash, value) 获取锁
  • 根据上面的获取到具体的 Segment[index]，根据 hash() 计算出元素在 HashEntry 里面的索引 i（参考 HashMap 添加元素）
  • 判断 i 位置上的 HashEntry 是否存在
    • 不存在
      • 根据当前容量，判断是否扩容
      • 头插法插入数据
    • 存在
      • 判断链表当前元素 key 和 hash 值是否一样，一样则替换
      • 不一样则遍历链表，满足 key 和 hash 值一样则进行替换
        • 如果当前容量大于扩容阀值，小于最大容量，进行扩容
        • 头插法插入数据

rehash(HashEntry<K,V> node) 扩容

ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize，参数里的 node 会在扩容之后使用链表头插法插入到指定位置。

JDK1.8

Node 数组 + 链表/红黑树

putVal() 方法插入值

源码上的 tab 表示 Node 数组

首先记住前提是自旋 for (Node<K,V>[] tab = table;;)

  • 根据 key 计算出 hash 值
  • 首先判断 tab 即 Node 数组是否需要初始化（这步骤最多只走一次）
  • 根据 key 找到 Node 的位置即 tab[i]，如果当前位置为空，CAS 写入数据
  • 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
  • 利用 synchronized 写入数据（这部分其实和 HashMap 链表/红黑树插入数据一样），写完数据后需要判断链表是否需要树化

get() 方法

  • 根据 hash 值计算位置

  • 查找到指定位置，如果头节点就是要找的，直接返回它的 value

  • 如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，搜索红黑树

  • 如果是链表，遍历

在 Java 8 及以后版本的 ConcurrentHashMap 实现中，get() 方法及其相关操作中出现的节点（Node）的哈希值 eh 小于 0 被用作特殊情况的标识。具体来说，节点的哈希值被用于不仅仅存储实际的哈希码，还用于标识节点的状态或类型。当一个节点的哈希值 eh 小于 0 时，它可能表示几种特殊情况：

  1. MOVED (-1)：表示该节点是一个 forwarding node（转发节点），这在扩容过程中使用。当 ConcurrentHashMap 正在进行扩容操作时，原数组中的部分槽位可能会指向这种特殊节点。这个节点告诉访问它的线程，当前桶已经被处理，并且数据可能已经被移动到新的数组中。这是一个信号，告诉线程它可能需要在新的 table 数组中搜索键值对。

  2. TREEBIN (-2)：表示该节点是一个树形桶的根节点。在 ConcurrentHashMap 的实现中，当一个桶中的链表长度超过一定阈值时，链表会被转换成红黑树，以提高搜索效率。TREEBIN 标记说明了这个桶已经被组织成了红黑树结构，对该桶的访问应当使用树相关的操作来进行。

  3. RESERVED (-3)：这是一个用于标记节点的保留值，用于未来的扩展或特殊操作，但在 JDK 的当前实现中可能不直接使用。

在 get() 方法中处理节点时，检查节点的哈希值是否小于 0 是区分这些情况的关键。这允许 ConcurrentHashMap 通过单一的节点数据结构来支持多种数据组织形式和并发操作，同时保持高效的访问和搜索性能。

通过这种设计，ConcurrentHashMap 能够在保持线程安全的同时，最小化锁的使用，实现高并发下的高性能读写操作。这是通过一系列精心设计的并发控制策略和数据结构调整来实现的，其中节点哈希值的特殊用途就是这些策略之一。

LinkedHashMap

LRU 缓存

Least Recently Used，最近最少使用，确保当存放的元素超过容器容量时，将最近最少访问的元素移除。实现思路：

  • 继承 LinkedHashMap;
  • 构造方法中指定 accessOrder 为 true ，这样在访问元素时就会把该元素移动到链表尾部，链表首元素就是最近最少被访问的元素；
  • 重写 removeEldestEntry 方法，该方法会返回一个 boolean 值，告知 LinkedHashMap 是否需要移除链表首元素（缓存容量有限）。
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
 
    /**
     * 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

什么是 LinkedHashMap？

LinkedHashMap 是 Java 集合框架中 HashMap 的一个子类，它继承了 HashMap 的所有属性和方法，并且在 HashMap 的基础重写了 afterNodeRemoval、afterNodeInsertion、afterNodeAccess 方法。使之拥有顺序插入和访问有序的特性。

LinkedHashMap 如何按照插入顺序迭代元素？

LinkedHashMap 按照插入顺序迭代元素是它的默认行为。LinkedHashMap 内部维护了一个双向链表，用于记录元素的插入顺序。因此，当使用迭代器迭代元素时，元素的顺序与它们最初插入的顺序相同。

LinkedHashMap 如何按照访问顺序迭代元素？

LinkedHashMap 可以通过构造函数中的 accessOrder 参数指定按照访问顺序迭代元素。当 accessOrder 为 true 时，每次访问一个元素时，该元素会被移动到链表的末尾，因此下次访问该元素时，它就会成为链表中的最后一个元素，从而实现按照访问顺序迭代元素。

LinkedHashMap 如何实现 LRU 缓存？

将 accessOrder 设置为 true 并重写 removeEldestEntry 方法当链表大小超过容量时返回 true，使得每次访问一个元素时，该元素会被移动到链表的末尾。一旦插入操作让 removeEldestEntry 返回 true 时，视为缓存已满，LinkedHashMap 就会将链表首元素移除，由此我们就能实现一个 LRU 缓存。

LinkedHashMap 和 HashMap 有什么区别？

LinkedHashMap 和 HashMap 都是 Java 集合框架中的 Map 接口的实现类。它们的最大区别在于迭代元素的顺序。HashMap 迭代元素的顺序是不确定的，而 LinkedHashMap 提供了按照插入顺序或访问顺序迭代元素的功能。此外，LinkedHashMap 内部维护了一个双向链表，用于记录元素的插入顺序或访问顺序，而 HashMap 则没有这个链表。因此，LinkedHashMap 的插入性能可能会比 HashMap 略低，但它提供了更多的功能并且迭代效率相较于 HashMap 更加高效。

CopyOnWriteArrayList

  • 写操作（如添加、删除元素）会先复制出一个新的数组，然后在新数组上进行修改，操作完成后再将原数组引用指向新数组。这样读操作可以安全地访问原数组，而不会受到写操作的影响。
  • 读操作可以直接访问底层数组，无需加锁，因此读操作非常高效。

适合读多写少的并发场景。写多的话，内存消耗和数组复制的时间开销比较大。

JUCRedis