fastutil1、概述2、命名规范与包结构3、高性能基本类型列表 (IntArrayList / LongArrayList)4、高性能基本类型集合 (IntOpenHashSet)5、键值对映射 (Int2ObjectOpenHashMap / Long2DoubleOpenHashMap)6、突破 2GB 限制的海量数据存储 (BigArrays IntBigArrayBigList)7、高性能优先队列与堆排序 (IntHeapPriorityQueue)8、基本类型极速排序工具 (IntArrays)9、内存开销对比与性能分析10、避坑指南与最佳实践1、概述fastutil 是由意大利米兰大学团队开发的 Java 高性能集合扩展库。它通过为所有 Java 基本数据类型primitive types 提供专门定制的 映射Map、集合Set、列表List、优先队列Priority Queue及大数组Big Array完美解决了 Java 原生集合框架JDK Collections Framework三大痛点装箱/拆箱开销Autoboxing/Unboxing不再需要将 int 自动装箱为 Integer极大降低了垃圾回收GC压力与 CPU 周期。内存极度浪费一个 JDK HashSet 在 64 位 JVM 上存储每个元素大约需要 32 字节以上的额外对象头和引用开销而 fastutil 的 IntOpenHashSet 使用扁平的紧凑基本类型数组存储每个元素仅占用 4 字节。海量数据支持突破 2GB 限制JDK 集合和数组的索引限制在 Integer.MAX_VALUE约 21 亿。fastutil 提供了基于二维交错数组实现的 BigArrays能够轻松支持超大规模数据的存储与索引。dependencygroupIdit.unimi.dsi/groupIdartifactIdfastutil/artifactIdversion8.5.13/version/dependency2、命名规范与包结构fastutil 的命名遵循极其严格的模式[Type1][Type2][Structure/Implementation]。数据类型前缀 (Type)Int、Long、Double、Float、Char、Byte、Short、Boolean、Object。数据结构接口 (Structure)List、Set、Map、BigList、Stack、PriorityQueue 等。底层实现方案 (Implementation)OpenHashSet / OpenHashMap开放寻址法哈希表线性探测/二次探测性能最高、内存占用最少是 fastutil 最推荐的默认实现。AVLTreeSet / AVLTreeMap基于平衡二叉树AVL 树实现的有序集合/映射。RBTreeSet / RBTreeMap基于红黑树实现的有序集合/映射。ArrayList / ArraySet基于动态数组的轻量级实现适用于小数据量或很少修改的场景。包路径规律it.unimi.dsi.fastutil.[type]s例如Int2ObjectOpenHashMap 位于 it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap而 Long2DoubleOpenHashMap 位于 it.unimi.dsi.fastutil.longs.Long2DoubleOpenHashMap。3、高性能基本类型列表 (IntArrayList / LongArrayList)IntArrayList 提供了对基本类型 int 数组的动态扩容封装避免了 java.util.ArrayListInteger 的装箱拆箱同时支持极其高效的无装箱遍历与数组提取。importit.unimi.dsi.fastutil.ints.IntArrayList;importit.unimi.dsi.fastutil.ints.IntList;importit.unimi.dsi.fastutil.ints.IntListIterator;publicclassFastutilListDemo{publicstaticvoidmain(String[]args){// 1. 初始化列表 (可以预分配初始容量避免频繁扩容)IntListlistnewIntArrayList(100);// 2. 添加基本类型元素 (无装箱)list.add(10);list.add(20);list.add(30);// 3. 批量添加list.addAll(IntArrayList.wrap(newint[]{40,50,60}));// 4. 零开销修改与按索引读取list.set(0,100);intfirstElementlist.getInt(0);// 注意使用 getInt(index) 避免装箱为 IntegerSystem.out.println(首元素: firstElement);// 5. 高性能遍历方式 1基于 Fastutil 特有的 Type-Specific 迭代器IntListIteratoriteratorlist.iterator();while(iterator.hasNext()){intvaliterator.nextInt();// 直接返回 int// System.out.println(val);}// 6. 高性能遍历方式 2无迭代器索引遍历 (最快)for(inti0;ilist.size();i){intvallist.getInt(i);}// 7. 直接导出为基本类型底层数组 (非常适合与 JNI 或低级 C/C 库交互)int[]rawArraylist.toIntArray();System.out.println(导出数组长度: rawArray.length);}}首元素:100导出数组长度:64、高性能基本类型集合 (IntOpenHashSet)IntOpenHashSet 采用开放寻址法Open Addressing解决哈希冲突比 JDK 基于拉链法链表/红黑树的 HashSetInteger 快 2~5 倍且内存开销降至 JDK 的 1/4。importit.unimi.dsi.fastutil.ints.IntOpenHashSet;importit.unimi.dsi.fastutil.ints.IntSet;publicclassFastutilSetDemo{publicstaticvoidmain(String[]args){// 创建开放寻址哈希集合IntSetsetnewIntOpenHashSet();// 1. 基础添加与查找set.add(100);set.add(200);set.add(300);System.out.println(是否包含 200: set.contains(200));// trueSystem.out.println(是否包含 500: set.contains(500));// false// 2. 集合运算 (并集、交集、差集)IntSetotherSetnewIntOpenHashSet(newint[]{200,300,400});// 保留交集 (Intersection)set.retainAll(otherSet);System.out.println(交集大小: set.size());// 2 (包含 200, 300)// 3. 极速过滤 / 函数式处理 (使用特化 Consumer)set.forEach((intval)-{// 无装箱函数式处理System.out.println(元素: val);});}}是否包含200:true是否包含500:false交集大小:2元素:200元素:3005、键值对映射 (Int2ObjectOpenHashMap / Long2DoubleOpenHashMap)fastutil 的 Map 类型细分非常极致Int2ObjectOpenHashMapVKey 为 intValue 为 Object 对象。Object2IntOpenHashMapKKey 为 Object 对象Value 为 int常用于词频统计/计数器。Int2IntOpenHashMapKey 和 Value 均为 int完全摒弃对象引用。示例 A高并发/高频计数字段 (Object2IntOpenHashMap)在词频统计Word Count场景下JDK 的 MapString, Integer 每次增加计数都需要创建新的 Integer 对象而 fastutil 提供了原生的 addTo 方法实现原地增量。importit.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;publicclassWordCountDemo{publicstaticvoidmain(String[]args){Object2IntOpenHashMapStringcounternewObject2IntOpenHashMap();// 设置默认返回值 (当 Key 不存在时get() 返回 0 而不是 null)counter.defaultReturnValue(0);String[]words{apple,banana,apple,cherry,apple,banana};// 1. 极速更新计数 (addTo 方法可以实现无对象创建的原地累加)for(Stringword:words){counter.addTo(word,1);// 如果不存在设为 1如果存在增加 1}System.out.println(apple 的数量: counter.getInt(apple));// 3System.out.println(banana 的数量: counter.getInt(banana));// 2System.out.println(orange 的数量: counter.getInt(orange));// 0 (触发 defaultReturnValue)}}apple 的数量:3banana 的数量:2orange 的数量:0示例 B原生键值映射 (Long2DoubleOpenHashMap)特别适合计算广告、推荐系统或高频交易中存储特征权重如 userId(long)→ \rightarrow→score(double)。importit.unimi.dsi.fastutil.longs.Long2DoubleOpenHashMap;publicclassKeyValueMapDemo{publicstaticvoidmain(String[]args){Long2DoubleOpenHashMapmapnewLong2DoubleOpenHashMap();map.defaultReturnValue(-1.0);// 找不到 Key 时返回 -1.0map.put(10001L,98.5);map.put(10002L,75.0);// 查找doublescoremap.get(10001L);System.out.println(得分: score);// 使用双游标FastEntryIterator进行无装箱高性能 Map 遍历map.long2DoubleEntrySet().fastIterator().forEachRemaining(entry-{longkeyentry.getLongKey();// 无装箱获取 Long Keydoublevalentry.getDoubleValue();// 无装箱获取 Double ValueSystem.out.println(key - val);});}}得分:98.510001-98.510002-75.06、突破 2GB 限制的海量数据存储 (BigArrays IntBigArrayBigList)Java 原生数组的最大长度是 Integer.MAX_VALUE2,147,483,647。当需要存储数十亿个元素时传统数组会直接抛出 OutOfMemoryError 或超出索引界限。fastutil 的 BigArrays 采用 Segmented Array分块段阵列 结构用 long 类型作为索引突破了 2GB/21亿 限制。importit.unimi.dsi.fastutil.ints.IntBigArrayBigList;importit.unimi.dsi.fastutil.ints.IntBigArrays;publicclassBigArrayDemo{publicstaticvoidmain(String[]args){// 1. 直接创建一个长度为 50 亿 (5,000,000,000) 的二维交错 int 大数组longhugeSize5_000_000_000L;int[][]bigArrayIntBigArrays.newBigArray(hugeSize);// 2. 通过 long 类型的索引进行元素设置与获取longtargetIndex4_000_000_000L;IntBigArrays.set(bigArray,targetIndex,99999);intvalueIntBigArrays.get(bigArray,targetIndex);System.out.println(长索引 40 亿处的元素值: value);// 3. 面向对象的 BigList 封装IntBigArrayBigListbigListnewIntBigArrayBigList();bigList.add(100);bigList.add(200);System.out.println(BigList 第 1 个元素: bigList.getInt(1L));// 参数传入 long 类型的索引}}7、高性能优先队列与堆排序 (IntHeapPriorityQueue)JDK 的 PriorityQueueInteger 会产生频繁的装箱与节点对象创建fastutil 提供了全原生的二进制最小堆/最大堆实现importit.unimi.dsi.fastutil.ints.IntHeapPriorityQueue;importit.unimi.dsi.fastutil.ints.IntComparators;publicclassPriorityQueueDemo{publicstaticvoidmain(String[]args){// 1. 默认构建最小堆 (Min-Heap)IntHeapPriorityQueueminHeapnewIntHeapPriorityQueue();minHeap.enqueue(50);minHeap.enqueue(10);minHeap.enqueue(30);System.out.println(堆顶最小值: minHeap.firstInt());// 10System.out.println(弹出堆顶: minHeap.dequeueInt());// 10System.out.println(新的堆顶: minHeap.firstInt());// 30// 2. 传入自定义比较器构建最大堆 (Max-Heap)IntHeapPriorityQueuemaxHeapnewIntHeapPriorityQueue(10,IntComparators.OPPOSITE_COMPARATOR);maxHeap.enqueue(50);maxHeap.enqueue(10);maxHeap.enqueue(30);System.out.println(堆顶最大值: maxHeap.firstInt());// 50}}堆顶最小值:10弹出堆顶:10新的堆顶:30堆顶最大值:508、基本类型极速排序工具 (IntArrays)fastutil 提供了比 java.util.Arrays.sort() 更高效的针对原生数组的排序工具如快速排序 QuickSort、归并排序 MergeSort、基数排序 RadixSort。基数排序RadixSort在海量数据下性能大幅超越双轴快排。importit.unimi.dsi.fastutil.ints.IntArrays;publicclassFastutilSortDemo{publicstaticvoidmain(String[]args){int[]data{9,3,1,5,13,2,7,8,4};// 1. 快速排序IntArrays.quickSort(data);// 2. 超高速并行基数排序 (Radix Sort) - 适合大数组int[]largeDatanewint[]{100,4,30,22,1,90,50};IntArrays.radixSort(largeData);System.out.println(基数排序结果: java.util.Arrays.toString(largeData));// 3. 间接排序 (Indirect Sort / Index Sort)// 不改变原数组返回排序后的索引数组 (非常适合多列数据按某一列排序)int[]score{88,99,60,75};int[]permIntArrays.getPermutation(score.length);IntArrays.quickSort(perm,(i1,i2)-Integer.compare(score[i1],score[i2]));System.out.println(按照分数升序排列的原始索引: java.util.Arrays.toString(perm));}}9、内存开销对比与性能分析以存储 1,000,000一百万个 64 位整数 (long) 为例方案 / 容器实现内存占用总量 (约)垃圾回收 (GC) 压力随机读取/查找性能JDK ArrayListLong~32 MB产生 100 万个 Long 对象GC 压力极高较慢 (指针追溯与缓存未命中)JDK HashSet~64 MB产生 100 万个 Node 100 万个 Long 对象较慢 (CPU L1/L2 缓存命中率低)fastutil LongArrayList~8 MB0 额外对象极快 (连续内存CPU 预取友好)fastutil LongOpenHashSet~16 MB0 额外对象极快 (开放寻址数组随机访问)10、避坑指南与最佳实践小心隐式装箱陷阱fastutil 容器为了兼容 JDK 接口同时实现了 JDK 的 ListInteger 或 MapInteger, String 接口。错误示范list.get(0)会调用 JDK 接口返回 Integer 对象导致装箱。正确示范list.getInt(0)调用 fastutil 特化方法返回 int。错误示范map.get(key)返回包装类型。正确示范map.getInt(key) 或 map.get(key) 的特化实现。合理使用 defaultReturnValue在 Map 中查找不存在的 Key 时JDK 的 map.get(key) 返回 null。但基本类型如 int无法为 nullfastutil 默认返回 0或 false/0.0。如果你的业务逻辑中 0 是合法值务必在初始化时使用 map.defaultReturnValue(-1) 显式修改默认返回值。开放寻址法Open Hash的扩容与 Load FactorOpenHashMap 和 OpenHashSet 默认的加载因子Load Factor为 0.75。如果已知数据规模务必在构造函数中指定容量如 new IntOpenHashSet(1_000_000)避免动态扩容带来的 Rehash 性能损耗。