一、Eclipse Collections (EC)

Eclipse Collections 是由 Goldman Sachs 开发并捐赠给 Eclipse 基金会的高性能 Java 集合库。它不仅提供了丰富的集合 API，还特别注重内存效率和性能优化，尤其擅长处理基本类型集合。本文将深入探讨 EC 的核心特性、使用场景及其与其他集合库的对比。

1、为什么需要 EC

1）Java 标准集合的局限

尽管 java.util 集合（如 ArrayList, HashMap）广泛使用，但在现代应用中存在明显短板：

2）EC 的核心价值

• 原生支持基本类型集合（如 IntList, LongSet）
• 丰富的函数式 API（类似 Scala、Kotlin 集合）
• 高性能实现（比 JDK 快 20–50%）
• 完整的可变/不可变集合体系
• 内存优化（如 UnifiedMap 比 HashMap 更紧凑）

二、核心特性

1、两大集合家族：可变 vs 不可变

2、基本类型集合支持

EC 为常用基本类型提供专用集合（不支持 char/float 等冷门类型）：

3、函数式 API（开发效率利器）

1） 对比 jdk 流

EC 将高阶函数直接集成到集合接口，无需转 Stream：

List<Integer> result = list.stream()
    .filter(x -> x > 0)      // 步骤1：过滤
    .map(x -> x * x)         // 步骤2：平方
    .collect(Collectors.toList());


MutableIntList result = intList
    .select(x -> x > 0)      // 第1次遍历 → 返回新 IntList [3, 5]
    .collect(x -> x * x);    // 第2次遍历 → 返回新 IntList [9, 25]


MutableIntList result = intList.asLazy()
    .select(x -> x > 0)
    .collect(x -> x * x)
    .toList(); // 触发执行

2）遍历次数

3）常用操作

4、Map

1）基本类型 Map（避免装箱）

EC 的 IntObjectHashMap 和 FastUtil 的 Int2ObjectOpenHashMap 在原理上高度相似，都采用开放寻址 + 平行数组。

2）特殊 Map 类型

三、底层原理：为什么又快又好？

之所以在性能和内存效率上显著优于 JDK 标准集合，甚至在某些场景下媲美 FastUtil，源于其精心设计的底层数据结构与运行时优化策略。以下是其三大核心技术支柱：

1、高效数据结构

1）UnifiedMap / UnifiedSet：告别 Entry 对象

JDK 的 HashMap 和 HashSet 每个元素都封装在一个 Node<K,V> 或 Entry 对象中，带来显著的内存开销（每个对象至少 24–32 字节，含对象头、哈希码、指针等）。

而 EC 的 UnifiedMap 采用 “平行数组 + 单桶位图” 的紧凑布局：

• Unified 的含义：统一存储，消除中间对象。

• 键（keys）和值（values）分别存储在两个独立的 Object[] 数组中

   所有 key 存在一个数组，所有 value 存在另一个数组
  Object[] keys;     // [key1, key2, key3, ...]
  Object[] values;   // [val1, val2, val3, ...]
  

• 使用一个 int[] 或 long[] 作为哈希表索引与状态标记（空/占用/删除）

2）原始类型集合：零装箱，原生数组

• 对于 MutableIntList、MutableLongSet 等原始类型集合：
• 内部直接使用 int[]、long[] 等原生数组
• 完全避免 Integer、Long 包装对象的创建

2、迭代与计算优化

1）高度优化的迭代器

EC 的迭代器（如 MutableList.iterator()）经过深度内联优化，减少方法调用开销：

• 大量方法标记为 final
  • final 方法不能被重写 → 调用目标在编译期就完全确定 → JIT 可安全地将其内联。
  • 最大化 JIT 内联机会，消除虚方法调用开销
• 循环体无虚方法调用（JIT 更易优化）
• 支持 快速失败（fail-fast） 但开销极低

2）惰性求值支持

通过 .asLazy() 可将链式操作转为惰性流：

• 仅遍历一次
• 无中间集合分配
• 全程保持原始类型，无装箱

MutableIntList result = intList
    .asLazy()
    .select(x -> x > 0)
    .collect(x -> x * x)
    .toList(); // 此时才执行

3、 内存布局与 CPU 缓存友好

1）连续内存访问

• 原始类型集合（如 int[]）在内存中连续存放
• 遍历时具有极佳的 空间局部性
• 极大减少 CPU 缓存未命中

2）减少指针跳转

JDK 的 LinkedList 或 HashMap 的 Node 链表会导致频繁的 非连续内存跳转，而 EC 的数组式结构避免了这一点。

四、与 FastUtil 和 JDK的对比

1、三大集合体系概览

2、原始类型支持

3、内部结构

1）FastUtil：开放寻址——“逻辑单桶”

public class Int2IntOpenHashMap {
    protected transient int[] key;      // 所有键
    protected transient int[] value;    // 所有值
    protected transient boolean[] used; // 标记槽位是否被占用（可选，部分版本用特殊值如 0 表示空）
    protected final float loadFactor;
}

a、工作原理：

• 哈希函数计算出初始位置 pos = hash(key) % capacity
• 直接检查 key[pos]：
  • 若 used[pos] == false → 空，插入
  • 若 key[pos] == target → 命中
  • 否则 → 线性探测：pos = (pos + 1) & mask，继续检查
• 键和值始终在同一索引 pos 上

b、内存布局示意图

index:   0    1    2    3    4    5    6    7
key:   [10] [20] [ ]  [30] [ ]  [ ]  [40] [ ]
value: [1]  [2]  [?] [3]  [?] [?] [4]  [?]
used:  [T]  [T]  [F] [T]  [F] [F] [T]  [F]

c、特点：

• 访问一个 entry 只需 一次索引计算，读 key[i] 和 value[i] 是相邻内存
• 探测过程在连续地址上进行 → CPU 缓存预取高效

d、致命缺陷（对象场景）

• 无法区分 null 键 和 空槽 → 必须禁止 null key。
• 删除后留 tombstone：key[i] = DEFUNCT_KEY，该槽位永远不能真正释放。
  • 导致：有效负载因子（actual fill ratio）持续下降。
  • 后果：即使只用了 50% 容量，也可能因 tombstone 触发扩容 → 内存浪费反超 EC。

2）EC：分离式结构——“物理三数组”

注意：EC 没有使用开放寻址，而是采用 “哈希 + 链式/探测”混合策略（早期版本用链表，新版本多用二次探测，但仍依赖 states[]）

public final class IntIntHashMap {
    private int[] keys;        // 键数组
    private int[] values;      // 值数组
    private byte[] states;     // 状态数组：0=free, 1=occupied, 2=removed
    private int occupiedCount;
}

a、工作原理：

• 哈希计算出初始位置 index
• 检查 states[index]：
  • 若为 0（free）→ 插入到 keys[index], values[index]
  • 若为 1（occupied）且 keys[index] == key → 命中
  • 否则 → 按探测序列（如二次探测）找下一个 index'
• 每次访问都要查三个数组的同一个下标

b、内存布局示意图：

keys:    [10, 20, ?, 30, ?, ?, 40, ?]
values:  [1,  2,  ?, 3,  ?, ?, 4,  ?]
states:  [1,  1,  0, 1,  0, 0, 1,  0]
          ↑   ↑      ↑         ↑
         idx=0,1,3,6 被占用

c、问题：

• CPU 读取 keys[i] 时，values[i] 和 states[i] 可能不在同一缓存行

• 尤其当数组很大时，三个数组分散在堆的不同区域 → 缓存未命中率升高

4、FQA

1）内存布局与性能

实测：存储 1 亿条 int → int 映射

a、JDK： HashMap

• 每个键值对封装为 Node<K,V> 对象
• 对象分散在堆中 → 指针跳转多、缓存不友好
• 装箱 + 对象头 → 内存膨胀 3–4 倍

b、EC： UnifiedMap / MutableIntIntMap

• 采用 双数组 + 状态标记：虽无 Entry 对象，但通常维护 三个数组
  • keys[] 存储键
  • values[] 存储值
  • states[]（或位图）标记槽位状态（空/占用/删除）
• 1个哈希槽位 = index，但 keys[index], values[index], occupied[index] 是三个独立数组的元素

• 无 Entry 对象，大幅减少对象数量，但哈希冲突仍通过线性探测或二次探测处理（非开放寻址）

• 内存访问需跨多个数组 → 缓存行利用率略低
• 设计更注重通用性与安全性（如支持 null 键/值）

c、FastUtil： Int2IntOpenHashMap

• 采用 开放寻址哈希（Open Addressing）
  • 所有数据连续存放，所有键值直接存入两个连续 int[] 数组
  • 一个哈希槽位 = (key[i], value[i])，冲突时 i → i+1 → i+2...
  • 冲突时通过 线性探测 + 位运算优化的哈希函数 解决
  • 无链表、无对象、无间接引用，
• 内存布局极致紧凑，CPU 缓存命中率极高

2）EC 为何不采用开放寻址

EC 的设计哲学更偏向 通用性与安全性：FastUtil 为性能牺牲了灵活性，EC 为通用性接受了一点性能折衷

1. 支持 null 键/值：FastUtil 的原始类型 Map 不支持 null（因用特殊值如 0 表示空），而 EC 允许（通过 states[] 区分）
2. 删除更安全：开放寻址中删除需标记为 “deleted”（否则破坏探测链），EC 的 states[] 天然支持
3. API 一致性：EC 的对象集合（如 UnifiedMap）也用类似三数组结构，保持内部统一

3）都是“数组”，但内存访问模式天差地别

4）EC 为何更适合业务系统？

5）如何选型？