前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

JavaUtil包：http://gitbook.net/java/util/index.html

一、FastUtil：高性能 Java 集合库

1、FastUtil 是什么

FastUtil 是由意大利米兰大学（University of Milan）开发的开源高性能集合库，专为处理 原始类型（primitive types） 的集合和映射而设计。

• 核心目标：避免装箱、减少内存、提升缓存局部性、加速 CPU 访问

• GitHub: https://github.com/vigna/fastutil

• Maven:

  <dependency>
      <groupId>it.unimi.dsi</groupId>
      <artifactId>fastutil</artifactId>
      <version>8.5.13</version>
  </dependency>
  

2、为什么需要 FastUtil？—— Java 标准集合的痛点

1）泛型不支持基本类型

Java 泛型只接受引用类型，所以必须用 Integer、Long 等包装类：

Map<Integer, Integer> map = new HashMap<>();
map.put(123, 456); // 自动装箱 → Integer.valueOf(123)

2）自动装箱/拆箱带来严重开销

3）内存占用对比

节省 75%+ 内存，性能提升 2~4 倍

二、FastUtil 的底层优化原理

1、开放寻址哈希

1）JDK HashMap（链地址法）

• 使用 Node<K,V>[] table
• 每个节点是一个独立对象（含 next 指针、hash、key、value）
• 冲突时挂链表 → 超过阈值转红黑树

2）FastUtil（开放寻址 + 线性探测）

• 所有键值对存储在两个平行数组中：

  int[] key;     // 存原始类型 key
  Object[] value; // 存 value（可为对象或原始类型）
  

• 无 Entry 对象 → 内存紧凑

• 冲突处理：线性探测（Linear Probing）

  • 探测序列：(h(k) + i) & mask（i = 0,1,2,…）
  • 使用位运算 & mask 替代 % length（快 10 倍+）

• 删除策略：使用 墓碑标记（Tombstone）

  • 删除时打标记，不移动后续元素 → O(1) 删除
  • 真正清理发生在：
    • 扩容（rehash）
    • 显式调用 trim() / compact()
    • 删除比例过高时自动压缩
  • 优点：删除快；
  • 缺点：可能浪费内存（大量 tombstone）

2、高效哈希函数

• 对 int/long 使用 位混合（bit spreading），例如：

  static int mix(int x) {
      x = (x ^ (x >>> 16)) * 0x45d9f3b;
      x = (x ^ (x >>> 16)) * 0x45d9f3b;
      return x ^ (x >>> 16);
  }
  

• 减少哈希聚集（clustering）

• 默认负载因子 0.75（可配置），平衡速度与内存

3、无泛型、无装箱

• 所有方法直接操作原始类型：

  public int put(int key, int value);
  public boolean containsKey(int key);
  public int get(int key);
  

• 零装箱 → 无临时对象 → 无 GC 压力

三、关键类型详解（Map / Set / List）

1、Map （核心优势区）

2、Set

3、List

四、Int2ObjectOpenHashMap<V>

1、什么是 Int2ObjectOpenHashMap

Int2ObjectOpenHashMap 是 FastUtil 库（一个高性能 Java 集合框架）提供的专门用于将 int 类型键映射到对象值 的哈希表实现。它属于 FastUtil 中的 “primitive maps”（原始类型映射）家族，专为提升性能和减少内存占用而设计。

• 包路径：it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap
• 泛型形式：Int2ObjectOpenHashMap<V>
• 用途：高效地将 int 键映射到任意对象类型 V。

2、底层结构

1）关键结构

int[] key;        // 存 int 键（原始类型）
Object[] value;   // 存 V 值（引用类型）

2）构造函数关键逻辑

• 默认负载因子：0.75f（与 JDK 一致）
• 初始容量计算：HashCommon.arraySize(expected, f) → 返回 ≥ expected / f 的最小 2 的幂
• 索引计算：hash & mask（mask = capacity - 1）→ 比 % 快 10 倍以上
• 扩容阈值：maxFill = capacity * loadFactor

public Int2ObjectOpenHashMap(int expected, float f) {
    // 负载因子合法性校验：if (!(f <= 0.0F) && !(f >= 1.0F))
    // 逻辑等价：0 < f < 1（负载因子必须在 0 到 1 之间）。
      if (!(f <= 0.0F) && !(f >= 1.0F)) {
          if (expected < 0) {
              throw new IllegalArgumentException("The expected number of elements must be nonnegative");
          } else {
              this.f = f;
              // 核心中的核心：计算哈希表的初始容量（2 的幂）。
              this.minN = this.n = HashCommon.arraySize(expected, f);
             // 计算索引掩码（比如 n=4096 → mask=4095）
             // 后续用hash & mask替代hash % n计算索引（位运算比取模快 10 倍 +）。
              this.mask = this.n - 1;
             // 计算扩容触发阈值（容量 × 负载因子）。
              this.maxFill = HashCommon.maxFill(this.n, f);
              this.key = new int[this.n + 1];
              this.value = new Object[this.n + 1];
          }
      } else {
          throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than 1");
      }
  }

3、核心原理

1）基于开放寻址

与 Java 标准库中的 HashMap（使用链地址法 + 红黑树）不同，Int2ObjectOpenHashMap 使用 开放寻址（open addressing） 解决哈希冲突：

• 所有键值对存储在一个连续的数组中。
• 当发生冲突时，通过探测（如线性探测或二次探测）寻找下一个空槽。
• FastUtil 默认使用 线性探测（linear probing）。

a、开放寻址 核心思想

开放寻址 是一种解决哈希冲突的策略。它的核心思想是：

所有键值对都存储在哈希表本身的底层数组中（而不是像链地址法那样使用链表或树等额外结构）。当发生哈希冲突（即多个键映射到同一个索引）时，算法会在数组中“探测”（probe）其他位置，直到找到一个空槽来存放新元素。

b、插入（put）

• 哈希函数：对于键 k，先计算其哈希值 h(k)，然后通过取模得到初始索引：

  index = h(k) % table.length
  

• 线性探测公式：探测序列：(h(k) + i) % table.length，其中 i = 0, 1, 2, ...

• 如果 table[index] 为空 → 直接插入。
• 如果已被占用（冲突）→ 线性探测：依次检查 index+1, index+2, …, 直到找到空槽。
• 若整个表快满（负载因子过高），则触发扩容（rehash）。

c、查找（get）

• 从 h(k) % len 开始，按相同探测顺序查找。
• 遇到空槽 → 键不存在（因为插入时会填满所有可能位置）。
• 遇到匹配键 → 返回值。

d、删除（remove）：这是开放寻址的难点！

• FastUtil 中通过特殊键值（如 0 对于 int 键，或 null 对于对象）结合状态位数组或哨兵值来高效处理删除。

• 不能简单置 null，否则会打断后续元素的查找路径。
• 解决方案：使用特殊标记（如 TOMBSTONE / “墓碑”）表示“此处曾有数据但已被删除”。
• 查找时跳过墓碑，插入时可复用墓碑位置。

2）原始类型优化

• 键是 int（不是 Integer），避免了自动装箱/拆箱（autoboxing/unboxing）。
• 内部数组直接使用 int[] 存储键，Object[] 存储值。
• 减少了对象创建和 GC 压力，提升缓存局部性。

3）高效哈希与内存布局

a、高效哈希

• 对 int 键使用高效的混合哈希（如 MurmurHash 变种），减少聚集。
• 支持自定义初始容量和负载因子。

b、内存布局紧凑

• 没有 Entry 对象（不像 HashMap 中每个键值对是一个 Node 对象）。
• 底层由两个平行数组组成：
  • 一个 int[] key 数组（存储键）
  • 一个 Object[] value 数组（存储值）
• 内存占用远小于 HashMap<Integer, V>，尤其在大数据量下优势明显。

4、对比 HashMap<Integer, V>

结论：只要无 null key 需求，一律用 Int2ObjectOpenHashMap

1）对比性能（速度）

1）Int2ObjectOpenHashMap：

• 避免 Integer 装箱/拆箱（zero boxing）
• 使用开放寻址（open addressing）而非链表/红黑树
• 实测比 HashMap<Integer, V> 快 2~4 倍（尤其在 get/put 高频操作时）

2）HashMap<Integer, V>：

• 每次 put(123, obj) 都会 Integer.valueOf(123)（装箱）
• 每次 get(123) 也会装箱 → 额外对象创建 + GC 压力

3）示例（300 万条数据，1000 万次查询）：

• HashMap: ~1765 ms

• Int2ObjectOpenHashMap: ~602 ms

• Int2IntOpenHashMap（value 也是 int）: ~552 ms

2）对比内存占用

1）Int2ObjectOpenHashMap：

• Key 直接存 int（4 字节），无 Integer 对象头（每个对象约 16~24 字节）
• 内存节省 40%~70%

2）HashMap<Integer, V>：

• 每个 key 都是一个 Integer 对象 → 大量小对象 → 堆膨胀 + GC 频繁

3）举例：存 1000 万个 <Integer, Object>：

• HashMap：约 1.1 GB
• Int2ObjectOpenHashMap：约 320 MB

3）场景推荐

只要 key 是原始 int，且无 null key 需求，默认就用 Int2ObjectOpenHashMap —— 它是“免费的性能提升”。

五、Object2ObjectOpenHashMap

1、FastUtil、EC、JDK

                          ┌───────────────────────┐
                          │      JDK HashMap      │
                          │  - 指针跳转           │
                          │  - Entry 对象开销大   │
                          │  - 红黑树兜底         │
                          └──────────┬────────────┘
                                     │ 安全、通用、支持 null
                                     ▼
┌───────────────────────┐  ┌───────────────────────┐
│  EC UnifiedMap        │  │ FastUtil O2O          │
│  - 三数组             │  │  - 双数组             │
│  - states[] 精确管理  │  │  - tombstone 陷阱     │
│  - 支持 null          │  │  - 不支持 null key    │
└──────────┬────────────┘  └──────────┬────────────┘
           │ 平衡之选                  │ 高风险高回报（但回报有限）
           ▼                           ▼
   [推荐用于大多数对象场景]    [仅限受控高性能场景]

2、性能对比

1）场景 1：小数据（< 1,000 条）

• JDK 最快：JIT 对 HashMap 高度优化，内联率高
• EC / FastUtil 略慢：方法调用链更长，边界检查多

2）场景 2：大数据插入/查询（100k+，哈希分布均匀）

• FastUtil ≈ EC > JDK
  • FastUtil 缓存局部性最好（仅两数组）
  • EC 因三数组，跨缓存行访问略慢
  • JDK 因指针跳转和对象分配，最慢

3）场景 3：哈希冲突严重（如所有 key 的 hashCode() 相同）

• JDK 最稳：自动转红黑树，O(log n)
• EC / FastUtil 崩溃：探测链极长，O(n) 性能雪崩

4）场景 4：频繁删除 + 插入

• EC 最佳：states[] 精确标记，可复用 removed 槽
• FastUtil 最差：tombstone 累积，负载因子虚高，触发不必要扩容
• JDK 中等：链表删除 O(1)，但对象仍需 GC

六、ObjectArrayList

1、基本定位

1）ObjectArrayList<E> 基础

• 全限定类名：it.unimi.dsi.fastutil.objects.ObjectArrayList<E>

• 继承关系：

  public class ObjectArrayList<E> extends AbstractList<E>
      implements RandomAccess, Cloneable, java.io.Serializable
  

• 作用：FastUtil 对 java.util.ArrayList<E> 的高性能替代实现，专用于存储对象引用（非原始类型）。

2）内部结构

• 懒初始化：默认构造函数设置 a = ObjectArrays.DEFAULT_EMPTY_ARRAY（共享空数组）
• 非线程安全：所有操作无同步
• 序列化支持：通过 writeObject/readObject 自定义序列化

public class ObjectArrayList<E> extends AbstractList<E> {
    protected transient E[] a;   // 底层数组（注意：不是 Object[]，而是 E[]）
    protected int size;          // 当前元素数量
}

3）为什么需要 ObjectArrayList？

说明：虽然不节省内存（仍存对象引用），但相比 JDK ArrayList，它在以下方面更优：

注意：这些优势主要体现在高频操作、算法场景或已引入 FastUtil 的项目中。

2、核心操作

1）添加元素（add(T element)）

• 直接写入 items[size++]
• 若容量不足，触发扩容 → 复制数组
• 无同步，非线程安全

2）随机访问（get(int index)）

• 直接返回 items[index]
• 有边界检查（if (index < 0 || index >= size) throw ...）
• 时间复杂度：O(1)

3）删除元素（remove(int index)）

• 将 index 后所有元素前移一位（System.arraycopy）
• 时间复杂度：O(n)

4）函数式操作（如 select, collect）

• 内部使用快速循环（fast enumeration），避免创建中间迭代器或 Stream 对象

• 示例：

  list.select(x -> x > 10); // 返回新的 ObjectArrayList，过滤高效
  

• 比 JDK 的 Stream.filter().collect() 更少 GC 压力，尤其在小数据集上更快

3、对比 ArrayList

1）使用建议

1）推荐使用 ObjectArrayList 的场景

• 已引入 FastUtil，希望统一体验（如同时用 IntArrayList）
• 需要频繁调用 removeElements(from, to) 等批量操作
• 在性能敏感循环中使用 forEach 避免 GC
• 对小容量扩容行为有确定性要求（如算法竞赛）

2）不推荐场景

• 简单 CRUD 业务，无性能瓶颈
• 无法引入第三方依赖
• 强依赖 JDK 原生行为（如某些反射框架）

2）杀手锏：原始类型特化

虽然 ObjectArrayList 用于对象，但 FastUtil 的最大优势在于对基本类型的直接支持。

• 零装箱/拆箱：直接操作基本类型，不创建 Integer 等包装对象
• 内存节省：int 占 4 字节，Integer 对象至少 16 字节（含对象头）

• GC 友好：减少堆对象数量，降低 GC 频率和停顿时间

• 实测：存储 1000 万个整数
  • ArrayList<Integer>：约占用 160 MB + 高频 GC
  • IntArrayList：仅占用 40 MB + 几乎无 GC

3）IntArrayList

存储大量基本类型数据时，IntArrayList 的内存占用仅为 ArrayList<Integer> 的约 20%，节省高达 80% 的堆内存，并极大降低 GC 压力。

5、FQA

1）空间效率：trim 的核心价值

• 行为与 JDK 几乎相同：a = Arrays.copyOf(a, size)
• 价值：在 size << capacity 时释放内存
• 典型场景：从大文件读取后过滤，保留少量结果 → 调用 trimToSize() 可节省 90%+ 内存

a、显著收益：

一个长期驻留的缓存列表（capacity=100万, size=1万）

• 不 trim：持续占用 4MB
• trim 后：仅占 40KB → 节省 99% 内存，集合的内部存储空间通常会缩小，GC 压力大幅下降

b、什么时候 trim

trim 牺牲一点时间，换大量空间 → 在内存受限或长期持有场景下，整体效率更高。

c、什么时候不 trimToSize()

2）扩容策略

• 为什么要 +1？考虑 oldCapacity = 1：

• ArrayList：1 + (1>>1) = 1 + 0 = 1 → 容量没变！不够用 → 实际会强制扩到 minCapacity（如 2）

• ObjectArrayList：1 + 0 + 1 = 2 → 直接满足需求