朝花夕拾

Appearance

Java 集合框架 ​

字数: 0 字 时长: 0 分钟

常用集合类图 ​

集合框架总览.webp

ArrayList ​

ArrayList接口分析.webp

RandomAccess 接口

RandomAccess 是一个标志接口，表明它支持快速随机访问（在 ArrayList 中通过元素序号快速获取元素对象）

底层数据结构

ArrayList 底层数据结构.webp

ArrayList 底层是一个 Object[] 数组，初始长度为 10。

数组扩容

扩容判断.webp

当数组元素个数达到数组容量大小极限时，会触发数组动态扩容。

  • 默认扩容为原容量的 1.5 倍
  • 当需要的 minCapacity 大于计算值时，直接使用 minCapacity （比如 addAll() 大量数据）
  • 空列表首次添加元素时，默认扩容为 DEFAULT_CAPACITY 容量为 10

数组扩容源码

java
private Object[] grow() {
    return grow(size + 1); // 至少需要 size+1 的容量
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength( // 新的扩容计算方式
            oldCapacity,
            minCapacity - oldCapacity, // 最小增长量
            oldCapacity >> 1           // 默认增长量（原容量50%）
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else { // 首次扩容的特殊处理
        return elementData = new Object[Math.max(
            DEFAULT_CAPACITY, // 默认初始容量10
            minCapacity
        )];
    }
}

LinkedList ​

LinkedList底层数据结构.webp

LinkedList 底层是一个双向链表结构，每个节点除了存储元素还需要存储节点的前后指针，因此内存占用相比ArrayList多。

随机访问效率为 O(n) (需要遍历),不如 ArrayList 的 O(1) (数组下标直接访问)

迭代器遍历效率， ArrayList 也更快 （连续内存遍历更友好）

不过 LinkedList 在头尾添加元素效率更高 O(1) ,因此除了频繁在头尾/操作添加元素，其他场景 ArrayList 更适合

LinkedList狗都不用.webp

哈哈哈哈，集合框架作者本人发声说自己从没使用过 LinkedList 。

HashMap ​

hashMap重要参数.webp

jdk8 以上，HashMap 底层数据结构为数组+链表+红黑树 结构，其中红黑树和链表直接可以根据阈值互相转换。链表节点数达到 8 时，转换为红黑树；如节点减少为 6 时则红黑树又退化为链表

核心存储结构

java
// JDK 8+ 的节点定义
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;     // 通过key的hashCode()计算得出
    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;
    }
}

transient Node<K,V>[] table;  // 哈希桶数组
transient int size;           // 实际Key-Value对数
int threshold;                // 扩容阈值 = capacity * loadFactor
final float loadFactor;       // 负载因子，默认0.75

hashMap数据结构.webp

HashMap 中的 key 通过 hashCode() 计算出 hash 值，然后通过 hash 值计算出在哈希桶数组中的位置

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

如果多个key 的 hash 值通过计算出的哈希桶位置相同，则通过链表结构存储

如果链表长度过长，查询效率过低（链表查询效率 O(n)）,则转换为红黑树结果 （O(log n)）提高性能

默认的链表转换为红黑树的阈值为 8 ，因为哈希冲突导致链表长度达到 8 的概率极低；树化会增加内存和操作复杂度，只是为了极端情况的优化