ArrayList 深度解析

1.1 底层数据结构

// JDK1.8源码关键定义
transient Object[] elementData; // 实际存储数据的数组
private int size; // 当前元素数量

1.2 核心机制

① 扩容机制

// 添加元素核心逻辑（JDK1.8）
public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 容量检查
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY(10), minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); // 触发扩容
}

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);
}

扩容流程图解：

添加元素 → 检查容量不足 → 计算新容量（原1.5倍）
       ↓               ↑
   数组拷贝（System.arraycopy）

② 随机访问性能

// 时间复杂度O(1)
public E get(int index) {
    rangeCheck(index);
    return elementData(index); // 直接数组下标访问
}

③ 插入删除性能瓶颈

// 中间插入示例（需移动元素）
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

元素移动示意图：

原数组: [A][B][C][D][ ][ ]
插入X到位置1:
1. 将B,C,D后移 → [A][ ][B][C][D][ ]
2. 放入X → [A][X][B][C][D][ ]

二、LinkedList 深度解析

2.1 底层数据结构

// JDK1.8双向链表节点定义
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

2.2 核心操作原理

① 插入元素

// 头部插入（O(1)时间复杂度）
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

② 随机访问性能

// get方法通过折半查找优化（仍为O(n)）
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    if (index < (size >> 1)) { // 前一半从头遍历
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else { // 后一半从尾遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

③ 内存占用分析

每个元素需要额外存储：

• 前驱节点引用（4/8字节）
• 后继节点引用（4/8字节）
• 对象头（12字节）
  总内存开销约为：(对象头) + 元素数据 + 2*指针

三、HashMap 深度解析

3.1 数据结构演进

JDK1.7 vs JDK1.8

3.2 核心实现原理

① 哈希函数优化

// JDK1.8的hash()方法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

设计目的：将高16位与低16位异或，减少哈希碰撞概率

② 链表树化条件

static final int TREEIFY_THRESHOLD = 8; // 链表转树阈值
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化容量

// 树化逻辑（部分代码）
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // 优先扩容
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 执行树化操作...
    }
}

③ 扩容机制（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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 双倍扩容
    }
    // ...其他情况处理
    
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 数据迁移逻辑（高低位拆分）...
    return newTab;
}

④ 红黑树退化为链表

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

3.3 put操作全流程

graph TD
    A[计算key的hash值] --> B{桶位置是否为空?}
    B -- 是 --> C[直接创建新节点插入]
    B -- 否 --> D{是否是树节点?}
    D -- 是 --> E[红黑树插入]
    D -- 否 --> F[遍历链表]
    F --> G{存在相同key?}
    G -- 是 --> H[覆盖value]
    G -- 否 --> I[尾部插入新节点]
    I --> J{链表长度≥8?}
    J -- 是 --> K{数组长度≥64?}
    K -- 是 --> L[转换为红黑树]
    K -- 否 --> M[扩容]

四、三大集合对比总结

五、高频面试问题

Q1：HashMap为什么用红黑树不用AVL树？

• 红黑树优势：插入删除操作旋转次数更少（最多3次）树高约束较宽松（黑高度平衡）适合读多写少场景

Q2：HashMap如何解决哈希冲突？

• 链地址法：相同桶位置形成链表/树
• 再哈希法：通过扰动函数优化哈希值分布
• 扩容机制：减少单个桶的冲突概率

Q3：ArrayList与LinkedList性能对比误区

• 实际测试结果（百万次操作）：

六、最佳实践建议

1. ArrayList初始化：预估数据量设置初始容量
2. HashMap优化：

// 避免频繁扩容 
Map<String, Object> map = new HashMap<>(expectedSize); 
// 或使用Guava工具 
Maps.newHashMapWithExpectedSize(100);

遍历选择：ArrayList优先用for循环，LinkedList必须用Iterator，HashMap遍历entrySet效率最高

通过深入理解这些集合的底层实现，可以更高效地进行Java程序开发与性能优化。