Java集合框架

• Java集合框架
  • 1.阻塞队列的阻塞是什么含义？
  • 2.阻塞队列的实现方式？
  • 3.线程不安全的集合变成线程安全的方法？
  • 4.HashMap的底层数据结构?
  • 5.为什么 HashMap 是线程不安全的？
  • 6.平衡二叉树
    • AVL 树
    • 红黑树
  • 7.HashMap 的 put 流程
  • 8.只重写 equals 没重写 hashcode，map put 的时候会发生什么?
  • 9.为什么要用高低做异或运算？为什么非得高低 16 位异或？
  • 10.为什么 HashMap 的容量是 2 的倍数呢？hashCode 对数组长度取模定位数组下标的优化策略？
  • 11.map 集合在使用时候一般都需要写容量值？为什么要写？扩容机制？
  • 12.红黑树转回链表的阈值为什么默认是6而不是8？
  • 13.JDK8对HashMap的实现原理做了哪些优化？
  • 14.HashMap和TreeMap的区别？

Java集合框架

1.阻塞队列的阻塞是什么含义？

阻塞队列的“阻塞”指的是当生产者往队列中添加元素时，如果队列已满，则生产者的添加操作会被阻塞，直到队列中有空闲空间；同样地，当消费者从队列中移除元素时，如果队列为空，则消费者的移除操作会被阻塞，直到队列中有新的元素被添加进来。这种机制确保了在多线程环境下队列的操作是线程安全的，并且能够有效地协调生产者和消费者之间的同步问题。

2.阻塞队列的实现方式？

Java中的BlockingQueue接口定义了阻塞队列的行为，并且Java并发库java.util.concurrent提供了多种BlockingQueue的具体实现。

ArrayBlockingQueue：

基于数组结构的有界阻塞队列。 固定大小的队列，当队列满时，生产者线程会被阻塞，直到队列中的元素被消费掉。 当队列空时，消费者线程会被阻塞，直到队列中有新的元素加入。

LinkedBlockingQueue：

基于链表结构的阻塞队列。 可以指定容量大小，如果不指定，默认为Integer.MAX_VALUE。 当队列满时，生产者线程会被阻塞；当队列空时，消费者线程会被阻塞。

PriorityBlockingQueue：

具有优先级的无界阻塞队列。 类似于PriorityQueue，但是加入了阻塞的功能。 不会阻塞生产者线程，但是可以保证具有较高优先级的元素会被先消费。

DelayQueue：

使用Delayed类型的元素的无界阻塞队列。 队列中的元素只有在其延迟过期后才能被消费者线程消费。 生产者线程不会被阻塞，但消费者线程可能会因为没有到期的元素而被阻塞。

SynchronousQueue：

不存储元素的阻塞队列。 每个插入操作必须等待另一个线程的对应移除操作，反之亦然。 实际上不存储任何元素，更多地用于线程间的数据交换。

LinkedTransferQueue：

基于链表结构的无界阻塞队列。 提供了更强的传递语义，允许生产者直接将元素传给消费者，如果消费者不存在则放入内部队列。 支持传递操作，即生产者可以直接将元素传递给消费者线程

3.线程不安全的集合变成线程安全的方法？

使用synchronizedXxx()方法：

java.util.Collections类提供了一系列静态方法，如synchronizedList(), synchronizedSet(), synchronizedMap()等，可以将线程不安全的集合包装成线程安全的集合。 例如，对于ArrayList，可以使用Collections.synchronizedList(new ArrayList<>())将其转换为线程安全的列表。

使用同步容器：

Java标准库提供了一些内置的线程安全容器，如Vector和Hashtable。 Vector是线程安全的List实现，而Hashtable是线程安全的Map实现。

显式同步：

可以手动对集合的操作进行同步控制，比如在访问集合前加上synchronized关键字，并使用集合对象本身或其外部的对象作为锁。 示例代码如下：

List list = new ArrayList<>();
Object lock = new Object();
synchronized(lock) {
    // 在这里执行对list的安全操作
}

使用并发集合：

Java并发包java.util.concurrent提供了线程安全的集合实现，如ConcurrentHashMap, CopyOnWriteArrayList, CopyOnWriteArraySet等。 这些集合在设计时就考虑到了并发访问的问题，因此不需要额外的同步措施。

使用ReentrantLock或其他锁机制：

可以使用更高级的锁机制，如ReentrantLock，来替代synchronized关键字，以获得更细粒度的锁控制。

使用不可变集合：

创建不可变集合，一旦创建就不能改变，这样也避免了并发修改的问题。 不可变集合可以被认为是线程安全的，因为它们的状态不会改变。

4.HashMap的底层数据结构?

JDK 8 中 HashMap 的数据结构是数组+链表+红黑树。

HashMap 的核心是一个动态数组（Node[] table），用于存储键值对。这个数组的每个元素称为一个“桶”（Bucket），每个桶的索引是通过对键的哈希值进行哈希函数处理得到的。

当多个键经哈希处理后得到相同的索引时，会发生哈希冲突。HashMap 通过链表来解决哈希冲突——即将具有相同索引的键值对通过链表连接起来。

不过，链表过长时，查询效率会比较低，于是当链表的长度超过 8 时（且数组的长度大于 64），链表就会转换为红黑树。红黑树的查询效率是 O(logn)，比链表的 O(n) 要快。数组的查询效率是 O(1)。

链表转换为红黑树的条件

链表长度：当单个桶（bucket）中的链表长度达到 8 时，该链表会被转换为红黑树。 最小树化容量：HashMap 的总容量（桶数组大小）必须至少为 64。如果 HashMap 的容量小于 64，即使链表长度达到 8，也不会进行树化，而是会选择扩容。

红黑树转换为链表的条件

树节点数量：当红黑树节点元素小于等于 6 时，红黑树会被转换回链表形式。这是因为，在小数据量时，链表的效率更高。

转换逻辑

树化：当一个桶中的链表长度达到 8，并且 HashMap 的容量大于等于 64 时，这个链表会被转换成红黑树。这样做的目的是为了减少链表的长度，从而提高查找的效率。红黑树的平均查找长度是 O(log n)，相比于链表的 O(n)，在链表长度较长时性能更好。

链表化：当红黑树中的节点数量减少到 6 或更少时，红黑树会被转换回链表。这是因为对于少量的数据，链表的开销较小，转换为链表可以减少不必要的内存占用和管理开销。

扩容机制

扩容：在某些情况下，如果 HashMap 的容量不足以容纳更多的元素，或者链表长度达到树化阈值但容量不足时，HashMap 会进行扩容。扩容操作会将容量加倍，并重新散列所有的元素。

当向 HashMap 中添加一个键值对时，会使用哈希函数计算键的哈希码，确定其在数组中的位置，哈希函数的目标是尽量减少哈希冲突，保证元素能够均匀地分布在数组的每个位置上。

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

当向 HashMap 中添加元素时，如果该位置已有元素（发生哈希冲突），则新元素将被添加到链表的末尾或红黑树中。如果键已经存在，其对应的值将被新值覆盖。

当从 HashMap 中获取元素时，也会使用哈希函数计算键的位置，然后根据位置在数组、链表或者红黑树中查找元素。

HashMap 的初始容量是 16，随着元素的不断添加，HashMap 的容量（也就是数组大小）可能不足，于是就需要进行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。

扩容后的数组大小是原来的 2 倍，然后把原来的元素重新计算哈希值，放到新的数组中。

总的来说，HashMap 是一种通过哈希表实现的键值对集合，它通过将键哈希化成数组索引，并在冲突时使用链表或红黑树来存储元素，从而实现快速的查找、插入和删除操作。

5.为什么 HashMap 是线程不安全的？

修改操作非原子性

HashMap 的修改操作（如 put 和 remove）并没有使用锁来保证原子性，这意味着在多线程环境中，这些操作可能会被中断，导致数据不一致。 例如，在 put 操作中，HashMap 需要计算哈希值、找到桶的位置、插入键值对等步骤，这些步骤在多线程环境下可能被其他线程干扰。

扩容时的竞态条件

当 HashMap 达到其容量限制时，它会进行扩容操作，这个过程涉及到重新散列所有已存在的键值对。 如果多个线程同时触发扩容操作，可能会导致竞态条件，其中一个线程的扩容操作可能被另一个线程覆盖，从而导致数据丢失或不一致。

链表或红黑树操作的不一致性

当多个线程同时操作同一个桶中的链表或红黑树时，如果没有适当的同步机制，可能会导致链表或红黑树的结构被破坏，进而导致数据丢失或无限循环等问题。

可见性问题

HashMap 中的变量（如容量、阈值等）在多线程环境中如果没有正确的同步机制，可能会导致线程间的可见性问题，即一个线程修改的数据不能被另一个线程及时看到。

解决方案

为了使 HashMap 在多线程环境中安全使用，可以采取以下措施：

使用 Collections.synchronizedMap：将 HashMap 包装成线程安全的集合。

使用 ConcurrentHashMap：这是 HashMap 的线程安全版本，专为多线程环境设计。 显式同步：在访问 HashMap 时手动加锁，确保同一时刻只有一个线程能够修改 HashMap。

6.平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，其中任意节点的左右子树高度差不超过一定范围。常见的平衡二叉树有 AVL 树和红黑树。

AVL 树

AVL 树是一种自平衡的二叉查找树，它通过在每个节点上存储一个平衡因子（balance factor）来保持树的平衡。平衡因子定义为左右子树的高度差，它可以是 -1、0 或 1。

AVL 树的基本操作

插入操作：

插入新节点。 通过旋转操作来保持平衡。

删除操作：

删除指定节点。 通过旋转操作来保持平衡。

查找操作：

在 AVL 树中查找指定键值的节点。

当平衡二叉树（如 AVL 树）的平衡性被破坏时，通常是因为插入或删除了一个节点，导致某些节点的平衡因子（左子树高度与右子树高度之差）的绝对值超过了允许的范围（对于 AVL 树来说是 1）。为了恢复平衡，需要执行一系列旋转操作。

恢复平衡的步骤

确定破坏点：找到第一个平衡因子绝对值大于 1 的节点。

识别破坏模式：根据破坏点与其子节点的关系，确定破坏模式。

执行相应的旋转操作：根据破坏模式执行单旋转或多旋转（双旋转）。

常见的破坏模式和对应的旋转操作

LL（左左）：破坏点的左子节点有一个更高的左子树。

RR（右右）：破坏点的右子节点有一个更高的右子树。

LR（左右）：破坏点的左子节点有一个更高的右子树。

RL（右左）：破坏点的右子节点有一个更高的左子树。

旋转操作

单旋转：当破坏模式为 LL 或 RR 时，执行一次旋转即可恢复平衡。

双旋转：当破坏模式为 LR 或 RL 时，首先对破坏点的子节点执行一次旋转，然后对破坏点执行一次旋转。

LL模式的旋转操作

RR模式的旋转操作

LR模式的旋转操作

RL模式的旋转操作

删除的旋转操作

红黑树

红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它通过特定的颜色标记以及旋转和重新着色操作来维持树的近似平衡，从而确保树的高度保持在(O(\log n))，这里(n)是树中节点的数量。这使得红黑树能够高效地执行查找、插入和删除操作。

红黑树的特点

红黑树的每个节点都有一个颜色属性，可以是红色（red）或黑色（black），并且满足以下性质：

节点属性：每个节点要么是红色的，要么是黑色的。

根节点：根节点总是黑色。

叶子节点：所有叶子节点（NIL节点，空节点）都是黑色的。

红色节点：两个红色节点之间不能相邻，即一个红色节点的父节点和子节点必须是黑色。

黑色高度：从任一节点到其每个叶子的所有简单路径上包含相同数量的黑色节点。

插入后恢复平衡的情况

当插入一个新节点后，该节点被标记为红色，并且可能违反红黑树的性质。常见的恢复策略包括：

变色：如果新插入的节点的父节点也是红色，那么需要考虑变色操作（若父节点为黑色则无需自平衡）。如果叔叔节点（父节点的兄弟节点）也是红色，则将父节点和叔叔节点都变为黑色，祖父节点变为红色，然后以祖父节点作为新的起点继续检查（即黑红红改为红黑红）。

旋转：如果叔叔节点是黑色或不存在，则需要进行旋转操作来调整树的结构。具体分为以下几种情况：

左左情况：如果新节点是其父节点的左孩子，而父节点又是其祖父节点的左孩子，则进行一次右旋。

右右情况：如果新节点是其父节点的右孩子，而父节点又是其祖父节点的右孩子，则进行一次左旋。

左右情况：如果新节点是其父节点的右孩子，而父节点是其祖父节点的左孩子，则先对其父节点进行左旋，再对祖父节点进行右旋。

右左情况：如果新节点是其父节点的左孩子，而父节点是其祖父节点的右孩子，则先对其父节点进行右旋，再对祖父节点进行左旋。

删除后的恢复平衡

删除节点后，可能需要调整树的结构来恢复红黑树的性质。主要关注的是删除操作可能导致的黑色高度减少问题。常见的恢复策略包括：

双黑节点：如果删除了一个黑色节点，并且替换它的节点是红色，则直接将其替换为黑色即可。否则，如果替换节点是黑色，则会产生一个“双黑”节点（即节点和其原本的NIL节点都被视为黑色）。

旋转和变色：为了修复双黑问题，需要考虑以下几个方向：

如果双黑节点的兄弟节点是红色，则可以通过旋转和变色来解决。例如，如果兄弟节点是红色，且兄弟节点的外侧子节点是黑色，则可以先进行一次旋转（左旋或右旋），使兄弟节点成为父节点，然后进行变色。

如果兄弟节点是黑色，且兄弟节点的两个子节点都是黑色，则将兄弟节点变为红色，并继续在其父节点处进行检查。

如果兄弟节点是黑色，且兄弟节点的外侧子节点是红色，则可以先进行一次旋转（左旋或右旋），使兄弟节点成为父节点，然后进行变色。

如果兄弟节点是黑色，且兄弟节点的内侧子节点是红色，则可以先进行一次旋转（左旋或右旋），使兄弟节点成为父节点，然后进行变色。

7.HashMap 的 put 流程

第一步，通过 hash 方法计算 key 的哈希值。

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

第二步，数组进行第一次扩容。

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

第三步，根据哈希值计算 key 在数组中的下标，如果对应下标正好没有存放数据，则直接插入。

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

如果对应下标已经有数据了，就需要判断是否为相同的 key，是则覆盖 value，否则需要判断是否为树节点，是则向树中插入节点，否则向链表中插入数据。

else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
}

注意，在链表中插入节点的时候，如果链表长度大于等于 8，则需要把链表转换为红黑树。

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

所有元素处理完后，还需要判断是否超过阈值threshold，超过则扩容。

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

8.只重写 equals 没重写 hashcode，map put 的时候会发生什么?

如果只重写 equals 方法，没有重写 hashcode 方法，那么会导致 equals 相等的两个对象，hashcode 不相等，这样的话，这两个对象会被放到不同的桶中，这样就会导致 get 的时候，找不到对应的值。

当你使用一个键去 Map 中获取对应的值时，Map 会首先使用键的 hashCode 方法来定位可能的位置，然后再调用 equals 方法来确认键是否匹配。

如果你只重写了 equals 方法，那么即使两个键 equals 相等，但它们的 hashCode 不同，Map 将无法找到正确的条目，导致返回 null，即使该键实际上存在于 Map 中。

9.为什么要用高低做异或运算？为什么非得高低 16 位异或？

为什么使用高低位进行异或运算？

提高哈希值的均匀性：

哈希函数的目标是将输入数据映射到一个固定大小的空间中，使得输出尽可能均匀分布。 使用高低位异或运算可以帮助混合高阶位和低阶位的信息，从而提高哈希值的均匀性和随机性。

避免局部相关性：

在许多情况下，输入数据的高阶位和低阶位可能存在一定的相关性。通过异或运算，可以打破这种相关性，使得哈希值更加独立和随机。

增强扩散效果：

异或运算可以将高阶位和低阶位的信息混合在一起，从而增强哈希值的扩散效果。这有助于防止哈希冲突，提高哈希函数的质量。

为什么选择高低 16 位进行异或？

字长的一半：

对于 32 位整数，高低 16 位正好是字长的一半。这样可以充分利用整个字长，同时避免了不必要的复杂性。 选择 16 位是因为 16 是一个合理的中间值，既不是太小也不是太大，可以很好地混合高低位信息。

性能考虑：

16 位的位数适中，可以在性能和效果之间取得良好的平衡。如果位数太少，可能不足以充分混合信息；如果位数太多，可能会增加计算复杂度。

经验选择：

在实际应用中，高低 16 位异或已经被证明是一种有效的哈希函数优化方法。许多成熟的哈希函数（如 Jenkins Hash Function）都采用了这种方法。

10.为什么 HashMap 的容量是 2 的倍数呢？hashCode 对数组长度取模定位数组下标的优化策略？

哈希值计算：

HashMap 使用哈希码来确定元素存储的位置。哈希码通过与数组长度进行取模运算 (%) 来计算出元素在数组中的位置。 当数组长度是 2 的幂次方时，取模运算可以简化为位运算。具体来说，hash % capacity 可以简化为 hash & (capacity - 1)。这是因为当 capacity 是 2 的幂次方时，capacity - 1 将会是一个二进制数，其低位全部为 1，高位为 0。因此，hash & (capacity - 1) 实际上是保留了 hash 的低位部分，这比传统的取模运算更快。

减少哈希碰撞：

如果 HashMap 的容量是 2 的幂次方，那么哈希值的分布会更加均匀，从而减少了哈希碰撞的概率。这是因为位运算的结果依赖于哈希值的低位，如果低位分布均匀，则可以更好地分散元素，减少碰撞。

扩容时的重新哈希：

当 HashMap 的容量需要扩展时，如果新的容量仍然是 2 的幂次方，那么重新哈希的过程也会更加均匀。这是因为新的容量与旧的容量之间存在倍数关系，可以使得元素在新的数组中重新分布，减少由于扩容带来的碰撞。

硬件优化：

在现代计算机体系结构中，位运算通常比算术运算（如除法和取模）更快。因此，使用位运算来替代取模运算可以带来性能上的优势。

11.map 集合在使用时候一般都需要写容量值？为什么要写？扩容机制？

在使用 Java 中的 HashMap 时，通常会在创建 HashMap 实例时指定初始容量。这是因为 HashMap 的性能很大程度上取决于它的容量大小。指定合适的初始容量可以帮助避免不必要的扩容操作，从而提高程序的性能。

为什么需要指定容量

1. 减少扩容次数：当 HashMap 的容量达到阈值时，会触发一次扩容操作。如果 HashMap 的容量过大，那么每次扩容都需要重新计算哈希值，这可能会导致不必要的性能开销。通过指定合适的初始容量，可以减少扩容操作的次数，提高 HashMap 的性能。

2. 减少哈希碰撞：如果 HashMap 的容量过小，可能会导致哈希碰撞（即两个不同的键计算出相同的哈希值）。这会导致在 HashMap 中存在多个键映射到同一个位置，从而导致查找和插入操作的时间复杂度提高。通过指定合适的初始容量，可以减少哈希碰撞，提高 HashMap 的性能。

3. 减少内存占用：当 HashMap 的容量过大时，可能会导致 HashMap 的内存占用过多。通过指定合适的初始容量，可以减少 HashMap 的内存占用，提高 HashMap 的性能。

扩容机制

HashMap 的默认初始容量是 16，而且容量总是 2 的幂次方。当 HashMap 中的元素数量超过了当前容量与加载因子（默认为 0.75）的乘积时，就会触发扩容操作。扩容时，HashMap 会创建一个新的数组，其容量通常是原来的两倍，并将原有数组中的所有元素重新散列并放入新的数组中。

12.红黑树转回链表的阈值为什么默认是6而不是8？

因为如果这个阈值也设置成 8，假如发生碰撞，节点增减刚好在 8 附近，会发生链表和红黑树的不断转换，导致资源浪费。

13.JDK8对HashMap的实现原理做了哪些优化？

1. 底层数据结构由数组 + 链表改成了数组 + 链表或红黑树的结构。

原因：如果多个键映射到了同一个哈希值，链表会变得很长，在最坏的情况下，当所有的键都映射到同一个桶中时，性能会退化到 O(n)，而红黑树的时间复杂度是 O(logn)。

2.链表的插入方式由头插法改为了尾插法。

原因：头插法虽然简单快捷，但扩容后容易改变原来链表的顺序。

3.扩容的时机由插入时判断改为插入后判断。

原因：可以避免在每次插入时都进行不必要的扩容检查，因为有可能插入后仍然不需要扩容。

4.优化了哈希算法

JDK 7 进行了多次移位和异或操作来计算元素的哈希值。JDK 8 优化了这个算法，只进行了一次异或操作，但仍然能有效地减少冲突。并且能够保证扩容后，元素的新位置要么是原位置，要么是原位置加上旧容量大小。

14.HashMap和TreeMap的区别？

1.HashMap 是基于数组+链表+红黑树实现的，put 元素的时候会先计算 key 的哈希值，然后通过哈希值计算出数组的索引，然后将元素插入到数组中，如果发生哈希冲突，会使用链表来解决，如果链表长度大于 8，会转换为红黑树。

get 元素的时候同样会先计算 key 的哈希值，然后通过哈希值计算出数组的索引，如果遇到链表或者红黑树，会通过 key 的 equals 方法来判断是否是要找的元素。

2.TreeMap 是基于红黑树实现的，put 元素的时候会先判断根节点是否为空，如果为空，直接插入到根节点，如果不为空，会通过 key 的比较器来判断元素应该插入到左子树还是右子树。

get 元素的时候会通过 key 的比较器来判断元素的位置，然后递归查找。

由于 HashMap 是基于哈希表实现的，所以在没有发生哈希冲突的情况下，HashMap 的查找效率是 O(1)。适用于查找操作比较频繁的场景。

而 TreeMap 是基于红黑树实现的，所以 TreeMap 的查找效率是 O(logn)。并且保证了元素的顺序，因此适用于需要大量范围查找或者有序遍历的场景。