java集合面试题-EW帮帮网

2.1 Collection 集合

Collection 集合有哪些类？

Collection 是 Java 集合框架中的一个根接口，它有多个子接口和实现类，常见的如下：

List 接口：有序可重复集合，元素有特定顺序，可通过索引访问。
- ArrayList：基于动态数组实现，随机访问快，插入和删除慢。
- LinkedList：基于双向链表实现，插入和删除快，随机访问慢。
- Vector：线程安全的动态数组，性能比 ArrayList 低。
Set 接口：无序不可重复集合，不允许有重复元素。
- HashSet：基于 HashMap 实现，元素存储无序。
- LinkedHashSet：继承自 HashSet，使用链表维护元素插入顺序。
- TreeSet：基于红黑树实现，可对元素进行排序。
Queue 接口：用于模拟队列，遵循先进先出（FIFO）原则。
- LinkedList：也可作为队列使用。
- PriorityQueue：基于堆实现的优先队列，元素按优先级排序。

ArrayList 的底层？

ArrayList 的底层是基于动态数组实现的。它使用一个 Object 类型的数组来存储元素，当创建一个 ArrayList 对象时，会初始化一个默认大小的数组（默认初始容量为 10）。随着元素的添加，当数组容量不足时，会创建一个更大的新数组，并将原数组中的元素复制到新数组中。

ArrayList 自动扩容？

当向 ArrayList 中添加元素时，如果当前数组的容量不足以容纳新元素，就会触发自动扩容机制。具体步骤如下：

计算新的容量：新容量通常是原容量的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。
创建新数组：根据新容量创建一个新的 Object 数组。
复制元素：将原数组中的元素复制到新数组中。
更新引用：将 ArrayList 内部的数组引用指向新数组。

以下是一个简单的示例代码，展示了 ArrayList 扩容的过程：

import java.util.ArrayList;

public class ArrayListResizeExample {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(2);
        System.out.println("初始容量: " + getCapacity(list));
        list.add(1);
        list.add(2);
        System.out.println("添加 2 个元素后容量: " + getCapacity(list));
        list.add(3);
        System.out.println("添加第 3 个元素后容量: " + getCapacity(list));
    }

    private static int getCapacity(ArrayList<?> list) {
        java.lang.reflect.Field field;
        try {
            field = ArrayList.class.getDeclaredField("elementData");
            field.setAccessible(true);
            return ((Object[]) field.get(list)).length;
        } catch (Exception e) {
            e.printStackTrace();
            return -1;
        }
    }
}

ArrayList 的 Fail - Fast 机制？

Fail - Fast 机制是 ArrayList 等集合类的一种错误检测机制。当一个线程正在遍历集合，而另一个线程对集合进行了结构上的修改（如添加、删除元素等）时，就会触发 Fail - Fast 机制，抛出 ConcurrentModificationException 异常。

ArrayList 内部通过一个 modCount 变量来实现 Fail - Fast 机制。每当对集合进行结构上的修改时，modCount 的值就会加 1。在使用迭代器遍历集合时，迭代器会记录当前的 modCount 值，在每次调用 next() 方法时，会检查 modCount 是否发生了变化，如果发生了变化，就会抛出 ConcurrentModificationException 异常。

2.2 Map

Map 有哪些类？

Map 是 Java 集合框架中的另一个重要接口，用于存储键值对，常见的实现类如下：

HashMap：基于哈希表实现，无序，允许键和值为 null，不是线程安全的。
LinkedHashMap：继承自 HashMap，使用链表维护元素的插入顺序或访问顺序。
TreeMap：基于红黑树实现，可根据键的自然顺序或指定的比较器对键进行排序。
Hashtable：线程安全的哈希表，不允许键和值为 null，性能比 HashMap 低。
ConcurrentHashMap：线程安全的哈希表，在多线程环境下性能比 Hashtable 高。
WeakHashMap：基于弱引用实现的哈希表，当键所引用的对象被垃圾回收时，对应的键值对会被自动移除。

JDK7 HashMap 如何实现？

JDK7 中的 HashMap 基于数组 + 链表实现。具体实现如下：

哈希表结构：使用一个 Entry 数组作为哈希表，每个 Entry 对象包含键、值、哈希值和指向下一个 Entry 的引用。
哈希函数：通过 hash() 方法计算键的哈希值，然后通过 indexFor() 方法将哈希值映射到数组的索引位置。
插入元素：当插入一个键值对时，首先计算键的哈希值，找到对应的数组索引位置。如果该位置为空，直接插入新的 Entry 对象；如果该位置已经有元素，则将新的 Entry 对象插入到链表的头部（头插法）。
查找元素：根据键的哈希值找到对应的数组索引位置，然后遍历链表，比较键的哈希值和键的 equals() 方法，找到匹配的键值对。
扩容机制：当哈希表中的元素数量超过阈值（容量 * 负载因子）时，会进行扩容操作。扩容时，会创建一个新的数组，容量为原数组的 2 倍，然后将原数组中的元素重新哈希到新数组中。

JDK8 HashMap 如何实现？

JDK8 中的 HashMap 在 JDK7 的基础上进行了优化，采用数组 + 链表 + 红黑树实现。具体实现如下：

哈希表结构：使用一个 Node 数组作为哈希表，每个 Node 对象包含键、值、哈希值和指向下一个 Node 的引用。当链表长度达到 8 且数组长度达到 64 时，链表会转换为红黑树；当红黑树中的节点数量减少到 6 时，红黑树会转换回链表。
哈希函数：通过 hash() 方法计算键的哈希值，然后通过 (n - 1) & hash 方法将哈希值映射到数组的索引位置（n 为数组长度）。
插入元素：当插入一个键值对时，首先计算键的哈希值，找到对应的数组索引位置。如果该位置为空，直接插入新的 Node 对象；如果该位置已经有元素，且是链表结构，则遍历链表，比较键的哈希值和键的 equals() 方法，找到匹配的键则更新值，否则将新的 Node 对象插入到链表尾部（尾插法）；如果该位置是红黑树结构，则调用红黑树的插入方法。
查找元素：根据键的哈希值找到对应的数组索引位置，如果是链表结构，则遍历链表，比较键的哈希值和键的 equals() 方法，找到匹配的键值对；如果是红黑树结构，则调用红黑树的查找方法。
扩容机制：当哈希表中的元素数量超过阈值（容量 * 负载因子）时，会进行扩容操作。扩容时，会创建一个新的数组，容量为原数组的 2 倍，然后将原数组中的元素重新哈希到新数组中。在重新哈希时，红黑树节点会根据哈希值的不同拆分成两个链表或红黑树。

HashSet 是如何实现的？

HashSet 是基于 HashMap 实现的。HashSet 内部维护了一个 HashMap 对象，当向 HashSet 中添加元素时，实际上是将该元素作为键，一个常量 PRESENT 作为值，存储到内部的 HashMap 中。由于 HashMap 的键是唯一的，所以 HashSet 中的元素也是唯一的。

以下是 HashSet 部分源码示例：

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

什么是 WeakHashMap?

WeakHashMap 是基于弱引用实现的哈希表。在 WeakHashMap 中，键是弱引用类型。当键所引用的对象被垃圾回收时，对应的键值对会被自动从 WeakHashMap 中移除。

WeakHashMap 的主要用途是在缓存场景中，当缓存的对象不再被其他地方引用时，能够自动释放内存，避免内存泄漏。例如：

import java.util.WeakHashMap;

public class WeakHashMapExample {
    public static void main(String[] args) {
        WeakHashMap<MyKey, String> weakHashMap = new WeakHashMap<>();
        MyKey key = new MyKey();
        weakHashMap.put(key, "Value");
        System.out.println("Before GC: " + weakHashMap);
        key = null;
        System.gc();
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("After GC: " + weakHashMap);
    }

    static class MyKey {
        // 空类
    }
}

在这个示例中，当 key 被置为 null 后，调用 System.gc() 进行垃圾回收，由于 key 是弱引用，其引用的对象会被回收，对应的键值对也会从 WeakHashMap 中移除。

java集合面试题