Java高频面试题2：集合框架

发布于：2025-04-04 ⋅ 阅读:(16) ⋅ 点赞:(0)

一、集合框架概述

1. 常见的集合框架有哪些？

  • Collection：存储单个元素的集合。
    • List（有序、可重复）：ArrayList（动态数组）、LinkedList（双向链表）。
    • Set（无序、唯一）：HashSet（基于HashMap）、TreeSet（红黑树）。
    • Queue（队列）：ArrayDeque（双端队列）、PriorityQueue（优先级队列）。
  • Map：存储键值对。
    • HashMap（数组+链表/红黑树）、LinkedHashMap（保持插入顺序）、TreeMap（红黑树，按Key排序）。

二、List

2. ArrayList和LinkedList的区别？

特性 ArrayList LinkedList
数据结构 动态数组 双向链表
增删效率 尾部O(1)，中间O(n) 头尾O(1)，中间O(n)
查找效率 随机访问O(1) 顺序访问O(n)
内存占用 连续内存，紧凑 非连续内存，每个节点含前驱/后继指针
线程安全 非线程安全 非线程安全

3. ArrayList的扩容机制？

  • 初始容量：默认16。
  • 扩容触发：当元素个数超过当前容量的loadFactor（默认0.75）时。
  • 扩容逻辑：新容量为原容量的1.5倍，通过Arrays.copyOf()复制旧数组到新数组。

4. 如何实现ArrayList的线程安全？

  • 使 ⽤ Ve c t o r ：不 推 荐 ， Ve c t o r 是 ⼀ 个 历 史 遗 留 类 。
  • 使用Collections.synchronizedList()：通过synchronized关键字保证线程安全。
  • 使用CopyOnWriteArrayList：写时复制，读操作无锁，适合读多写少场景。
  • 在 使 ⽤ A r r a y L i s t 时 ， 应 ⽤ 程 序 通 过 同 步 机 制 去 控 制 A r r a y L i s t 的 读 写 。

三、Map

5. HashMap的底层数据结构？

  • JDK7：数组+链表。
  • JDK8：数组+链表/红黑树（链表长度≥8且数组长度≥64时转换为红黑树）。

6. HashMap的put流程？

  1. 计算哈希值：通过hash(key)方法（hashCode()异或高16位）。
  2. 确定桶位置：(n-1) & hash（n为数组长度）。
  3. 处理冲突：
    • 若桶为空，直接插入。
    • 若桶不为空，遍历链表/红黑树：
      • 若Key存在，覆盖Value。
      • 若Key不存在，链表尾插（JDK8），红黑树插入。
  4. 扩容检查：若元素个数超过阈值（capacity * loadFactor），触发扩容（2倍）。

7. HashMap的哈希函数设计？

  • 扰动函数：(h = key.hashCode()) ^ (h >>> 16)，混合高低位信息，减少哈希冲突。
  • 数组长度：必须为2的幂，保证(n-1) & hash均匀分布。

8. 为什么链表转红黑树的阈值是8？

  • 泊松分布：链表长度超过8的概率极低（约0.00000006），树化是为极端情况优化。
  • 空间权衡：红黑树节点占用更多内存，避免频繁转换。

9. JDK8对HashMap的优化？

  • 红黑树：链表过长时转换为红黑树，提升查询效率。
  • 尾插法：避免JDK7头插法导致的扩容死循环。
  • 扩容优化：节点位置仅可能是原位置或原位置+旧容量，减少重新计算哈希的开销。

10. HashMap的线程安全问题及解决方案？

  • 问题：多线程下扩容可能导致死循环、数据覆盖或丢失。
  • 解决方案：
    • Hashtable：方法级synchronized，性能差。
    • ConcurrentHashMap：JDK7分段锁，JDK8 CAS+synchronized，高并发场景首选。
    • Collections.synchronizedMap：同步包装器，适合低并发。

11. LinkedHashMap如何保持有序？

  • 双向链表：维护插入顺序或访问顺序（通过accessOrder参数）。
  • 实现LRU缓存：重写removeEldestEntry方法。

12. TreeMap如何实现有序？

  • 红黑树：基于Key的自然排序（实现Comparable）或自定义Comparator。
  • 范围查询：支持subMap、headMap等方法。

13.为什么HashMap的容量是2的幂次方？

  • 保证通过位运算(n-1)&hash高效计算索引，避免哈希冲突。
  • 扩容时只需检查高位，减少重新哈希的开销。

14.ConcurrentHashMap与Hashtable的区别？

  • 锁粒度：在 JDK 1.7 中，采用分段锁（Segment）机制，将数据分成多个段，每个段独立加锁。在 JDK 1.8 中，进一步优化为使用 CAS（Compare-And-Swap）和 synchronized 锁单个桶（bucket），减少了锁的粒度。Hashtable全表锁。
  • 性能：ConcurrentHashMap吞吐量更高。
  • 空键值：Hashtable不允许null键值，ConcurrentHashMap允许。

四、Set

15. HashSet的底层实现？

  • 基于HashMap：值为固定对象PRESENT，利用HashMap的Key唯一性。
  • 去重逻辑：依赖hashCode()和equals()方法。

五、其他高频问题

16. 快速失败（Fail-Fast）与安全失败（Fail-Safe）？

  • 快速失败：遍历时若集合被修改（非预期），抛出ConcurrentModificationException（如ArrayList）。
  • 安全失败：遍历拷贝的集合副本，不反映原集合的修改（如CopyOnWriteArrayList）。

17. 如何选择集合类？

  • 需要随机访问：选ArrayList。
  • 频繁增删：选LinkedList。
  • 键值对存储：
    • 无序：HashMap。
    • 插入顺序：LinkedHashMap。
    • 排序：TreeMap。
  • 线程安全：ConcurrentHashMap或CopyOnWriteArrayList。

六、代码实战

18. 手写简易HashMap（数组+链表版）？

public class SimpleHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private Node<K, V>[] table;
    private int size;

    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public void put(K key, V value) {
        int index = hash(key) & (DEFAULT_CAPACITY - 1);
        Node<K, V> node = table[index];
        if (node == null) {
            table[index] = new Node<>(key, value);
            size++;
        } else {
            while (node != null) {
                if (node.key.equals(key)) {
                    node.value = value;
                    return;
                }
                if (node.next == null) {
                    node.next = new Node<>(key, value);
                    size++;
                    return;
                }
                node = node.next;
            }
        }
    }

    public V get(K key) {
        int index = hash(key) & (DEFAULT_CAPACITY - 1);
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.key.equals(key)) return node.value;
            node = node.next;
        }
        return null;
    }

    private int hash(K key) {
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }
}

19. LinkedHashMap 实现 LRU（Least Recently Used，最近最少使用）缓存

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // 调用父类构造函数，设置初始容量、负载因子和访问顺序
        super(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                // 当缓存大小超过容量时，移除最旧的元素
                return size() > capacity;
            }
        };
        this.capacity = capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        System.out.println(cache.get(1)); 
        cache.put(4, "four"); 
        System.out.println(cache.get(2)); 
    }
}

此代码定义了一个 LRUCache 类，它继承自 LinkedHashMap。在构造函数里，借助 LinkedHashMap 的特性，把访问顺序设为 true，这意味着访问元素时会将其移到链表尾部。同时，重写了 removeEldestEntry 方法，当缓存大小超出容量时，就会移除最旧的元素。在 main 方法里，对 LRUCache 的功能进行了简单测试。

总结：以上题目覆盖Java集合框架核心知识点，建议重点掌握HashMap的底层实现、扩容机制、线程安全方案以及List/Set的特性对比。面试时需结合源码和实际场景说明设计原理，体现对细节的理解。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布