适配下半区密集操作的优先队列数据结构选型咨询

算法伪代码 #

T<int, int[]> dataStructure = new T();

// 遍历无限递增的整数序列，这里用int类型，也可改用long或BigInt
for (int current = 11; true; current += 2) {
  if (current in dataStructure) {
    // 若当前整数是数据结构的键，删除该条目，将值列表中的每个整数移至current + value * 2对应的位置
    int[] values = dataStructure.delete(current);
    for (int value in values) {
      dataStructure[current + value * 2].add(value);
    }
  } else {
    // 若当前整数不是数据结构的键，将其添加至current * 3对应的列表，同时返回该整数作为质数结果
    dataStructure[current * 3].add(current);
    yield(current);
  }
}

特性观察 #

• 频繁访问T中的最小键值
• T近似优先队列，但入队后优先级固定，无需decreaseKey操作
• 实际场景中，每个键对应的最大值数量约为ceil(log10(key)) + 1
• T中的唯一键数量常超过100,000个
• 插入操作更集中于（但不限于）T的下半区
• 仅对T中的最小键执行删除操作

当前实现与思考 #

• 当前采用Java的TreeMap搭配ArrayList存储值
• 曾尝试PriorityQueue与FibonacciHeap，但性能远逊于TreeMap
• 考虑将T中较大键的条目转储至磁盘（如SQLite），因这类条目短期内访问概率低
• 担忧平衡树结构会产生大量不必要的节点旋转
• 担忧分配数百万个ArrayList会导致效率低下

推荐数据结构及优化方向 #

1. 优化现有TreeMap实现

   • 既然TreeMap是当前性能最优的选择，可针对性减少开销：
     • 替换ArrayList为轻量型整数集合，比如Apache Commons的IntArrayList（避免自动装箱），或预先分配小容量的原生int[]（因每个键对应的值数量极少），降低对象分配和扩容的开销。
     • 维护一个缓存变量记录当前最小键，避免每次调用firstKey()遍历树结构，仅在最小键被删除后重新获取新的最小键。

2. 分段式内存+磁盘存储

   • 结合“大键访问概率低”的特性，拆分存储层：
     • 内存层用TreeMap存储较小的键（比如小于当前遍历值的2倍），保证高频操作的性能。
     • 当键超过设定阈值时，将条目转储到SQLite或有序本地文件中，访问时按需加载回内存。转储时需保证键的有序性，方便快速定位。

3. 有序链表+哈希表混合结构

   • 针对“仅删除最小键”的核心特性，设计混合结构：
     • 用有序双向链表存储键，链表头即为最小键，删除操作仅需操作链表头，时间复杂度O(1)。
     • 搭配哈希表（HashMap）实现键到链表节点的O(1)映射，快速完成键存在性检查和节点查找。
     • 优化插入：因插入集中在下半区，可从链表头开始遍历定位插入位置，或维护分段链表减少遍历长度。

4. 值集合的内存优化

   • 由于每个键对应的值数量极少，可直接用固定大小的原生数组代替动态集合，或合并多个小集合的存储，减少内存碎片化和对象实例数量。

内容的提问来源于stack exchange，提问作者Felix ZY