Java 集合框架 #

Java 集合框架面试核心知识点

📋 目录 #

HashMap #

面试必考 ⭐⭐⭐⭐⭐

核心问题速答 #

问题 答案
HashMap是否有序？ ❌ 无序
有序的Map有哪些？ TreeMap, LinkedHashMap
TreeMap实现原理 红黑树 + SortedMap接口
LinkedHashMap实现原理 双向链表 + 插入/访问顺序

底层数据结构 #

HashMap

数组 Node<K,V>[]

链表

红黑树

阈值: 8转树

阈值: 6转链表

版本演进 #

版本 实现方式 问题
Java 7 数组 + 链表（头插法） 扩容时可能导致死循环
Java 8+ 数组 + 链表 + 红黑树（尾插法） 解决死循环，解决数据丢失风险

核心源码解析 #

put() 流程 #

public V put(K key, V value) {
    // 1. 计算hash值
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 2. 初始化table
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 3. 计算下标，如果没有碰撞直接放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 节点已存在

        // 4. 链表长度超过8转红黑树
        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;
            }
        }

        // 5. 节点已存在，替换旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;
    // 6. 桶满了，扩容（容量*加载因子）
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

关键阈值 #

参数 默认值 说明
初始容量 16 必须是2的幂
加载因子 0.75 平衡时间和空间
树化阈值 8 链表长度≥8转红黑树
树转链表阈值 6 红黑树节点≤6转链表
最小树化容量 64 数组长度≥64才允许树化

为什么树化阈值是8？ #

树化成本:
  - 时间复杂度: O(log n)
  - 转换开销: 节点重建

链表 vs 红黑树:
  - 链表短时 (n<8): O(n) ≈ O(log n) 且无转换开销
  - 链表长时 (n≥8): O(n) >> O(log n) 转换值得

阈值差异 (8 vs 6):
  - 避免频繁转换，增加性能抖动

面试高频问题 #

Q1: HashMap为什么线程不安全？ #

问题场景 说明
1.8数据丢失 多线程同时put，后执行的线程会覆盖之前的值
1.7死循环 扩容时链表形成环（头插法导致）
数据不一致 视觉上可见但未完全写入

Q2: 扰动函数的作用？ #

static final int hash(Object key) {
    int h;
    // 高16位异或低16位，减少hash冲突
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

目的: 充分利用高位信息，减少哈希冲突

Q3: 扩容机制？ #

扩容条件: size > threshold (容量 * 加载因子)
扩容容量: newCapacity = oldCapacity << 1 (翻倍)
数据迁移: 重新计算下标

Q4: 为什么容量必须是2的幂？ #

// 下标计算
index = (n - 1) & hash;

// 当n是2的幂时，n-1的二进制全是1
// 直接与操作即可得到下标，效率高
// 16 - 1 = 15 = 00001111

Q5: 当key为自定义对象时？ #

public class User {
    // 必须重写
    @Override
    public boolean equals(Object obj) {}

    @Override
    public int hashCode() {}
}

ConcurrentHashMap #

并发核心 ⭐⭐⭐⭐⭐

版本对比 #

特性 Java 7 Java 8+
实现方式 分段锁 Segement CAS + synchronized
锁粒度 Segement级别 Node级别
查询效率 需要加锁 无锁(除了first node)

Java 8+ 核心原理 #

ConcurrentHashMap

Node数组

HeadNode

CAS操作

synchronized

红黑树

put() 核心流程 #

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable(); // 初始化
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 1. CAS插入新节点
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        }
        else if ((fh = f.hash) == MOVED)
            // 2. 正在扩容，帮助迁移
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 3. synchronized锁住首节点
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            Ek ek = e.key;
                            if (ek == key ||
                                (ek != null && key.equals(ek))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 红黑树处理
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

面试重点 #

概念 说明
CAS Compare And Swap，无锁并发
volatile 保证可见性
synchronized 1.8后用于锁住首节点
spread() 类似HashMap的扰动函数

有序Map对比 #

特性 HashMap TreeMap LinkedHashMap
有序性 ❌ ✅ ✅
排序方式 - key自然排序 插入/访问排序
底层实现 数组+链表+红黑树 红黑树 双向链表+HashMap
复杂度 O(1) O(log n) O(1)
null key ✅ ❌ ✅

TreeMap 实现原理 #

// 实现SortedMap接口
public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

// 基于红黑树
private final Entry<K,V> getEntry(Object key) {
    // 红黑树查找逻辑
}

LinkedHashMap 实现原理 #

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    // 双向链表维护顺序
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
    }

    // 访问排序模式
    public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder; // true: 访问顺序; false: 插入顺序
    }
}

List对比 #

List

ArrayList

LinkedList

Vector

CopyOnWriteArrayList

数组实现
随机访问快

双向链表
插入删除快

线程安全
已废弃

写时复制
读多写少

特性 ArrayList LinkedList
实现 数组 双向链表
随机访问 O(1) ⭐ O(n)
插入删除 O(n) O(1)
扩容 1.5倍 -
线程安全 ❌ ❌

源码细节 #

ArrayList 扩容 #

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Set对比 #

特性 HashSet TreeSet LinkedHashSet
底层实现 HashMap TreeMap LinkedHashMap
有序性 ❌ ✅ ✅
允许null ✅ ❌ ✅
重复 ❌ ❌ ❌

🎯 面试题汇总 #

基础题 #

  1. HashMap底层数据结构是什么？

    • Java 7: 数组 + 链表
    • Java 8+: 数组 + 链表 + 红黑树，链表长度超过8转红黑树，低于6转链表

  2. HashMap的扩容机制？

    • 触发条件: size > threshold（容量 × 加载因子）
    • 扩容倍数: 扩容为原来的 2倍（newCapacity = oldCapacity << 1）
    • 数据迁移: 每个元素重新计算哈希下标，迁移到新数组

  3. 为什么是8转红黑树，6转链表？

    • 概率原因: 根据泊松分布，哈希冲突长度达到8的概率非常低（约0.00000006）
    • 性能权衡: 链表查找 O(n)，红黑树查找 O(log n)
      • 链表短时 (n < 8): O(n) ≈ O(log n)，且无树化转换开销
      • 链表长时 (n ≥ 8): O(n) >> O(log n)，转换值得
    • 阈值差异 (8 vs 6): 避免频繁在链表和红黑树之间转换，减少性能抖动

  4. ConcurrentHashMap和HashMap的区别？

    区别 HashMap ConcurrentHashMap
    线程安全 ❌ 不安全 ✅ 安全
    锁机制 无锁 Java 8+ CAS + synchronized
    允许null ✅ 允许key/value为null ❌ 不允许
    使用场景 单线程环境 并发环境

进阶题 #

  1. HashMap为什么线程不安全？

    • Java 8+: 多线程同时put时，后写入的线程会覆盖之前的值，造成数据丢失
    • Java 7: 扩容时使用头插法，多个线程同时扩容可能导致链表形成环，造成死循环
    • 根本原因: 没有对底层数组的修改做同步保护

  2. 扰动函数的作用？

    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
    • 目的: 让高16位和低16位异或，充分利用高位信息
    • 效果: 减少哈希冲突，使得哈希分布更均匀

  3. ConcurrentHashMap的Java 7和Java 8实现差异？

    对比项 Java 7 Java 8+
    实现 分段锁 Segement CAS + synchronized
    锁粒度 Segement级别（粗） Node首节点级别（细）
    查询效率 需要加锁 无锁读取（除首节点）

  4. 不同List的选择场景？

    List类型 适用场景
    ArrayList 读多写少，需要随机访问
    LinkedList 频繁在中间插入/删除元素
    Vector 不推荐，已过时（锁粒度太粗）
    CopyOnWriteArrayList 读多写少，并发环境

源码题 #

  1. 手写一个简易HashMap

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

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

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public SimpleHashMap() {
        table = new Node[DEFAULT_CAPACITY];
        threshold = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR);
        size = 0;
    }

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

    public V put(K key, V value) {
        int hash = hash(key);
        int n = table.length;
        int i = (n - 1) & hash;

        if (table[i] == null) {
            table[i] = new Node<>(hash, key, value, null);
        } else {
            Node<K, V> p = table[i];
            Node<K, V> e = null;

            if (p.hash == hash && (p.key == key || (key != null && key.equals(p.key)))) {
                e = p;
            } else {
                for (Node<K, V> curr = p; ; curr = curr.next) {
                    if (curr.hash == hash && (curr.key == key || (key != null && key.equals(curr.key)))) {
                        e = curr;
                        break;
                    }
                    if (curr.next == null) {
                        curr.next = new Node<>(hash, key, value, null);
                        break;
                    }
                }
            }

            if (e != null) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        size++;
        if (size > threshold) {
            resize();
        }
        return null;
    }

    public V get(K key) {
        int hash = hash(key);
        int n = table.length;
        int i = (n - 1) & hash;
        Node<K, V> p = table[i];

        if (p != null) {
            do {
                if (p.hash == hash && (p.key == key || (key != null && key.equals(p.key)))) {
                    return p.value;
                }
                p = p.next;
            } while (p != null);
        }
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        int oldCapacity = table.length;
        int newCapacity = oldCapacity << 1;
        Node<K, V>[] newTable = new Node[newCapacity];

        for (int j = 0; j < oldCapacity; j++) {
            Node<K, V> p = table[j];
            if (p != null) {
                do {
                    Node<K, V> next = p.next;
                    int i = (newCapacity - 1) & p.hash;
                    p.next = newTable[i];
                    newTable[i] = p;
                    p = next;
                } while (p != null);
            }
        }

        table = newTable;
        threshold = (int) (newCapacity * DEFAULT_LOAD_FACTOR);
    }

    public int size() {
        return size;
    }
}

  2. 手写ConcurrentHashMap的put逻辑

    核心逻辑要点：

    • 对null值检查校验
    • 如果table为空，初始化table
    • 如果对应位置为空，用CAS尝试插入
    • 如果正在扩容（hash = MOVED），帮助迁移
    • 否则synchronized锁住首节点，插入或更新
    • 插入后检查是否需要树化，增加计数

    完整源码参考本文前面的「put() 核心流程」部分。

  3. 分析扩容时的死循环问题

    Java 7 头插法问题：

    • 死循环发生在transfer扩容方法中
    • 多个线程同时扩容，头插法会改变链表顺序
    • 可能形成 node.next = node 的环形链表
    • get()查询时遍历环形链表，导致死循环

    Java 8+ 解决：

    • 使用尾插法，不会改变链表顺序
    • 不可能形成环形结构，从根源解决死循环问题

🔗 相关笔记 #

最后更新: 2026-04-29