java中的集合到底是干什么的？有了数据类型存储数据了，为什么还要设计一套集合框架？集合框架有什么好处？怎么实现的？

集合框架总览

场景引入

在编程中，我们需要管理和操作一组数据 。不用集合框架，只用数组，你会发现：

创建时必须指定大小，不能动态改变；只能存放单一类型元素；只有length属性，没有增删改查方法，需要自己去实现数据操作；存放基本类型

比如：在一个电商网站中，用数组实现购物车：添加商品需要手动检查容量，找空位；删除商品：需要遍历找到位置，后面元素迁移

用集合解决

  1. 动态容量：不需要预先知道数据量，不需要指定大小
  2. 丰富操作：调用一个方法直接完成增删改查数据操作
  3. 数据结构封装：不同场景选择不同集合
  4. 统一接口：所有集合都遵守统一规范

原理拆解

集合是什么？集合里面有什么？

集合框架是一套数据结构的标准库 ，通过统一的接口体系(List/Set/Queue/Map)，提供多种数据存储和组织方式。它的核心价值是 开发者无需自己实现链表、哈希表、树等数据结构 ，直接使用经过优化的标准实现。

主要有List，Set，Queue，Map，每一个集合都有自己独特特性：数据操作和存储结构

集合框架层次结构

Iterable (接口)
    └── Collection (接口)
            ├── List (接口) - 有序、可重复
            │       ├── ArrayList
            │       ├── LinkedList
            │       └── Vector (遗留)
            │               └── Stack (遗留)
            ├── Set (接口) - 无序、不可重复
            │       ├── HashSet
            │       ├── LinkedHashSet
            │       └── TreeSet
            └── Queue (接口) - 队列
                    ├── PriorityQueue
                    └── Deque (双端队列)
                            └── ArrayDeque

Map (接口) - 键值对
    ├── HashMap
    ├── LinkedHashMap
    ├── TreeMap
    ├── Hashtable (遗留)
    └── WeakHashMap

其实深挖底层，就会发现有的集合底层就是一个数组，那数组和集合之间有什么不同？为什么不直接采用数组，还要多此一举，封装成集合？

集合底层很多是数组，但封装提供了动态性和便利性 ，开发者不用重复造轮子

集合 vs 数组对比

特性 数组 集合
长度 固定 动态
类型 可存基本类型 只能存引用类型
功能 仅长度属性 提供丰富API
性能 最高 略低(有封装开销)

对比分析

接口 有序性 重复性 null值 典型实现
List 有序 可重复 允许多个 ArrayList, LinkedList
Set 无序/有序 不可重复 允许一个 HashSet, TreeSet
Map 无序/有序 键不重复 允许 HashMap, TreeMap
Queue FIFO 可重复 视实现 LinkedList, PriorityQueue

常见坑点

  1. 基本类型陷阱: 集合只能存储引用类型，基本类型会自动装箱/拆箱
List<int> list;  //编译错误
List<Integer> list = new ArrayList<>();  //正确
  1. 泛型擦除: 运行时泛型信息丢失

泛型擦除 ：Java的泛型只在编译期有效，运行时会"擦除"泛型信息，所有泛型类型都变成原始类型(Object或上界类型)

List list = new ArrayList<>();

list.add(“hello”);

String s = list.get(0);

// 编译器擦除后等价于

List list = new ArrayList();

list.add(“hello”);

String s = (String) list.get(0); // 编译器自动插入类型转换

泛型擦除带来的问题

//问题1: 不能用泛型创建数组

List[] arr = new List[10]; // 编译错误

//问题2: 不能instanceof判断泛型

if (list instanceof List) { } // 编译错误

//问题3: 静态方法不能用类的泛型

class Test {

static void method(T t) { }  // 编译错误

}

//解决方法: 通配符

void printList(List<?> list) { } // 可以接收任何类型的List

为什么设计泛型擦除

历史原因 ：Java 5才引入泛型，为了 向后兼容 老代码(Java 1-4没有泛型)，采用擦除实现，这样老代码不需要修改就能运行。

List<String> stringList = new ArrayList<>();
List<Integer> intList = new ArrayList<>();

// 编译期：编译器会检查类型
stringList.add("hello");  //正确
stringList.add(123);      //编译错误

// 运行期：泛型信息被擦除
System.out.println(stringList.getClass());  // class java.util.ArrayList
System.out.println(intList.getClass());     // class java.util.ArrayList
System.out.println(stringList.getClass() == intList.getClass());  // true! 同一个类

// 泛型参数在运行时不存在
System.out.println(stringList instanceof List<String>);  //编译错误! 不能这样写
  1. Collection vs Collections: Collection是接口，Collections是工具类

问题

为什么提供Iterable接口而不是Collection直接提供iterator()？

  1. 解耦：Iterable接口提供遍历方法，而Collenticon接口专注于提供集合的相关操作的方法；如果Collection接口提供iterator(),所有需要遍历但不是集合的类都必须实现Collection
  2. 职责单一原则

数组和集合哪一个的性能高？

  1. 基本类型 + 固定大小：数组性能最高
  2. 引用类型 + 动态大小：ArrayList性能和数组接近，且更灵活
  3. 频繁首尾操作：LinkedList可能更快
  4. 大多数业务场景：集合的性能差异可忽略，灵活性和开发效率更重要
  5. 一句话总结 ：数组在基本类型操作和内存占用上有优势，但在动态扩容和引用类型场景，集合的性能损失很小，开发效率提升显著

List接口体系

ArrayList源码剖析

核心属性

public class ArrayList<E> extends AbstractList<E> 
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    //无参构造时的默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    //共享的空数组实例
    //用于显式指定容量为0的情况: new ArrayList(0)
    //static final:所有空ArrayList都能共享同一个空数组对象，这样就可以节省内存
    //空数组是{}不是null，因为后续操作(如length)不需要null检查
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //用于无参构造器: new ArrayList()
    //第一次添加元素时才扩容到DEFAULT_CAPACITY(10)
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //存储元素的底层数组缓冲区
    //transient: 不参与Java默认序列化
    transient Object[] elementData;
        
    //实际包含的元素个数 
    private int size;

    //数组最大分配大小
    //Integer.MAX_VALUE = 2^31 - 1 = 2147483647
    //MAX_ARRAY_SIZE = 2147483639
    //约2GB，单个数组的最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

核心属性中的问题和思考

DEFAULT_CAPACITY为什么是10而不是其他值?

太小(如4): 添加少量元素就触发扩容，频繁复制数组

太大(如100): 创建空ArrayList就占用大量内存

10是经验值，适用于大多数常见场景

DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA的区分

第一次add时，需要知道是"懒加载首次添加"还是"显式指定容量0"

如果是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，首次add扩容到10

如果是EMPTY_ELEMENTDATA，首次add只扩容到1

ArrayList list1 = new ArrayList();        // 指向DEFAULTCAPACITY_EMPTY
ArrayList list2 = new ArrayList(0);       // 指向EMPTY_ELEMENTDATA
list1.add("A");  // 扩容到10，放入"A"
list2.add("A");  // 扩容到1，放入"A"，下次add再扩容
elementData的解读

类型是Object[]而非E[]的原因:

Java泛型是类型擦除的，运行时E变为Object，而且new E[capacity]在Java中是语法错误(无法创建泛型数组)，

所以直接使用Object[]存储，读取时强制转换为E

数组容量: elementData.length

有效元素: 前size个位置(elementData[0]到elementData[size-1])

空闲位置: size到elementData.length-1(都是null)

size的关键点

size ≠ 容量(capacity)：elementData.length

关系: 0 ≤ size ≤ elementData.length

add时: elementData[size] = e; size++;

remove时: size–; elementData[size] = null;

MAX_ARRAY_SIZE为什么要减8

某些JVM实现在数组对象头部存储了元数据

预留8字节作为安全余量，避免OutOfMemoryError

为什么是8？这是JVM规范的建议值

构造器源码

public ArrayList(int initialCapacity) {
    //如果初始化容量大于0，说明用户指定了容量
    //就能知道要存储多少元素，进行预先分配，避免扩容
    if (initialCapacity > 0) {
        //此时size为默认值0，因为有效元素为0个
        this.elementData = new Object[initialCapacity];
    //用户显式指定容量为0
    //确定不会添加元素，或者稍后通过addAll批量添加
    } else if (initialCapacity == 0) {
        //指向共享空数组，节省内存
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
    //容量为负数，抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    //无参构造，懒加载策略
    //指向空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    //把集合转换为数组
    elementData = c.toArray();
    //检测集合是否为空，同时完成size赋值
    if ((size = elementData.length) != 0) {
        //检查toArray返回的数组类型
        if (elementData.getClass() != Object[].class)
            //如果不相等，说明toArray返回了特定类型的数组(如String[])
            //必须转换为Object[]，否则后续add不同类型的元素会失败
            //创建新的Object[]数组并复制元素
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //指向共享空数组，不创建新对象
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

空数组懒加载？

为什么要分开实现空数组和显式指定为0？

add()方法完整流程

public boolean add(E e) {
    //传入size + 1: 传入添加后需要的最小容量
    ensureCapacityInternal(size + 1);
    //将元素e放入数组的size位置
    //size++是后置递增: 先用size的当前值，再size+1
    elementData[size++] = e;
    return true;
}

//确保数组有足够的容量容纳新元素
private void ensureCapacityInternal(int minCapacity) {
    //判断是否是首次添加，==比较引用地址，不是比较内容
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //取默认容量10和所需容量的最大值
        //首次添加时: minCapacity = size + 1 = 0 + 1 = 1
        //非首次添加时: 不进入此if，minCapacity保持size+1
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

//进入精确容量检查
//传递计算后的minCapacity
private void ensureExplicitCapacity(int minCapacity) {

    //记录结构性修改次数
    modCount++;
    //判断是否需要扩容
    //需要空间的最小值，减去当前数组的长度
    if (minCapacity - elementData.length > 0)
        //真正执行扩容
        grow(minCapacity);
}

add()带来的问题思考

为什么不直接检查elementData.length?

因为容量检查封装了懒加载逻辑(首次添加扩容到10)

封装了溢出保护逻辑(减法判断)

单一职责: add只关心"添加"，容量检查交给专门方法

为什么不先size++再赋值?

elementData[++size] = e; 会导致从索引1开始存，索引0浪费；或者需要先size–再赋值，逻辑复杂

为什么不需要检查size < elementData.length?

ensureCapacityInternal方法已经保证了容量足够，如果ensureCapacityInternal正确实现，这里不会越界，多余的检查只会浪费性能

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)带来的思考

为什么不用elementData.length == 0判断?显式指定容量为0，也是这种情况，但是不应该扩容到10

必须通过比较地址来判断，这样显式指定容量为0，不会通过此判断

为什么是扩容到10？

为什么不是1？每次添加一次就扩容一次，避免每次都扩容，一次性分配较多空间，减少扩容次数，采用空间换时间的策略

为什么是10？经验值

modCount是用来干嘛的？

modCount定义在AbstractList: protected transient int modCount = 0

记录结构性修改次数

结构性修改: 改变List大小的操作(add、remove、clear等)

非结构性修改: 不改变List大小的操作(set等)

用途: fail-fast机制

Iterator创建时记录expectedModCount = modCount

每次next()检查: if (modCount != expectedModCount) throw CME

防止遍历过程中集合被修改导致不一致

通过add方法进行了修改，为什么在此处进行++操作？而不是在add方法里？

ensureExplicitCapacity是所有容量检查的入口，包括add、addAll等方法，统一在此处++避免遗漏

为什么使用减法而非直接比较minCapacity > elementData.length

防止整数溢出攻击

假设minCapacity = Integer.MIN_VALUE(溢出后变为负数)

elementData.length = 100

minCapacity > elementData.length: -2147483648 > 100 → false(错误)

minCapacity - elementData.length > 0: 负数 - 正数 = 更小的负数 > 0 → false(正确)

实际场景:

正常情况下minCapacity = size + 1，不会溢出

但如果有人恶意调用ensureCapacity(Integer.MAX_VALUE)

减法判断能正确处理极端情况

grow()扩容源码

private void grow(int minCapacity) {
    //保存旧容量到局部变量	
    int oldCapacity = elementData.length;
    //核心扩容公式: 新容量 = 旧容量 + 旧容量的一半
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果扩容后依旧不够，直接使用minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //检查是否超过最大数组大小
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //创建新数组并复制旧数据	
    elementData = Arrays.copyOf(elementData, newCapacity);
}

//处理超大容量
private static int hugeCapacity(int minCapacity) {
    //检查整数溢出
    //可能的情况：size接近Integer.MAX_VALUE 和  size + 1溢出为负数
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    //如果需要的容量超过MAX_ARRAY_SIZE，返回Integer.MAX_VALUE
    //否则返回MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

扩容机制

核心扩容机制

int newCapacity = oldCapacity + (oldCapacity >> 1)

核心扩容公式: 新容量 = 旧容量 + 旧容量的一半

oldCapacity >> 1: 算术右移1位，等价于 oldCapacity / 2

位运算vs除法:

除法: CPU需要执行除法指令，较慢(10-20个时钟周期)

右移: CPU直接移位，极快(1个时钟周期)

编译器可能自动优化，但显式位运算更明确

1.5倍扩容的完整分析:

设初始容量为C，每次扩容为1.5倍

扩容序列: C, 1.5C, 2.25C, 3.375C, ...

添加N个元素的总扩容次数: log_1.5(N/C)

总复制元素数: C + 1.5C + 2.25C + ... ≈ 3N



如果是2倍扩容:

扩容序列: C, 2C, 4C, 8C, ...

扩容次数: log_2(N/C)

总复制元素数: C + 2C + 4C + ... ≈ 2N



1.5倍: 扩容次数多，但每次复制少，内存利用率高

2倍: 扩容次数少，但每次复制多，可能浪费内存

1.5倍是时间和空间的折中
处理超大容量时，返回时为什么有两个最大值？

MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 (推荐的安全值)

Integer.MAX_VALUE = 2147483647 (绝对最大值，可能触发JVM数组头溢出)

大多数JVM能分配Integer.MAX_VALUE大小的数组，但不保证

remove()方法源码

public E remove(int index) {
    //检查索引是否在有效范围内
    rangeCheck(index);
    //结构性修改，修改计数加1
    modCount++;
    //保存要删除的元素，用于方法返回
    //elementData(index)是私有方法
    E oldValue = elementData(index);
    //计算需要向前移动的元素个数
    //总共有size个元素(索引0到size-1)
    //删除索引index的元素
    //index之后的元素需要前移
    //index之后的元素索引: index+1, index+2, ..., size-1
    //个数: (size-1) - (index+1) + 1 = size - index - 1
    //示例:size=10, index=0: numMoved = 10-0-1 = 9 (删除首元素，移动9个)
    int numMoved = size - index - 1;
    //只有需要移动元素时才执行arraycopy
    //删除最后一个元素时numMoved=0，不需要移动
    //这是性能优化，避免无意义的内存拷贝
    if (numMoved > 0)
        //将index后面的元素向前移动一位
        //参数详解:
        //src: elementData (源数组)
        //srcPos: index+1 (源起始位置，从被删除元素的下一个开始)
        //dest: elementData (目标数组，同一个数组!)
        //destPos: index (目标起始位置，覆盖被删除元素的位置)
        //length: numMoved (要复制的元素个数)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //移除了一个元素后，大小-1
    //--size: size先减1，再使用新值
    //将最后一个位置置为null
    elementData[--size] = null;
    
    return oldValue;
}

//有效范围: 0 ≤ index < size
private void rangeCheck(int index) {
    //索引大于大小，抛出异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

remove方法问题思考

rangeCheck只检查index >= size，不检查index < 0，为什么只检查上界？

如果index < 0，访问elementData[index]时，JVM的数组访问指令会自动检查下界，自动抛出ArrayIndexOutOfBoundsException，Java代码重复检查是浪费

elementData[–size] = null为什么要置null？

内存泄漏问题:

例如：System.arraycopy后，元素E在位置3和位置4各有一份引用。位置3的E是有效元素，位置4的E是"幽灵引用"，不应该存在，如果不置null，位置4的E无法被GC回收，即使外部不再引用这个E，它仍然被elementData引用，这就是"内存泄漏"(对象无法被回收)

基本类型数组不需要置null:int[]等数组存储的是值，不是引用，没有内存泄漏问题，但ArrayList存储Object引用，必须置null

Iterator 和 fail-fast 机制

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;
    int lastRet = -1;
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
fail-fast机制解读

场景：当你使用迭代器（如 <font style="color:rgb(34, 34, 34);">for-each</font> 循环或 <font style="color:rgb(34, 34, 34);">iterator()</font>）遍历 HashMap 时。

原理：

1.迭代器在创建时，会记录当前 HashMap 的modCount值，记为expectedModCount
2. 在遍历过程中，如果其他线程（或当前线程）直接调用了put或remove方法修改了集合结构，modCount就会自增，++modCount
3. 当下一次调用迭代器的next()方法时，迭代器会对比当前的modCount和创建时的expectedModCount
4. 如果发现两者不一致，说明集合在遍历过程中被修改了，迭代器会立即抛出ConcurrentModificationException异常，而不是继续遍历可能导致数据不一致的集合。
5. 操作本身不是原子性的，所以在多线程环境下，即使抛出了异常，也不能完全依赖它来保证线程安全，它更多是一种“尽力而为”的检测机制</font>

LinkedList源码剖析

核心属性

先来看 LinkedList 的类定义和核心属性：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 链表长度
    transient int size = 0;

    // 头节点指针（第一个节点）
    transient Node<E> first;

    // 尾节点指针（最后一个节点）
    transient Node<E> last;
}
  • transient 关键字表示该字段不会被序列化。LinkedList 自己实现了 writeObject 和 readObject 方法来控制序列化逻辑，只序列化有效数据而不是整个链表结构。
  • size 初始值为 0，first 和 last 初始值为 null，表示空链表。
  • 继承 AbstractSequentialList 而非 AbstractList，暗示它更适合顺序访问而非随机访问。

Node 内部类

LinkedList 的核心数据结构是双向链表，每个节点由内部类 Node 表示：

// 静态内部类，表示链表中的每一个节点
private static class Node<E> {
    // 当前节点存储的数据
    E item;

    // 指向下一个节点的指针
    Node<E> next;

    // 指向上一个节点的指针
    Node<E> prev;

    // Node构造方法，创建一个新节点
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;   // 设置当前节点的数据
        this.next = next;      // 设置指向下一个节点的指针
        this.prev = prev;      // 设置指向上一个节点的指针
    }
}

Node 被设计为静态内部类（static class），这是有意为之的。静态内部类不持有外部类的引用，这意味着：

  1. 每个 Node 对象不会隐式引用整个 LinkedList 对象，避免了内存泄漏的风险。
  2. 如果 Node 是非静态内部类，每个节点都会额外持有一个 LinkedList 的引用，在链表很长时会造成显著的内存浪费。
  3. Node 只在 LinkedList 内部使用，private static 保证了封装性，外部无法直接操作节点。

另外，Node 的构造方法接收 prev 和 next 两个参数，使得创建节点时就能直接建立与前后节点的关联，这是一种一步到位的设计，避免了先创建再修改的多步操作。

核心属性全景图

LinkedList 对象
┌─────────────────────────────────┐
│  size = 3                       │
│  first ──────────────────┐      │
│  last ─────────────────┐ │      │
└─────────────────────────│─│──────┘
                          │ │
                          ▼ ▼
    ┌──────────────────────────────────────────────┐
    │                                              │
    ▼                                              │
┌────────┐    ┌────────┐    ┌────────┐             │
│ Node 1 │◄──►│ Node 2 │◄──►│ Node 3 │             │
│item="A"│    │item="B"│    │item="C"│             │
│prev=null│   │prev=N1 │    │prev=N2 │             │
│next=N2 │    │next=N3 │    │next=null│             │
└────────┘    └────────┘    └────────┘             │
    ▲                                              │
    │                                              │
  first                                           last

核心属性中的问题和思考

Node 为什么是双向链表？单向不行吗？

单向链表完全可以实现基本功能，但双向链表在以下场景有巨大优势：

操作 单向链表 双向链表
从尾部插入 O(n)，需要遍历到尾部 O(1)，直接通过 last 指针操作
从尾部删除 O(n)，需要找到前驱节点 O(1)，直接通过 last.prev 找到前驱
反向遍历 不支持 支持
删除指定节点 O(n)，需要找到前驱节点 O(1)，如果已有节点引用

双向链表的核心价值

LinkedList 同时实现了 Deque 接口，要求支持双端操作（头部和尾部都能插入/删除）。如果使用单向链表，从尾部删除的时间复杂度会从 O(1) 退化到 O(n)，因为需要从头遍历找到尾节点的前驱。这直接违背了 Deque 接口的设计初衷。

双向链表的代价是每个节点多一个 prev 指针，增加了约 33% 的内存开销（从 3 个引用变为 4 个引用：item、next、prev + 对象头）。但在需要频繁双端操作的场景下，这个代价是完全值得的。

为什么同时实现 List 和 Deque 接口？
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

List** 接口** 提供了有序集合的基本操作：get、add、remove、indexOf 等。

Deque** 接口** 提供了双端队列的操作：push、pop、offerFirst、pollLast 等。

一鱼多吃的接口设计

同时实现两个接口意味着 LinkedList 是一个多面手：

  • 当作 List 使用：list.add(e)、list.get(i)、list.remove(i)
  • 当作 队列（Queue） 使用：queue.offer(e)、queue.poll()、queue.peek()
  • 当作 双端队列（Deque） 使用：deque.addFirst(e)、deque.addLast(e)
  • 当作 栈（Stack） 使用：stack.push(e)、stack.pop()

但这也带来了一个隐患：API 过于庞大。LinkedList 有超过 50 个公开方法，使用者很容易混淆不同角色的方法。比如 remove() 在 List 中删除第一个出现的元素，在 Queue 中删除队头元素，语义容易产生歧义。

这也是为什么《Effective Java》建议：优先使用接口而非实现类来引用对象。如果你需要一个队列，应该写成 Deque<String> deque = new LinkedList<>() 而非 LinkedList<String> list = new LinkedList<>()，这样能明确表达你的意图，也方便后续替换实现。

add() 方法源码

add() 方法
// 将指定元素追加到列表末尾
// 等价于 addLast(e)
public boolean add(E e) {
    linkLast(e);  // 调用尾插法
    return true;  // LinkedList 的 add 操作总是返回 true
}

add() 方法总是返回 true，这与 ArrayList 的行为一致。因为 LinkedList 是无界集合（没有容量限制），不像某些集合（如 BoundedQueue）可能会因为容量不足而拒绝添加。

linkLast() 方法 – 尾插法的核心
// 将元素 e 链接到列表末尾
void linkLast(E e) {
    // 保存当前尾节点的引用到局部变量 l
    final Node<E> l = last;

    // 创建新节点：prev 指向当前尾节点，next 为 null，新的末尾
    final Node<E> newNode = new Node<>(l, e, null);

    // 将 last 指针指向新节点，新节点成为新的尾节点
    last = newNode;

    // 如果原来的尾节点为 null，说明链表之前是空的
    if (l == null)
        // 链表为空，新节点同时也是头节点
        first = newNode;
    else
        // 链表不为空，将原尾节点的 next 指向新节点，完成链接
        l.next = newNode;

    // 链表长度 +1
    size++;

    // 修改次数 +1，用于 fail-fast 机制
    modCount++;
}

假设当前链表为 [A] <-> [B]，执行 linkLast("C") 的过程如下：

步骤 2 和步骤 4 的顺序很关键：先创建新节点并设置好 prev 指针，再修改原尾节点的 next 指针。这种顺序保证了即使在多线程环境下（虽然 LinkedList 本身不是线程安全的），链表结构的一致性也能得到最大程度的保障。

modCount++ 是 Java 集合框架中的 fail-fast 机制的核心。当使用 Iterator 遍历集合时，如果在遍历过程中其他线程（或当前线程通过其他方式）修改了集合结构，Iterator 会检测到 modCount 变化并抛出 ConcurrentModificationException。

linkFirst() 方法 – 头插法
// 将元素 e 链接到列表头部
void linkFirst(E e) {
    // 保存当前头节点的引用到局部变量 f
    final Node<E> f = first;

    // 创建新节点：prev 为 null（因为是新的头部），next 指向当前头节点
    final Node<E> newNode = new Node<>(null, e, f);

    // 将 first 指针指向新节点（新节点成为新的头节点）
    first = newNode;

    // 如果原来的头节点为 null，说明链表之前是空的
    if (f == null)
        // 链表为空，新节点同时也是尾节点
        last = newNode;
    else
        // 链表不为空，将原头节点的 prev 指向新节点，完成链接
        f.prev = newNode;

    // 链表长度 +1
    size++;

    // 修改次数 +1
    modCount++;
}

add() 方法问题思考

为什么默认从尾部插入？

add(E e) 默认调用 linkLast(e) 而非 linkFirst(e)，原因是：

  1. 语义一致性：add 的语义是"追加"，符合 FIFO（先进先出）的直觉。大多数使用场景中，元素的顺序就是添加的顺序。
  2. 与 ArrayList 行为对齐：ArrayList.add() 也是在尾部追加，保持接口行为的一致性可以降低使用者的认知负担。
  3. 历史原因：List.add() 的 JavaDoc 明确规定：“Appends the specified element to the end of this list”。

如果需要从头部插入，可以显式调用 addFirst(E e) 或 offerFirst(E e)。

get() 方法源码

get() 方法
// 返回列表中指定位置的元素
public E get(int index) {
    // 检查索引是否越界：index >= 0 && index < size
    checkElementIndex(index);

    // 根据索引返回对应的节点数据
    return node(index).item;
}
node() 方法 – 核心查找逻辑
// 返回指定索引处的（非空）节点
Node<E> node(int index) {
    // 如果索引小于链表长度的一半
    if (index < (size >> 1)) {
        // 从头节点开始正向遍历
        Node<E> x = first;
        // 遍历 index 次，到达目标节点
        for (int i = 0; i < index; i++)
            x = x.next;  // 不断移动到下一个节点
        return x;
    } else {
        // 从尾节点开始反向遍历
        Node<E> x = last;
        // 遍历 (size - 1 - index) 次，到达目标节点
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // 不断移动到上一个节点
        return x;
    }
}
  • size >> 1 等价于 size / 2，使用无符号右移代替除法是一种常见的性能优化技巧（虽然在现代 JVM 中差异微乎其微）。
  • 这个优化将平均查找次数从 n/2 减少到 n/4，是一个简单但有效的折中方案。

remove() 方法源码（unlink）

remove(int) 方法
// 移除列表中指定位置的元素
public E remove(int index) {
    // 检查索引是否越界
    checkElementIndex(index);

    // 先找到目标节点，再解除它的链接
    return unlink(node(index));
}
remove(Object) 方法
// 移除列表中首次出现的指定元素
public boolean remove(Object o) {
    // 如果要删除的元素为 null
    if (o == null) {
        // 从头遍历，找到第一个 item 为 null 的节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);  // 找到后解除链接
                return true;  // 删除成功
            }
        }
    } else {
        // 从头遍历，找到第一个 item 等于 o 的节点（使用 equals 比较）
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);  // 找到后解除链接
                return true;  // 删除成功
            }
        }
    }
    // 没找到，返回 false
    return false;
}

remove(Object) 方法对 null 的特殊处理。这是因为 null.equals(...) 会抛出 NullPointerException，所以需要单独判断。这是 Java 集合框架中的标准做法，ArrayList 的 remove(Object) 也有同样的处理逻辑。

unlink() 方法 – 核心删除逻辑
// 解除某个非空节点的链接
E unlink(Node<E> x) {
    // 保存要删除节点的数据（最终要返回给调用者）
    final E element = x.item;

    // 保存要删除节点的后继节点引用
    final Node<E> next = x.next;

    // 保存要删除节点的前驱节点引用
    final Node<E> prev = x.prev;

    // 情况1：要删除的节点是头节点（prev 为 null）
    if (prev == null) {
        // 将头指针直接指向后继节点
        first = next;
    } else {
        // 不是头节点，将前驱节点的 next 跳过当前节点，直接指向后继节点
        prev.next = next;
        // 帮助 GC：断开当前节点对前驱的引用
        x.prev = null;
    }

    // 情况2：要删除的节点是尾节点（next 为 null）
    if (next == null) {
        // 将尾指针直接指向前驱节点
        last = prev;
    } else {
        // 不是尾节点，将后继节点的 prev 跳过当前节点，直接指向前驱节点
        next.prev = prev;
        // 帮助 GC：断开当前节点对后继的引用
        x.next = null;
    }

    // 清空当前节点的数据，帮助 GC
    x.item = null;

    // 链表长度 -1
    size--;

    // 修改次数 +1
    modCount++;

    // 返回被删除节点的数据
    return element;
}

unlink 的指针操作

unlink 方法需要处理四种情况：

  1. 删除头节点：prev == null，只需将 first 指向 next
  2. 删除尾节点：next == null，只需将 last 指向 prev
  3. 删除中间节点：同时修改 prev.next 和 next.prev
  4. 删除唯一节点（头尾相同）：prev == null && next == null，first 和 last 都设为 null

代码中 x.prev = null、x.next = null、x.item = null 这三行的作用：主动断开引用，帮助垃圾回收器更快地回收被删除的节点。虽然不手动置空，在方法返回后局部变量 x 也会失效，但显式置空是一种良好的编程习惯，尤其在链表这种自引用结构中。

remove() 方法问题和思考
remove(int) 和 remove(Object) 有什么区别？这会导致什么问题？
list.remove(1);     // 删除索引为 1 的元素（第二个元素）
list.remove(Integer.valueOf(1));  // 删除值为 1 的元素

这是一个经典的方法重载歧义问题。当你调用 list.remove(1) 时，1 是 int 字面量，会匹配 remove(int index) 而非 remove(Object o)。如果你想删除值为 1 的元素，必须显式装箱为 Integer.valueOf(1)。

自动装箱的陷阱

这个问题不仅存在于 LinkedList，ArrayList 也有同样的问题。在实际开发中，这是一个非常常见的 Bug 来源。

List<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

// 想删除值为 2 的元素，实际上删除了索引为 2 的元素（即 3）
list.remove(2);

// 正确做法
list.remove(Integer.valueOf(2));

LinkedList vs ArrayList 全面对比

底层结构对比
特性 ArrayList LinkedList
底层结构 动态数组（Object[]） 双向链表（Node）
内存布局 连续内存 离散内存
每个元素额外开销 无（数组直接存储引用） 两个指针（prev、next）+ Node 对象头
扩容机制 按 1.5 倍扩容 无需扩容（动态增长）
内存占用对比

LinkedList 的隐藏内存成本

以存储 100 万个 Integer 对象为例：

ArrayList 的内存开销：

  • Object[] 数组引用：100 万 x 4 字节 = 4 MB
  • 数组对象头：约 16 字节
  • 总计：约 4 MB

LinkedList 的内存开销：

  • 每个 Node 对象：对象头（12 字节）+ item 引用（4 字节）+ prev 引用（4 字节）+ next 引用（4 字节）= 24 字节
  • 100 万个 Node：100 万 x 24 字节 = 24 MB
  • 加上 Integer 对象本身的内存（每个约 16 字节）：100 万 x 16 字节 = 16 MB
  • 总计：约 40 MB

LinkedList 的内存占用大约是 ArrayList 的 10 倍！这是因为：

  1. 每个 Node 都是一个独立对象，有对象头开销
  2. 每个节点多了两个指针引用
  3. 离散内存分布可能导致内存碎片
CPU 缓存友好性

CPU 缓存为什么偏爱 ArrayList？

现代CPU有多级缓存（L1、L2、L3），缓存以缓存行（Cache Line，通常 64 字节）为单位加载数据。

ArrayList（连续内存）：

  • 数组元素在内存中紧密排列
  • CPU 读取 array[0] 时，会自动将 array[1]、array[2] 等相邻元素一起加载到缓存行中
  • 遍历时缓存命中率极高，接近 100%

LinkedList（离散内存）：

  • 节点在堆内存中随机分布
  • 读取一个节点后，下一个节点可能在内存的任意位置
  • 每次跳转几乎都会触发缓存未命中（Cache Miss），需要从主存重新加载

实测表明，在遍历场景下，ArrayList 的速度可以比 LinkedList 快 5-10 倍，即使两者的时间复杂度都是 O(n)。这就是常数因子的巨大差异。

为什么实际开发中 95% 场景用 ArrayList？

综合以上分析，ArrayList 在绝大多数场景下都优于 LinkedList：

  1. 随机访问占主导：大多数业务代码都需要频繁读取数据，ArrayList 的 O(1) 随机访问是压倒性优势
  2. CPU 缓存友好：连续内存布局带来巨大的性能红利
  3. 内存效率高：节省约 3 倍的内存
  4. JVM 优化充分：ArrayList 是 Java 中最常用的集合，JVM 对数组操作有大量内建优化（如范围检查消除、循环展开等）
  5. 尾部操作足够快：ArrayList 的尾部 add 是均摊 O(1)，覆盖了绝大多数追加场景

LinkedList 真正的优势场景非常有限：

  • 频繁在头部插入/删除
  • 需要用作队列或双端队列
  • 需要频繁在已知节点位置插入/删除（O(1)）

LinkedList 总结

LinkedList 是一个基于双向链表实现的集合类，同时具备 List、Deque、Queue 三种角色的能力。它的核心优势在于头部和尾部的 O(1) 插入/删除操作，适合用作队列、双端队列和栈。

但在实际开发中，由于随机访问 O(n)、内存占用大、CPU 缓存不友好等劣势，LinkedList 的使用场景非常有限。绝大多数情况下，ArrayList（配合 ArrayDeque 作为队列/栈）是更好的选择。

选型决策树：

需要频繁随机访问？
├── 是 → ArrayList
└── 否 → 需要频繁头部操作？
    ├── 是 → ArrayDeque（推荐）/ LinkedList
    └── 否 → 需要频繁中间插入/删除？
        ├── 是 → 考虑使用 LinkedList（但需评估实际性能）
        └── 否 → ArrayList（默认选择）

总结

ArrayList

ArrayList是基于动态数组实现的List，底层使用Object[]数组存储元素

数组在内存中是连续分配的，这意味着可以通过下标直接访问任意位置的元素，时间复杂度为O(1)，这也是ArrayList查询快的根本原因

现代CPU对连续内存有硬件预读优化，会提前将缓存行加载到L1/L2缓存中，所以ArrayList的遍历性能也非常好

扩容机制

ArrayList的初始容量默认为10。当数组空间不足时，ArrayList会自动扩容，新容量为旧容量的1.5倍

扩容的本质是创建一个更大的新数组，通过Arrays.copyOf()将旧数组元素复制过去，然后让内部引用指向新数组

这个过程涉及内存分配和数据拷贝，是比较耗时的操作，因此如果能预估数据量，建议在构造时指定初始容量以避免频繁扩容

时间复杂度分析

ArrayList的增删操作时间复杂度为O(n)，因为数组是连续的，在中间位置插入或删除元素后，需要将该位置之后的所有元素向前或向后移动一位。

但如果是尾部操作（add/remove最后一个元素），则不需要移动任何元素，时间复杂度为O(1)均摊。

线程不安全

ArrayList是非线程安全的。在多线程环境下同时进行增删操作可能导致数据不一致或数组越界

解决方案包括使用Collections.synchronizedList()包装、使用CopyOnWriteArrayList（读多写少场景），或手动加锁。

ArrayList通过modCount字段实现快速失败（fail-fast）机制：每次结构修改都会递增modCount，迭代器创建时记录当前modCount值，遍历时检查两者是否一致，不一致则抛出ConcurrentModificationException

LinkedList

LinkedList是基于双向链表实现的集合，同时实现了List和Deque两个接口，因此它既可以作为列表使用，也可以作为队列（FIFO）或栈（LIFO）使用。

LinkedList的核心数据结构是内部类Node，每个Node包含三个字段：item（存储数据）、prev（指向前一个节点）、next（指向后一个节点）。此外，LinkedList维护了first和last两个指针，分别指向链表的头节点和尾节点。

时间复杂度分析

由于链表的特性，LinkedList在头尾进行增删操作的时间复杂度为O(1)，只需修改几个指针即可完成。

但在中间位置插入或删除时，需要先遍历找到目标位置，时间复杂度为O(n)。

LinkedList的get(int index)方法也做了优化：如果目标索引小于size/2，则从头节点开始遍历；否则从尾节点开始遍历。这种二分思想虽然减少了平均遍历次数，但时间复杂度仍然是O(n)。

在实际开发中，绝大多数场景都应该优先选择ArrayList而非LinkedList

  1. 第一，LinkedList每个节点需要额外存储两个指针（prev和next），在64位JVM上每个节点约多占用40字节内存
  2. 第二，链表节点在堆内存中分散分布，CPU缓存命中率远低于ArrayList的连续数组
  3. 第三，现代JVM对数组访问有大量优化（如边界检查消除、循环展开等），使得ArrayList即使在涉及中间插入的场景下，实测性能也往往优于LinkedList

Map接口体系

HashMap

原理拆解

3.1 HashMap数据结构 (JDK 8+)
数组 + 链表 + 红黑树

         index    buckets
         ┌───┐
      0  │   │ → null
         ├───┤
      1  │   │ → [key1,val1] → [key2,val2] → ... (链表)
         ├───┤
      2  │   │ → null
         ├───┤
      3  │   │ → [key3,val3] 
         ├───┤      ↓
      4  │   │   [TreeNode] (红黑树，链表长度≥8且数组长度≥64)
         └───┘

核心属性:

transient Node<K,V>[] table;  // 桶数组
transient int size;  // 键值对数量
int threshold;  // 扩容阈值
float loadFactor;  // 负载因子(默认0.75)
3.2 put方法完整流程
1. 计算key的hash值: hash(key) = (h = key.hashCode()) ^ (h >>> 16)
2. 如果table为空，调用resize()初始化
3. 计算桶索引: i = (n - 1) & hash
4. 如果桶为空，直接创建新节点
5. 如果桶不为空:
   a. 检查首节点key是否匹配(hash和equals)
   b. 如果是树节点，调用putTreeVal()
   c. 否则遍历链表:
      - 找到相同key则覆盖value
      - 否则尾插法添加
      - 链表长度≥8，调用treeifyBin()树化
6. size++，检查是否需要扩容
3.3 扩容机制
默认初始容量: 16
负载因子: 0.75
扩容阈值: capacity * loadFactor
扩容规则: newCapacity = oldCapacity << 1 (2倍)
扩容操作: 重新计算索引，元素可能留在原位置或移动到oldCap位置
3.4 树化与退化
  • 链表转红黑树: 链表长度 ≥ 8 且 数组长度 ≥ 64
  • 红黑树转链表: 树的节点数 ≤ 6
  • 为什么是8: 泊松分布下，链表长度达到8的概率约为0.00000006

源码刨析

核心常量
//默认初始化容量：16
//为什么是16？因为容量必须是2的幂次方，16是2的4次方，是一个适中的起始值
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子：衡量哈希表填满程度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表长度≥8时转为红黑树
static final int TREEIFY_THRESHOLD = 8;
//红黑树节点≤6时退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//数组长度≥64时链表才能树化
static final int MIN_TREEIFY_CAPACITY = 64;
// 哈希表数组，长度必须是2的幂次方
transient Node<K,V>[] table;
// 当前HashMap中存储的键值对数量
transient int size;
// 扩容阈值，当size大于等于这个值时触发扩容。threshold = capacity * loadFactor
int threshold;
// 实际的负载因子
final float loadFactor;
核心常量中的问题和思考
table长度必须是2的幂?

这是HashMap设计中最精妙的地方之一。容量是2的幂次方，是为了让哈希值映射到数组索引的运算更高效。

当我们要把一个哈希值映射到数组的索引位置时，最直观的做法是取模运算：

index = hash % capacity

但取模运算（%）的效率比较低。如果capacity是2的幂次方，就可以用位运算替代取模：

index = hash & (capacity - 1)

为什么等价？因为当capacity是2的幂次方时，capacity - 1的二进制表示全是1。例如capacity = 16时，capacity - 1 = 15，二进制是1111。任何数与1111做按位与操作，就等于取这个数的低4位，效果等同于对16取模。

位运算的速度远快于取模运算，这就是为什么HashMap要求容量必须是2的幂次方。

那如果用户指定的初始容量不是2的幂次方怎么办？HashMap会通过tableSizeFor方法找到大于等于指定值的最小2的幂次方。例如用户指定10，实际容量会被调整为16。

当n是2的幂时，n-1的二进制是"全1"形式:

n = 16: n-1 = 15 = 0000 1111

n = 32: n-1 = 31 = 0001 1111

此时 (n-1) & hash 等价于 hash % n，但位运算更快

如果n不是2的幂:

n = 10: n-1 = 9 = 0000 1001

此时 & 运算只取hash的第0位和第3位

索引分布极不均匀，大量冲突!

MAXIMUM_CAPACITY = 1 << 30,为什么不是Integer.MAX_VALUE(2^31-1)?

最大容量: 2^30 ≈ 10亿

原因1: 数组索引是int，如果容量是2^31-1，扩容时newCap = oldCap << 1会溢出为负数

原因2: threshold = capacity * loadFactor，如果capacity = 2^31-1, threshold ≈ 16亿，添加超过16亿个元素在实际中不可能

原因3: 内存限制，每个Entry至少32字节(4个字段+对象头)，10亿个Entry ≈ 32GB，远超一般机器内存

DEFAULT_LOAD_FACTOR负载因子是干什么的？为什么是0.75f?

负载因子: 衡量哈希表填满程度

负载因子决定了HashMap在什么时候扩容。0.75是时间和空间的一个平衡点：

  • 负载因子越大（比如1.0）：空间利用率高，但哈希冲突概率增大，查询效率下降
  • 负载因子越小（比如0.5）：哈希冲突概率低，查询效率高，但空间浪费大

0.75是经过数学分析得出的理想值。根据泊松分布，当负载因子为0.75时，哈希冲突导致链表长度达到8的概率极低（约为0.00000006），这意味着在正常情况下，链表几乎不会转成红黑树

官方文档: “As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs”

TREEIFY_THRESHOLD是干什么的？为什么是8？

链表长度≥8时转为红黑树

为什么是8?让元素均匀分布，数学依据(见上面的泊松分布)，在良好hash函数下，链表长度≥8的概率 ≈ 0.00000006

UNTREEIFY_THRESHOLD是干什么的？为什么是6不是8？

避免频繁转换的"抖动"问题

如果 UNTREEIFY_THRESHOLD 也设为 8：插入/删除一个元素时，会频繁地在链表，红黑树之间切换，非常耗时

设置为6，中间有7作为“缓冲带”，避免在临界值附近来回切换，减少抖动

MIN_TREEIFY_CAPACITY = 64，为什么要有这个限制？

HashMap刚创建，容量很小（16），如果没有这个限制，容量为16，某一个链表长度为8，就触发树化，整个HashMap就十几个元素，就出现了红黑树，导致空间浪费，查询效率提升有限

有了这个限制后，链表长度达到8，先扩容，扩容后链表变短，用更少的内存去解决问题，扩容后的hash分布更均匀

链表过长有两种解决方案：树化 / 扩容，容量小时优先扩容（成本低，效果好），容量大时才树化（说明hash分布确实不均匀）

Node 节点完整解析
//静态内部类，不持有外部HashMap的引用
//如果是非static,每个Node都隐含持有HashMap.this引用，每个Node多4-8字节引用，浪费内存
//可能有内存泄漏: Node被其他地方引用时，HashMap无法被GC
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;//key的hash值
    final K key;//key的值
    V value;//value的值
    Node<K,V> next;//指向下一个Node节点

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    // ... 省略equals/hashCode/toString等方法
}
Node节点问题和思考
key的hash值为什么要存储，为什么不每次用key.hashCode()计算？

原因1：性能，hashCode()可能需要计算，虽然String也缓存了，但需要方法调用，直接访问int字段比方法调用快

原因2：后续要多次使用hash值，所有直接存储，避免重复调用方法计算

hash，key值为什么是final?

final修饰，不可被修改，避免修改后导致找不到

V value的相关思考

支持被put修改覆盖，HashMap非线程安全，多线程操作同一key时，value可能被覆盖

Node<K,V> next干什么用的？

HashMap底层是数组 + 链表 + 红黑树（jdk8+），遇到哈希冲突的key，哈希冲突的node放在同一个链表上，是解决哈希冲突的"链地址法"，next为null表示链表尾部

hash() 扰动函数完整解析

HashMap并不是直接用key的hashCode()返回值作为哈希值，而是做了一个扰动处理：

这就是扰动处理的作用：让哈希值的分布更加均匀，减少冲突

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  
// null key的hash值为0，HashMap允许一个null key，null key始终在索引0的位置
// (h = key.hashCode()) ^ (h >>> 16)
// h = key.hashCode(): 获取key的原始hashCode并赋值
// h >>> 16: 无符号右移16位
// ^: 按位异或(XOR)
// 效果: 将hashCode的高16位与低16位混合
}
hash()扰动函数问题和思考：为什么要扰动？

为什么要这样做？

数组长度通常不会太大（几十到几千），所以用hash & (capacity - 1)计算索引时，实际上只用了hash的低几位。例如capacity = 16时，只用低4位。

这意味着，如果两个key的hashCode只有高位不同、低位相同，它们会被映射到同一个索引位置，造成哈希冲突。

扰动处理（高16位与低16位异或）让高位的信息也能参与到索引计算中，从而减少哈希冲突。

HashMap的索引计算: index = (n - 1) & hash

这就是扰动处理的作用：让哈希值的分布更加均匀，减少冲突

问题: 当n较小时，只有hash的低位参与运算

例: n = 16 (二进制 10000) n - 1 = 15 (二进制 01111)

(n-1) & hash 只取hash的最低4位!

比如：

两个key的hashCode:

key1.hashCode() = 0000 0000 0000 0000 0000 0000 0000 1010 = 10

key2.hashCode() = 0000 0000 0000 0001 0000 0000 0000 1010 = 65546

不扰动时:

key1索引: 15 & 10 = 0000 1111 & 0000 1010 = 0000 1010 = 10

key2索引: 15 & 65546 = 0000 1111 & 0000 1010 = 0000 1010 = 10

→ 冲突! 尽管hashCode相差很大，但低位相同

扰动后:

key1.hash:

h = 10 = 0000 0000 0000 0000 0000 0000 0000 1010

h >>> 16 = 0000 0000 0000 0000 0000 0000 0000 0000

h ^ (h>>>16) = 0000 0000 0000 0000 0000 0000 0000 1010 = 10

key2.hash:

h = 65546 = 0000 0000 0000 0001 0000 0000 0000 1010

h >>> 16 = 0000 0000 0000 0000 0000 0000 0000 0001

h ^ (h>>>16) = 0000 0000 0000 0001 0000 0000 0000 1011 = 65547

现在计算索引:

key1索引: 15 & 10 = 10

key2索引: 15 & 65547 = 0000 1111 & 0000 1011 = 0000 1011 = 11

不冲突了，高位信息通过扰动影响到了低位

put（）方法，putVal（）方法
public V put(K key, V value) {
//调用内部方法putVal
//参数1: hash(key) - 对key进行扰动计算
//参数2: key - 原始key
//参数3: value - 要存储的值
//参数4: onlyIfAbsent = false
//   false表示: 如果key已存在，覆盖旧值，true表示: 如果key已存在，不覆盖(用于putIfAbsent)
//参数5: evict = true，用于LinkedHashMap的访问顺序模式
//    true表示: 这是正常插入，可能触发淘汰策略，false表示: 这是初始化阶段，不触发淘汰
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    //tab: 哈希表数组引用，p: 桶中的第一个节点，n: 数组长度，i: 计算出的索引位置
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //同时完成赋值和判断：
    //tab = table: 获取HashMap的table字段
    //table == null: 第一次put，table还未初始化
    //tab.length == 0: table是空数组(极少情况)
    //如果table数组还没有创建（第一次put），或者长度为0
    if ((tab = table) == null || (n = tab.length) == 0)
        //调用resize()方法进行初始化：resize()方法既负责初始化，也负责扩容
        //resize()做了两件事:创建新数组(首次调用时创建),返回新数组引用
        //tab = resize(): 赋值tab指向新数组
        //n = tab.length: 获取数组长度(首次是16)
        n = (tab = resize()).length;
    //p = tab[i]: 获取该位置的节点
    //p == null: 判断该位置是否为空
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果p == null:说明该位置没有元素，没有哈希冲突，直接创建新节点放入
        tab[i] = newNode(hash, key, value, null);

    else {
        //e: 用于保存找到的"相同key"的节点，k: 用于保存节点的key，避免重复获取
        Node<K,V> e; K k;
        //判断第一个节点是否就是要找的key
        //先比hash（快），再比地址（更快），最后equals（最慢但准确）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果第一个节点是TreeNode，就调用putTreeVal()红黑树插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //否则就是链表
        else {
            //binCount: 记录遍历过的节点数（用于判断是否需要树化）
            for (int binCount = 0; ; ++binCount) {
                //e = p.next: 获取当前节点的下一个节点
                //如果为空，则p是最后一个节点，在后面插入新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);//链表的尾插法
                    //检查是否需要树化
                    // binCount >= 7 (即 TREEIFY_THRESHOLD - 1)
                    // 为什么减1？
                    // binCount=0，没有遍历节点，表示链表有2个节点（p和新插入的）
                    // binCount=7 表示链表有9个节点，已经超过8个
                    // 实际上：新节点插入后，链表长度 = binCount + 2
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        //进行树化-链表转红黑树
                        treeifyBin(tab, hash);
                    //插入完成，结束遍历
                    break;
                }
                //e 是当前遍历到的节点和当前的keyhash相同 且 (地址相同 或 equals相等)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    //找到相同key，跳出循环，e指向该节点
                    break;
                p = e;
            }
        }
        //处理找到的相同key节点
        //e不为空，说明找到了相同的节点
        if (e != null) {
            //保存旧值
            V oldValue = e.value;
            // 判断是否覆盖：
            // !onlyIfAbsent: 如果不是"仅不存在时才插入"，则覆盖
            // oldValue == null: 或者旧值为null，也覆盖
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //回调方法（LinkedHashMap用，用于LRU）
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //插入完成后，执行
    //用来记录该集合被结构性修改的次数
    ++modCount;
    //如果size（元素总数）大于threshold（扩容阈值），就调用resize()扩容
    if (++size > threshold)
        resize();
    //这是一个回调方法（Hook Method），在 HashMap 类中，它的实现是空的
    //它的主要目的是为了支持子类（主要是 LinkedHashMap）在插入新节点后执行特定的逻辑
    afterNodeInsertion(evict);
    return null;
}
putVal方法问题和思考
为什么不在构造器里初始化table?

懒加载策略:很多HashMap创建后可能从未put元素,避免不必要的内存分配,new HashMap()不分配数组，首次put才分配

为什么不直接table = resize()，还要使用一个局部变量？

局部变量tab比字段table访问快，后续代码大量使用tab，缓存到局部变量提升性能，这是编译器优化技巧，开发者显式写出

i = (n - 1) & hash解析

i = (n - 1) & hash是核心的索引计算公式

n-1的低位全是1(因为n是2的幂)，与hash按位与，取hash的低位

例如: n=16, hash=37

(16-1) & 37 = 15 & 37 = 0000 1111 & 0010 0101 = 0000 0101 = 5

newNode（）方法

创建新节点放入数组位置i

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

next = null: 新节点是链表的唯一节点

处理存在哈希冲突的情况

如果table[i]位置已经有元素了，就出现哈希冲突。处理哈希冲突的步骤：

  1. 先检查第一个节点的key是否和要插入的key相同（hash值相同且key.equals()为true）。如果相同，直接覆盖value。
  2. 如果不同，判断该位置是红黑树还是链表。
  3. 如果是红黑树，调用红黑树的putTreeVal方法。
  4. 如果是链表，遍历链表：
  • 遍历过程中如果找到key相同的节点，覆盖value
  • 如果遍历到链表尾部都没有找到，在尾部插入新节点
  • 插入后检查链表长度是否达到8，如果达到8且数组长度达到64，将链表转为红黑树
为什么链表转红黑树需要两个条件？

链表转红黑树需要同时满足两个条件：

  1. 链表长度 >= 8（TREEIFY_THRESHOLD）
  2. 数组长度 >= 64（MIN_TREEIFY_CAPACITY）

为什么还需要数组长度 >= 64？

因为如果数组很小（比如默认初始容量16），即使链表长度达到8，更好的做法是先扩容数组，而不是转红黑树。扩容后，元素会重新分布到不同的索引位置，链表长度自然就变短了。

转红黑树是一种"最后的手段"，只有在数组已经足够大、哈希冲突仍然严重的情况下才使用。

resize方法
final Node<K,V>[] resize() {
    //保存旧数组信息
    Node<K,V>[] oldTab = table;// 旧数组引用
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧容量
    int oldThr = threshold;// 旧阈值
    int newCap, newThr = 0;
    
    //计算新容量和新阈值
    if (oldCap > 0) {
        // 情况1：旧容量已超过最大值，不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;// 阈值设为最大
            return oldTab;// 不再扩容，直接返回
        }
        // 情况2：正常扩容，容量翻倍（oldCap << 1）
        //扩容前：capacity=16, threshold=12, size=13
        //扩容后：capacity=32, threshold=24
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;  // 阈值也翻倍
    }
    // 情况3：oldCap == 0 但 oldThr > 0（指定了初始容量的构造方法，但还没有插入元素）
    else if (oldThr > 0)
        //扩容到阈值，用threshold作为新容量
        newCap = oldThr;
    // 情况4：oldCap == 0 且 oldThr == 0（无参构造，首次put）
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;      // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  // 12
    }
    
    // 计算新阈值（针对情况3）
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        //新阈值，旧阈值都要小于最大容量
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //阈值也对应修改
    threshold = newThr;
    
    //创建新数组并迁移数据
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    if (oldTab != null) {
        // 遍历旧数组的每个桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;//记录当前桶的第一个节点
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;  // 帮助GC
                
                // 情况A：桶中只有一个节点
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                
                // 情况B：桶中是红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                
                // 情况C：桶中是链表（JDK8核心优化）
                else {
                    Node<K,V> loHead = null, loTail = null;  // 低位链表（原位置）
                    Node<K,V> hiHead = null, hiTail = null;  // 高位链表（原位置+oldCap）
                    Node<K,V> next;
                    
                    do {
                        next = e.next;
                        // 核心判断：hash & oldCap == 0 ?
                        // 为0：在新数组中的位置不变（仍是j）
                        // 为1：在新数组中的位置 = j + oldCap
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 将两条链表放入新数组
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
resize方法问题和思考

扩容是HashMap中最复杂的操作。当size超过threshold时，HashMap会创建一个容量为原来2倍的新数组，把所有元素重新分配到新数组中。

为什么要扩容？

HashMap的本质是用空间换时间。数组越大，哈希冲突的概率越低，查询效率越高。但数组太大浪费内存。所以HashMap采用动态扩容的策略：数据少的时候用小数组，数据多了就扩大数组。

扩容后元素怎么重新分配？

这是扩容的核心问题。旧数组中的每个元素，在新数组中的位置只有两种可能：

原位置（索引不变）

原位置 + 旧数组长度（索引偏移旧容量）

为什么？因为新容量是旧容量的2倍，而容量是2的幂次方。在计算索引时，新容量比旧容量多了一个高位。所以只需要看hash值的这个高位是0还是1：

容量 = 2^n 时，计算索引就是取 hash 的低 n 位

旧容量 = 16 = 2^4 → 取 hash 的低 4 位

新容量 = 32 = 2^5 → 取 hash 的低 5 位

关键：新容量只比旧容量多看了"第5位"（从右往左数）

如果是0：新索引 = 旧索引

如果是1：新索引 = 旧索引 + 旧容量

假设：某个key的hash值 = 53（二进制 110101）

旧容量 = 16（二进制 10000，n=4）

新容量 = 32（二进制 100000，n=5）

hash 的二进制： 1 1 0 1 0 1

位位置： 5 4 3 2 1 0

第5位 = 1

旧索引计算（取低4位）：hash & (16-1) = 110101 & 001111 = 000101 = 5

新索引计算（取低5位）：hash & (32-1) = 110101 & 011111 = 110101 = 21

观察：21 = 5 + 16（旧索引 + 旧容量）

┌─────────────────────────────────────────────────────────────────┐
│                    扩容前后的索引变化                             │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  旧数组（容量16）：                                              │
│  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐                   │
│  │  0  │  1  │ ... │  5  │ ... │ 15  │                       │
│  └─────┴─────┴─────┴─────┴─────┴─────┴─────┘                   │
│                      ↑                                          │
│                   桶[5]                                         │
│                                                                 │
│  新数组（容量32）：                                              │
│  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐       │
│  │  0  │  1  │ ... │  5  │ ... │ 15  │ 16  │ ... │ 21  │       │
│  └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘       │
│                      ↑                 ↑                        │
│                   位置不变          位置+16                      │
│                 (hash&16=0)       (hash&16=16)                  │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

这个设计非常巧妙，避免了重新计算hash，只需要做一次位运算判断。

新数组 容量32

旧数组 容量16

hash新增位为0

hash新增位为1

索引3: 链表

索引3: 链表低位部分

索引19: 链表高位部分 3+16
扩容的线程安全问题

HashMap在扩容过程中，如果有其他线程同时进行put操作，可能会导致：

  • 数据丢失：多个线程同时扩容，互相覆盖
  • 死循环（JDK 1.7）：头插法在多线程扩容时可能导致链表成环
  • 数据不一致：部分元素没有被正确迁移

这就是为什么HashMap是线程不安全的。在多线程环境下，应该使用ConcurrentHashMap。

get()方法源码
/**
 * 返回指定键所映射的值，如果不存在则返回null
 * 
 * @param key 要查找的键
 * @return 对应的值，不存在返回null
 */
public V get(Object key) {
    Node<K,V> e;                                    // 声明一个节点变量用于存储查找结果
    return (e = getNode(hash(key), key)) == null   // 调用getNode方法查找节点，如果结果为null
            ? null                                  // 则返回null
            : e.value;                              // 否则返回节点的value值
}

get()方法本身非常简洁，它只是一个"门面方法"，真正的查找逻辑委托给了getNode()方法。这里使用了三元运算符，使代码更加紧凑。值得注意的是，它先调用hash(key)计算键的哈希值，然后将哈希值和键一起传递给getNode()方法。

深入分析：为什么get方法要设计得如此简洁？这是典型的"单一职责"设计模式的应用。get方法只负责"对外接口"，而getNode方法负责"核心实现"。这种设计使得其他需要查找功能的方法（如containsKey）可以复用getNode的逻辑，避免代码重复。

getNode()方法源码
/**
 * HashMap的核心查找方法
 * 
 * @param hash 键的哈希值（经过扰动处理后的）
 * @param key  要查找的键
 * @return 找到的节点，不存在返回null
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;        // 哈希表的数组引用（table字段）
    Node<K,V> first, e;     // first：桶的第一个节点；e：遍历时的当前节点
    int n;                  // 数组长度
    K k;                    // 用于存储节点的key
    
    // 步骤1：检查table是否已初始化，且长度大于0，且目标桶不为空
    if ((tab = table) != null               // 将table赋值给tab，检查是否已初始化
            && (n = tab.length) > 0         // 将长度赋值给n，检查长度是否大于0
            && (first = tab[(n - 1) & hash]) != null) {  // 计算桶索引，获取第一个节点，检查是否为空
        // 步骤2：检查第一个节点是否就是目标节点
        if (first.hash == hash              // 首先比较hash值（快速失败机制）
                && ((k = first.key) == key  // 然后用==比较引用（同一对象直接返回）
                    || (key != null         // key不为null时
                        && key.equals(k)))) // 使用equals比较内容
            return first;                    // 找到了，返回第一个节点
        
        // 步骤3：第一个节点不是目标，需要遍历链表或红黑树
        if ((e = first.next) != null) {     // 检查是否有后续节点
            // 步骤3.1：如果是红黑树结构
            if (first instanceof TreeNode)  // 判断是否为树节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);  // 调用红黑树查找方法
            
            // 步骤3.2：如果是链表结构，遍历查找
            do {
                if (e.hash == hash          // 先比较hash值
                        && ((k = e.key) == key  // 再用==比较引用
                            || (key != null     // key不为null时
                                && key.equals(k))))  // 使用equals比较内容
                    return e;                // 找到了，返回当前节点
            } while ((e = e.next) != null); // 移动到下一个节点，直到链表末尾
        }
    }
    // 步骤4：未找到，返回null
    return null;
}

getNode()方法是HashMap查找操作的核心，它完整实现了从哈希定位到节点匹配的全过程。整个方法可以分为四个关键步骤：

  1. 前置检查：确保table已初始化且目标桶存在
  2. 首节点匹配：直接检查桶的第一个节点
  3. 结构化查找：根据数据结构类型（链表/红黑树）执行不同的查找策略
  4. 返回结果：找到返回节点，未找到返回null
getNode方法问题思考
为什么先比较hash再比较key？
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))

答案：这是一种性能优化的"快速失败"机制。

深入分析：

  1. hash比较是整数比较：直接比较两个int值，速度极快（单条CPU指令）
  2. equals可能很慢：如果key是复杂对象，equals方法可能涉及大量字段比较
  3. hash不同则必然不相等：根据HashMap的契约，相等的对象必须有相同的hash值，因此hash不同可以直接跳过
  4. 短路求值：如果hash不匹配，后面的equals根本不会执行

这种设计体现了"先做低成本检查，再做高成本检查"的编程智慧。

假设HashMap中有1000个节点分布在100个桶中，每个桶平均10个节点。如果直接用equals比较，最坏情况需要调用10次equals。而先比较hash，由于hash冲突的概率较低，大多数情况下只需要1次整数比较就能排除不匹配的节点。

为什么用==和equals双重判断？
(k = first.key) == key || (key != null && key.equals(k))

答案：两种比较方式各有用途，组合使用可以覆盖所有场景。

比较方式 适用场景 性能 特点
== 引用比较 最快 比较内存地址，同一对象立即返回true
equals 内容比较 较慢 比较对象内容，需要执行方法调用

深入分析：

  1. ==比较引用：如果是同一个对象（内存地址相同），直接返回true，无需调用equals
  2. equals比较内容：对于内容相同但不是同一对象的情况（如两个new String(“abc”)），需要equals来判断
  3. key != null检查：防止空指针异常，因为调用null.equals()会抛出NPE
  4. 短路或运算：如果==为true，equals不会执行，节省性能
get方法的时间复杂度分析
场景 数据结构 时间复杂度 说明
最好情况 任意 O(1) 目标节点正好是桶的首节点
平均情况（链表） 链表 O(1) 假设hash分布均匀，链表长度很短
最坏情况（链表） 链表 O(n) 所有key都hash冲突，退化为长链表
平均情况（红黑树） 红黑树 O(log n) 树化后的查找效率
最坏情况（红黑树） 红黑树 O(log n) 红黑树保证查找效率

深入分析：

为什么HashMap声称get是O(1)？

这基于一个重要假设：良好的hash函数使元素均匀分布。在理想情况下：

  • 每个桶的链表长度很短（通常≤8）
  • 查找只需要常数次比较

JDK 1.8的优化：

当链表长度≥8且数组长度≥64时，链表会树化为红黑树。这使得最坏情况从O(n)改善到O(log n)。

链表查找: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → [目标]  // O(n)
红黑树查找:        4                    // O(log n)
               /     \
              2       6
             / \     / \
            1   3   5   8
                       /
                      [目标]

在实际应用中，应该注意以下几点以保证get方法的性能：

  1. 选择好的hash函数：自定义对象作为key时，应正确重写hashCode方法
  2. 避免hash冲突：设计良好的key结构，减少冲突概率
  3. 设置合适的初始容量：避免频繁扩容导致的性能损耗
  4. 负载因子选择：默认0.75是时间和空间的平衡点
对比项 JDK7 JDK8
底层结构 数组 + 链表 数组 + 链表 + 红黑树
链表插入方式 头插法 尾插法
哈希扰动 4次位移+异或 1次位移+异或
扩容时机 先扩容再插入 先插入再扩容
链表转红黑树阈值 无此机制 链表长度≥8且数组长度≥64
红黑树转链表阈值 无此机制 红黑树节点数≤6

JDK8引入红黑树是为了解决哈希冲突严重时链表过长导致的查询效率问题。链表查询时间复杂度为O(n)，红黑树为O(log n)，当链表长度达到8时，查询效率差距明显。

深入分析：为什么JDK8简化了哈希扰动？

JDK7的哈希扰动进行了9次位移和异或操作（4次位移+5次异或），目的是让hash值的高位和低位都参与到数组下标的计算中，减少哈希冲突。JDK8简化为1次位移+1次异或，原因是：

  1. 现代JVM对位移和异或操作优化较好
  2. 引入红黑树后，哈希冲突的代价降低
  3. 简化计算可以提升整体性能

HashMap JDK7 vs JDK8 核心区别

数据结构对比
对比项 JDK7 JDK8
底层结构 数组 + 链表 数组 + 链表 + 红黑树
链表插入方式 头插法 尾插法
哈希扰动 4次位移+异或 1次位移+异或
扩容时机 先扩容再插入 先插入再扩容
链表转红黑树阈值 无此机制 链表长度≥8且数组长度≥64
红黑树转链表阈值 无此机制 红黑树节点数≤6

JDK8引入红黑树是为了解决哈希冲突严重时链表过长导致的查询效率问题。链表查询时间复杂度为O(n)，红黑树为O(log n)，当链表长度达到8时，查询效率差距明显。

深入分析：为什么JDK8简化了哈希扰动？

JDK7的哈希扰动进行了9次位移和异或操作（4次位移+5次异或），目的是让hash值的高位和低位都参与到数组下标的计算中，减少哈希冲突。JDK8简化为1次位移+1次异或，原因是：

  1. 现代JVM对位移和异或操作优化较好
  2. 引入红黑树后，哈希冲突的代价降低
  3. 简化计算可以提升整体性能
JDK7 头插法
原链表：null ← A ← B ← C（head指向C）

插入新节点D：
Step1: D.next = head（D指向C）
Step2: head = D（head指向D）

结果：null ← A ← B ← C ← D（head指向D）
JDK8 尾插法
原链表：A → B → C → null

插入新节点D：
Step1: C.next = D（C指向D）
Step2: D.next = null（D指向null）

结果：A → B → C → D → null
深入分析：头插法 vs 尾插法的性能差异

头插法的时间复杂度为O(1)，无需遍历链表；尾插法需要遍历到链表尾部，时间复杂度为O(n)。但JDK8引入了tail指针记录尾部位置，使得尾插法也达到O(1)。更重要的是，尾插法保持了链表的插入顺序，这是解决死循环问题的关键。

JDK7多线程死循环原理

死循环产生条件

  1. 多线程并发扩容：多个线程同时触发扩容操作
  2. 头插法导致链表反转：迁移过程中链表顺序被反转
  3. 形成环形链表：线程切换导致指针指向异常，形成闭环

死循环问题只在JDK7中存在，JDK8通过尾插法解决了这个问题。但JDK8的HashMap仍然不是线程安全的！

==================== 初始状态 ====================
初始链表：A → B → null
数组table[0]指向A

==================== 线程1执行到一半暂停 ====================
线程1执行transfer方法：
  e = A, next = B  （已读取，还未执行插入操作）
  
此时线程1被挂起，线程2开始执行

==================== 线程2完成扩容 ====================
线程2完整执行transfer方法（头插法）：

Step1: 迁移A
  e = A, next = B
  A.next = newTable[0] = null
  newTable[0] = A
  e = B

Step2: 迁移B（头插法，B插到A前面）
  e = B, next = null
  B.next = newTable[0] = A  // B指向A
  newTable[0] = B           // B成为新的头节点
  e = null

线程2完成后新链表：B → A → null

==================== 线程1继续执行 ====================
线程1恢复执行（注意：它还持有旧的e和next值）：

Step1: 处理A
  e = A, next = B（这是线程1之前保存的值）
  A.next = newTable[0] = B  // A指向B（此时newTable[0]是B）
  newTable[0] = A           // A成为头节点
  e = B

Step2: 处理B
  e = B, next = null
  B.next = newTable[0] = A  // B指向A（形成环！）
  newTable[0] = B           // B成为头节点
  e = null（但A.next = B，B.next = A）

==================== 最终结果 ====================
结果：A ↔ B 形成环形链表

get操作时：无限循环 → CPU 100%
JDK8如何解决死循环

JDK8通过尾插法保持链表原有顺序，避免了链表反转问题。

// JDK8 resize方法中的链表迁移部分（简化版）
if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            if (e.next == null)
                // 单节点直接放入新桶
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)
                // 红黑树拆分
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            else {
                // 链表迁移：保持原有顺序（尾插法）
                Node<K,V> loHead = null, loTail = null;  // 低位链表
                Node<K,V> hiHead = null, hiTail = null;  // 高位链表
                Node<K,V> next;
                do {
                    next = e.next;
                    // 根据hash值的新增高位决定放入哪个链表
                    if ((e.hash & oldCap) == 0) {
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;  // 尾插法
                        loTail = e;
                    } else {
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;  // 尾插法
                        hiTail = e;
                    }
                } while ((e = next) != null);
                // 将链表放入新数组
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
}
  1. JDK8的尾插法为什么不会形成环形链表？
    • 尾插法保持链表原有顺序，每个节点的next指针只会被设置一次，不会出现循环指向
  2. loHead和hiHead分别代表什么？
    • loHead：原位置的链表头（hash新增位为0）
    • hiHead：原位置+oldCap位置的链表头（hash新增位为1）

线程安全问题

JDK7线程安全问题
问题 原因 后果
死循环 头插法+并发扩容 CPU 100%，服务不可用
数据丢失 并发put覆盖 数据不一致
size计数错误 ++size非原子操作 统计不准确
JDK8线程安全问题
问题 原因 后果
数据覆盖 并发put到同一桶 后插入的数据覆盖先插入的数据
size计数错误 ++size非原子操作 统计不准确
脏读 读到中间状态 数据不一致

JDK8的尾插法只解决了死循环问题，HashMap仍然不是线程安全的！

线程安全解决方案
方案 适用场景 性能 特点
ConcurrentHashMap 高并发读写 最高 JDK7分段锁，JDK8 CAS+synchronized
Collections.synchronizedMap 低并发 一般 全表锁，简单易用
Hashtable 不推荐使用 差 全表锁，遗留类
ConcurrentHashMap使用示例
import java.util.concurrent.ConcurrentHashMap;

// 创建ConcurrentHashMap
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// 线程安全的put操作
map.put("key", 1);

// 线程安全的get操作
Integer value = map.get("key");

// 原子操作：如果不存在则插入
map.putIfAbsent("key", 2);

// 原子操作：计算并更新
map.compute("key", (k, v) -> v == null ? 1 : v + 1);
问题和思考
  1. 为什么Hashtable不推荐使用？
    • Hashtable使用synchronized修饰所有方法，全表锁，并发性能差
    • Hashtable不允许null键和null值，使用不便
  2. ConcurrentHashMap为什么性能高？
    • JDK7使用分段锁（Segment），只锁一部分数据
    • JDK8使用CAS+synchronized，只锁单个桶，并发度更高
  3. Collections.synchronizedMap的原理是什么？
    • 使用装饰器模式，包装一个普通HashMap，所有方法都加synchronized

为什么重写equals必须重写hashCode

原理解释
import java.util.HashMap;

// 自定义Person类
class Person {
    String name;
    int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    // 只重写equals方法
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;           // 同一个对象，直接返回true
        if (obj == null) return false;          // 对象为null，返回false
        if (getClass() != obj.getClass())       // 类型不同，返回false
            return false;
        Person other = (Person) obj;            // 强制类型转换
        return age == other.age &&              // 比较age属性
               (name == null ? other.name == null : name.equals(other.name));  // 比较name属性
    }
    
    // 没有重写hashCode方法！使用Object默认的hashCode
}

public class Main {
    public static void main(String[] args) {
        // 创建两个"相等"的Person对象
        Person p1 = new Person("张三", 20);
        Person p2 = new Person("张三", 20);
        
        System.out.println(p1.equals(p2));  // true，因为重写了equals
        System.out.println(p1.hashCode() == p2.hashCode());  // false！默认hashCode不同
        
        // HashMap中出现问题
        HashMap<Person, String> map = new HashMap<>();
        map.put(p1, "A");     // p1被放入某个桶
        System.out.println(map.get(p2));  // null！因为p2的hashCode不同，定位到不同的桶
    }
}

深入分析：HashMap的查找过程

  1. 计算key的hashCode
  2. 根据hashCode计算数组下标
  3. 遍历该位置的链表/红黑树
  4. 使用equals方法比较key

如果hashCode不同，根本不会进入同一个桶，equals永远不会被调用！

正确的实现方式
import java.util.Objects;

class Person {
    String name;
    int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;                    // 同一对象引用，直接返回true
        if (obj == null || getClass() != obj.getClass()) // null或类型不同，返回false
            return false;
        Person other = (Person) obj;                     // 类型转换
        return age == other.age &&                       // 比较基本类型age
               Objects.equals(name, other.name);         // 比较引用类型name（处理null）
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);  // 使用Objects工具类计算hashCode
    }
}
规范要求
规则 说明
equals相等 → hashCode必须相等 保证相等的对象在HashMap中能正确找到
hashCode相等 → equals不一定相等 允许哈希冲突，不同的对象可以有相同的hashCode
hashCode一致性 同一对象多次调用hashCode应返回相同值（除非对象被修改）

Java规范规定：如果两个对象equals返回true，那么它们的hashCode必须相同。违反这个规则会导致HashMap、HashSet等基于哈希的集合无法正常工作。

问题和思考
  1. 为什么hashCode相等但equals不一定相等？
    • 这是哈希冲突的概念，不同的对象可能计算出相同的hashCode，但equals比较时可能不相等
  2. Objects.hash()方法的原理是什么？
    • 将多个字段组合计算，使用质数31作为乘数，减少哈希冲突
  3. 为什么选择31作为乘数？
    • 31是质数，能减少哈希冲突
    • 31 * i 等价于 (i << 5) - i，可以用位运算优化
    • 不会导致整数溢出

HashMap JDK7 vs JDK8 总结

面试要点速记
  1. JDK7 vs JDK8核心区别：数据结构、插入方式、哈希扰动、扩容时机
  2. JDK7死循环原因：头插法+并发扩容→链表反转→环形链表
  3. JDK8解决方案：尾插法保持顺序，但仍有线程安全问题
  4. 线程安全选择：ConcurrentHashMap > Collections.synchronizedMap > Hashtable
  5. equals和hashCode：必须同时重写，保证一致性
最佳实践
// 1. 多线程环境使用ConcurrentHashMap
ConcurrentHashMap<String, Object> concurrentMap = new ConcurrentHashMap<>();

// 2. 自定义对象作为key时，同时重写equals和hashCode
class MyKey {
    private String id;
    
    @Override
    public boolean equals(Object obj) { /* ... */ }
    
    @Override
    public int hashCode() { /* ... */ }
}

// 3. 初始化时指定容量，避免频繁扩容
HashMap<String, Object> map = new HashMap<>(16);  // 指定初始容量

// 4. 使用computeIfAbsent等原子方法
map.computeIfAbsent("key", k -> new ArrayList<>()).add("value");

LinkedHashMap

原理解析

LinkedHashMap是HashMap的子类，在HashMap的基础上维护了一个双向链表，从而实现了有序性。它既可以保持插入顺序，也可以保持访问顺序（LRU），这使得它成为实现LRU缓存的理想选择。

  • 继承自HashMap，复用HashMap的核心功能
  • 通过双向链表维护元素的迭代顺序
  • 支持两种排序方式：插入顺序（默认）和访问顺序
  • 非线程安全，需要外部同步

源码刨析

核心属性
// 双向链表头节点，指向最早插入或最久未访问的元素
transient LinkedHashMap.Entry<K,V> head;

// 双向链表尾节点，指向最新插入或最近访问的元素
transient LinkedHashMap.Entry<K,V> tail;

// 访问顺序控制参数
// true = 访问顺序（LRU模式），访问过的元素会被移到链表尾部
// false = 插入顺序（默认），按照插入顺序排列
final boolean accessOrder;

为什么需要head和tail两个指针？

双向链表需要头尾指针才能在O(1)时间复杂度内完成头部删除和尾部插入操作。当accessOrder=true时，每次访问都需要将元素移到尾部，有了tail指针可以直接定位插入位置；当需要淘汰最老元素时，head指针可以直接定位删除位置。

  • head：链表头部，迭代时第一个返回的元素
  • tail：链表尾部，迭代时最后一个返回的元素
  • accessOrder：决定迭代顺序的关键参数，默认为false
Entry内部类
static class Entry<K,V> extends HashMap.Node<K,V> {
    // before指针：指向链表中的前一个节点
    Entry<K,V> before, after;
    // after指针：指向链表中的后一个节点
    
    // 构造方法
    Entry(int hash, K key, V value, Node<K,V> next) {
        // 调用父类HashMap.Node的构造方法
        // hash: 哈希值，用于确定桶位置
        // key: 键
        // value: 值
        // next: 哈希桶中的下一个节点（解决哈希冲突的链表）
        super(hash, key, value, next);
    }
}

Entry的双重身份

LinkedHashMap.Entry继承自HashMap.Node，因此它具有双重身份：

  1. 哈希表节点：通过next指针维护哈希桶中的链表/红黑树结构
  2. 双向链表节点：通过before和after指针维护迭代顺序

这种设计使得LinkedHashMap可以在不增加太多内存开销的情况下，同时支持O(1)的查找和有序遍历。

核心属性问题思考
LinkedHashMap如何继承HashMap并维护顺序？

LinkedHashMap通过以下方式继承并扩展HashMap：

  1. 继承关系：LinkedHashMap继承HashMap，复用了HashMap的数组、哈希计算、扩容等核心逻辑
  2. Entry扩展：LinkedHashMap.Entry继承HashMap.Node，增加了before和after指针
  3. 钩子方法：HashMap预留了afterNodeAccess()、afterNodeInsertion()、afterNodeRemoval()三个空方法，LinkedHashMap重写这些方法来维护链表
  4. 迭代器重写：LinkedHashMap重写了迭代器，按照双向链表顺序遍历，而不是桶数组顺序
accessOrder参数的作用？

accessOrder是LinkedHashMap的核心参数，决定了元素的迭代顺序：

accessOrder值 行为 适用场景
false（默认） 插入顺序，元素按照put的顺序排列 需要保持插入顺序的场景
true 访问顺序（LRU），get/put操作会将元素移到链表尾部 LRU缓存实现
afterNodeAccess()方法源码

该方法在访问元素后被调用，当accessOrder=true时，将访问的元素移动到链表尾部（最近访问位置）。

void afterNodeAccess(Node<K,V> e) { // e: 被访问的节点
    LinkedHashMap.Entry<K,V> last;  // last: 记录移动前的尾节点
    
    // 只有当accessOrder=true且被访问节点不是尾节点时才需要移动
    if (accessOrder && (last = tail) != e) {
        // 将e强转为LinkedHashMap.Entry类型，获取双向链表指针
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        
        // 将p的after置为null，因为p即将成为新的尾节点
        p.after = null;
        
        if (b == null)
            // 如果b为null，说明p是头节点
            // 移动p后，a成为新的头节点
            head = a;
        else
            // 如果b不为null，将b的after指向a，跳过p
            b.after = a;
        
        if (a != null)
            // 如果a不为null，将a的before指向b，跳过p
            a.before = b;
        else
            // 如果a为null，说明p原本就是尾节点
            // 但前面已经判断过(last = tail) != e，所以这个分支理论上不会执行
            // 这里是防御性编程，更新last为b
            last = b;
        
        if (last == null)
            // 如果last为null，说明链表原本只有一个节点p
            // p移动后仍是唯一的节点，设为头节点
            head = p;
        else {
            // 将p链接到链表尾部
            p.before = last;    // p的前驱指向原尾节点
            last.after = p;     // 原尾节点的后继指向p
        }
        // 更新tail指针，p成为新的尾节点
        tail = p;
        
        // 增加修改次数，用于快速失败机制
        // 这样迭代器可以检测到并发修改
        ++modCount;
    }
}

为什么移动到尾部而不是头部？

LRU（Least Recently Used，最近最少使用）缓存的淘汰策略是淘汰最久未使用的数据。在双向链表中：

  • 尾部：最近访问/插入的元素（热数据）
  • 头部：最久未访问的元素（冷数据，淘汰候选）

将访问的元素移到尾部，使得链表从头到尾的顺序就是"从最久未访问到最近访问"的顺序，淘汰时只需删除head即可。

afterNodeAccess()在以下场景被调用：

  1. get()方法获取元素后
  2. put()方法更新已存在的键值对后
  3. replace()方法替换值后

注意：只有当accessOrder=true时才会触发移动操作。

afterNodeAccess()问题思考
为什么需要判断(last = tail) != e？

这个判断有两个作用：

  1. 性能优化：如果被访问的节点已经是尾节点，说明它已经是"最近访问"的位置，无需移动
  2. 避免不必要的modCount增加：移动操作会增加modCount，可能影响正在进行的迭代
移动操作的时间复杂度是多少？

移动操作只涉及指针修改，时间复杂度为O(1)。这是双向链表的优势，也是LinkedHashMap适合实现LRU的原因之一。

为什么需要增加modCount？

modCount用于实现"快速失败"（fail-fast）机制。如果在迭代过程中链表结构被修改（如移动节点），迭代器会检测到modCount变化并抛出ConcurrentModificationException，避免数据不一致。

afterNodeInsertion()方法源码

该方法在插入元素后被调用，用于在必要时删除最老的元素（链表头部）。

void afterNodeInsertion(boolean evict) { // evict: 是否允许驱逐（淘汰）元素
    LinkedHashMap.Entry<K,V> first;  // first: 链表头节点（最老的元素）
    
    // 如果evict=true（正常模式）且头节点不为null
    // 且removeEldestEntry返回true，则删除头节点
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        // 获取要删除的键
        K key = first.key;
        // 调用HashMap的removeNode方法删除节点
        // 参数含义：hash值, 键, 值(为null表示不匹配值), 
        //          matchValue(是否匹配值), movable(是否移动节点)
        removeNode(hash(key), key, null, false, true);
    }
}

// 默认实现：永远返回false，不删除任何元素
// 子类可以重写此方法来实现自定义的淘汰策略
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;  // 默认不删除任何元素
}

evict参数的作用

evict参数控制是否允许驱逐元素：

  • true：正常模式，允许驱逐（put、putAll等操作时）
  • false：创建模式，不允许驱逐（如反序列化、构造函数中从其他Map复制时）
LRU缓存实现示例
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 基于LinkedHashMap实现的LRU缓存
 * @param <K> 键类型
 * @param <V> 值类型
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;  // 最大容量
    
    /**
     * 构造方法
     * @param maxCapacity 最大容量
     */
    public LRUCache(int maxCapacity) {
        // 参数说明：
        // 1. 初始容量
        // 2. 负载因子
        // 3. accessOrder = true，启用访问顺序（LRU模式）
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }
    
    /**
     * 重写removeEldestEntry方法，实现自动淘汰
     * 当size > maxCapacity时返回true，触发删除最老的元素
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }
    
    // 测试示例
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);
        
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        System.out.println(cache);  // {A=1, B=2, C=3}
        
        cache.get("A");  // 访问A，A移到尾部
        System.out.println(cache);  // {B=2, C=3, A=1}
        
        cache.put("D", 4);  // 插入D，B被淘汰（最久未访问）
        System.out.println(cache);  // {C=3, A=1, D=4}
    }
}

ConcurrentHashMap

概述

ConcurrentHashMap是线程安全的HashMap实现，采用CAS + synchronized保证并发安全。

线程安全

JDK7使用分段锁（Segment）

JDK8使用CAS + synchronized（锁粒度更细）

不允许null键和null值

迭代器弱一致性

JDK8核心属性

// 最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认初始容量
private static final int DEFAULT_CAPACITY = 16;

// 负载因子
private static final float LOAD_FACTOR = 0.75f;

// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 哈希表数组
transient volatile Node<K,V>[] table;

// 扩容时的新数组
private transient volatile Node<K,V>[] nextTable;

// 控制标识符
// -1: 正在初始化
// -N: 有N-1个线程正在扩容
// >0: 下次扩容的阈值
private transient volatile int sizeCtl;

put()方法源码

public V put(K key, V value) {
    return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 不允许null键和null值
    if (key == null || value == null) throw new NullPointerException();
    
    // 计算hash值
    int hash = spread(key.hashCode());
    int binCount = 0;
    
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        
        // 情况1：数组为空，初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        
        // 情况2：目标桶为空，CAS直接插入
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;  // CAS成功，跳出循环
        }
        
        // 情况3：正在扩容，帮助扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        
        // 情况4：正常插入，synchronized锁住头节点
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 链表处理
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == 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) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 检查是否需要树化
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 更新计数，检查是否需要扩容
    addCount(1L, binCount);
    return null;
}

CAS

CAS‌（Compare-And-Swap，即“比较并交换”）是一种‌无锁的并发控制机制‌，用于在多线程环境下实现原子操作。

CAS 操作涉及三个参数：

内存值 V‌：当前共享变量在内存中的实际值。

预期值 A‌：线程期望该变量当前的值。

新值 B‌：若预期成立，将要写入的新值。

流程：

1. <font style="color:rgb(51, 51, 51);">比较内存值 V 是否等于预期值 A。</font>
2. <font style="color:rgb(51, 51, 51);">若相等，则将 V 更新为 B，并返回操作成功。</font>
3. <font style="color:rgb(51, 51, 51);">若不相等，则不进行任何修改，返回操作失败。</font>

整个比较与交换过程由‌一条 CPU 原子指令‌完成，确保线程安全，无需加锁

总结

HashMap

HashMap是Java集合框架中最核心的类之一，JDK8中其底层数据结构为数组 + 链表 + 红黑树。

  1. HashMap使用一个Node<K,V>[]数组作为哈希表，数组的每个位置称为一个"桶"（bucket）。
  2. 当多个key的hash值定位到同一个桶时，就会产生哈希冲突，HashMap采用**链地址法（拉链法）**解决冲突——冲突的元素用链表串起来。
  3. 当某个桶的链表长度过长（≥8）且数组容量≥64时，链表会转换为红黑树，将查询时间复杂度从O(n)优化O(log n)。
    哈希计算是HashMap高效的关键。
  4. HashMap首先调用key的hashCode()方法获取原始哈希值，然后通过扰动函数(h = key.hashCode()) ^ (h>>>16)将高16位与低16位进行异或运算，目的是让高位信息也参与到索引计算中，减少哈希冲突。
  5. 索引的计算方式为hash & (n-1)，其中n是数组长度。这等价于hash % n，但位运算的效率远高于取模运算。

这也解释了为什么HashMap的数组长度必须是2的幂次方——只有当n是2的幂时，n-1的二进制才是全1，才能让hash值的每一位都参与到索引计算中，保证元素均匀分布。

put操作的完整流程：

先计算hash值，如果数组为空则调用resize()初始化；

然后通过hash & (n-1)定位桶索引；如果桶为空则直接插入新节点；如果桶不为空，先检查首节点是否匹配（先比hash再比equals），匹配则覆盖value；

如果是红黑树则调用putTreeVal；

如果是链表则遍历查找，找到则覆盖，找不到则在尾部插入（尾插法）。

插入完成后检查链表长度是否达到树化阈值，以及元素总数是否超过扩容阈值。

扩容机制：

当元素总数size超过阈值threshold（等于capacity × loadFactor）时触发扩容。

新数组容量为旧数组的2倍。

JDK8对扩容时的元素迁移做了重要优化：由于新容量是旧容量的2倍，元素的索引要么保持不变，要么等

于"原索引 + 旧容量"，判断依据是hash & oldCap是否为0。

这个设计避免了重新计算每个元素的hash值，只需一次位运算就能确定新位置，大幅提升了扩容效率。

HashMap是非线程安全的。JDK7中由于采用头插法，多线程并发扩容可能导致链表成环，引发get操作死循环。

JDK8改为尾插法解决了死循环问题，但仍然存在数据覆盖、size计数不准确等并发问题。多线程环境下应使用

ConcurrentHashMap。

LinkedHashMap 底层原理

LinkedHashMap是HashMap的子类，在HashMap的基础上增加了一条双向链表来维护元素的迭代顺序。

它的Entry继承自HashMap.Node，额外增加了before和after两个指针，用于串联双向链表。

ConcurrentHashMap 底层原理

ConcurrentHashMap是线程安全的高性能HashMap。它的实现经历了重大演进：JDK7采用分段锁，JDK8改为CAS + synchronized。

JDK7中，ConcurrentHashMap将整个哈希表分成若干个Segment（默认16个），每个Segment继承ReentrantLock，相当于一个独立的HashMap。

不同Segment的操作可以并发执行，同一Segment内的操作需要竞争锁。这种设计的缺点是并发度固定（等于Segment数量），且锁粒度仍然较粗。

JDK8彻底抛弃了Segment，数据结构与普通HashMap一致（数组 + 链表 + 红黑树），但将锁粒度缩小到了桶级别。

put操作时：如果目标桶为空，使用CAS（Compare-And-Swap）无锁插入；如果桶不为空，使用synchronized锁住头节点（只锁一个桶），然后在桶内执行链表或红黑树操作。

这种设计使得并发度理论上只受数组长度限制，远高于JDK7的固定16。

get操作全程不需要加锁，这是ConcurrentHashMap性能优异的关键。

原因是Node的val和next字段都用volatile修饰，保证了多线程下的可见性。读线程通过volatile语义可以直接看到其他线程的写结果，无需加锁。

ConcurrentHashMap不允许null键和null值，原因是多线程环境下的二义性问题：如果允许null值，当get返回null时，无法区分"key不存在"和"key存在但value为null"。

HashMap可以在单线程下用containsKey精确判断，但ConcurrentHashMap的多线程环境下，get和containsKey之间可能有其他线程修改，结果不可靠。

JDK8还引入了多线程协助扩容机制。当一个线程触发扩容时，其他线程如果在操作中发现某个桶已被标记为正在迁移（ForwardingNode，hash值为MOVED），会参与协助扩容，将旧数组的一部分桶迁移到新数组。这种设计充分利用了多核CPU的并行能力，大幅提升了扩容速度。

Set接口体系

HashSet

原理概述

HashSet是基于HashMap实现的Set集合，它不保证元素的迭代顺序，允许null元素，非线程安全。

  • 底层使用HashMap存储元素
  • 元素作为HashMap的key存储
  • 不保证迭代顺序
  • 允许一个null元素
  • 非线程安全

源码刨析

核心属性
// 底层使用HashMap存储元素
private transient HashMap<E,Object> map;

// 虚拟值，作为HashMap中所有key对应的value
private static final Object PRESENT = new Object();

深入分析：为什么用Object作为value？

HashSet只需要存储唯一的元素（key），不需要value。但HashMap要求每个key必须对应一个value，所以使用一个共享的Object对象作为所有key的value，节省内存。

构造方法
// 默认构造，创建一个空的HashMap
public HashSet() {
    map = new HashMap<>();
}

// 指定初始容量
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

// 指定初始容量和负载因子
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
核心方法
// 添加元素，调用HashMap的put方法
public boolean add(E e) {
    return map.put(e, PRESENT) == null;  // 返回null表示之前不存在
}

// 删除元素
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

// 判断是否包含元素
public boolean contains(Object o) {
    return map.containsKey(o);
}

// 获取元素个数
public int size() {
    return map.size();
}
HashSet总结

LinkedHashSet源码刨析

原理概述

LinkedHashSet是HashSet的子类，使用LinkedHashMap存储元素，保持元素的插入顺序。

源码解析

public class LinkedHashSet<E> extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    
    // 构造方法，底层创建LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);  // 调用HashSet的专用构造方法
    }
    
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
    
    public LinkedHashSet() {
        super(16, .75f, true);
    }
}

// HashSet的专用构造方法（包级私有）
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);  // 创建LinkedHashMap
}

TreeSet源码刨析

原理概述

TreeSet是基于TreeMap实现的有序Set，元素按照自然顺序或自定义比较器排序。

  • 底层使用TreeMap存储元素
  • 元素有序（自然顺序或比较器）
  • 不允许null元素（如果使用自然排序）
  • 非线程安全

源码刨析

核心属性
// 底层使用NavigableMap（TreeMap的实现接口）
private transient NavigableMap<E,Object> m;

// 虚拟值，与HashSet相同
private static final Object PRESENT = new Object();
构造方法
// 默认构造，使用自然排序
public TreeSet() {
    this(new TreeMap<E,Object>());
}

// 使用自定义比较器
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
核心方法
// 添加元素
public boolean add(E e) {
    return m.put(e, PRESENT) == null;
}

// 获取第一个元素（最小）
public E first() {
    return m.firstKey();
}

// 获取最后一个元素（最大）
public E last() {
    return m.lastKey();
}

// 获取小于指定元素的最大元素
public E lower(E e) {
    return m.lowerKey(e);
}

// 获取大于指定元素的最小元素
public E higher(E e) {
    return m.higherKey(e);
}

总结

HashSet 底层原理

HashSet的底层实现非常简单——它完全基于HashMap，所有操作都委托给内部的HashMap实例来完成。HashSet中的元素作为HashMap的key存储，而value统一使用一个名为PRESENT的静态常量Object对象。

去重原理是HashSet的核心机制。当调用add(e)时，实际执行的是map.put(e, PRESENT)

HashMap的put方法会先计算e的hashCode定位桶，如果桶为空则直接插入；如果桶不为空则遍历链表或红黑树，用equals方法逐一比较。

只有当hashCode相同且equals返回true时，才认为元素已存在，不执行插入。

因此，HashSet的去重完全依赖于hashCode和equals两个方法，如果自定义对象作为HashSet的元素，必须同时重写这两个方法，且必须保持一致：equals为true的两个对象，hashCode必须相同。

HashSet允许一个null元素（因为HashMap允许一个null key），不保证迭代顺序（取决于hash计算结果），非线程安全。查询、插入、删除的时间复杂度均为O(1)。

LinkedHashSet 底层原理

LinkedHashSet继承自HashSet，但它的底层使用LinkedHashMap而非HashMap来存储元素。

这个切换通过HashSet的一个包级私有的隐藏构造方法实现——当LinkedHashSet调用=super(initialCapacity, loadFactor, true)时，HashSet会创建LinkedHashMap实例。

LinkedHashMap的双向链表机制使得LinkedHashSet能够保持元素的插入顺序。

与HashSet相比，LinkedHashSet只是多了维护链表指针的开销，插入、查询、删除的时间复杂度仍然是O(1)，但内存占用略高。适用场景是需要去重且需要按插入顺序遍历的情况。

fail-fast机制

原理概述

fail-fast机制是Java集合框架中的一种错误检测机制。当多个线程对集合进行结构上的修改时，迭代器会快速感知并抛出ConcurrentModificationException。

核心原理：modCount检测

// AbstractList中的modCount定义
protected transient int modCount = 0;  // 记录集合被修改的次数

// 迭代器中的expectedModCount
private class Itr implements Iterator<E> {
    int cursor;
    int expectedModCount = modCount;  // 期望的修改次数

    public E next() {
        checkForComodification();  // 每次next前检查
        // ...
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

触发场景示例

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");

Iterator<String> it = list.iterator();
list.add("c");  // modCount变为3，但迭代器的expectedModCount仍为2

it.next();  // 抛出ConcurrentModificationException

集合选型指南

List选型决策树

是否需要频繁随机访问？
  ├─ 是 → ArrayList
  └─ 否 → 是否频繁在头尾操作？
           ├─ 是 → LinkedList / ArrayDeque
           └─ 否 → ArrayList

ArrayList vs LinkedList 的本质区别：

  • ArrayList基于动态数组实现，内存连续，CPU缓存友好
  • LinkedList基于双向链表实现，每个节点独立分配内存
  • 在大多数场景下，ArrayList性能优于LinkedList，即使涉及中间插入操作

Map选型决策树

是否需要排序？
  ├─ 是 → TreeMap（自然排序）或 自定义Comparator
  └─ 否 → 是否需要保持插入顺序？
           ├─ 是 → LinkedHashMap
           └─ 否 → HashMap（默认选择）
           
是否多线程环境？
  ├─ 是 → ConcurrentHashMap
  └─ 否 → HashMap

Set选型决策树

是否需要排序？
  ├─ 是 → TreeSet
  └─ 否 → 是否需要保持插入顺序？
           ├─ 是 → LinkedHashSet
           └─ 否 → HashSet（默认选择）

总结

  1. 默认选择：List选ArrayList，Map选HashMap，Set选HashSet
  2. 需要排序：选TreeMap/TreeSet，或HashMap + 手动排序
  3. 需要顺序：选LinkedHashMap/LinkedHashSet
  4. 高并发：选ConcurrentHashMap、CopyOnWriteArrayList、LongAdder
  5. 队列：优先选ArrayDeque，而非LinkedList
  6. 避免使用：Vector、Hashtable、Stack等遗留类
# java # python # 开发语言
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

当 AI 修图师装上“万能插头“：MCP 如何改变修图工作流

avatar AI编程社区
cover

2026年8月开发者实战指南：ChatGPT Plus / Pro + Codex 如何协同完成需求分析、编码、测试、调试与代码审查

avatar AI编程社区
cover

投资一台B300，部署Claude Opus 5多久才能回本？

avatar AI编程社区