SparseSet

稀疏集

SparseSet（稀疏集） 是一种专为有界整数 ID设计的高性能集合数据结构，核心优势是插入、删除、查询、清空均为 O (1) 时间复杂度，且遍历高效、缓存友好。它通过稀疏数组（sparse）+ 密集数组（dense）+ 元素计数（n） 实现，广泛用于游戏引擎（如 ECS）、编译器、图算法等场景。

核心结构

SparseSet 由三部分组成：

• dense[]（密集数组）：按插入顺序存储集合中的实际元素值，仅包含存在的元素，内存紧凑、遍历高效。
• sparse[]（稀疏数组）：以元素值为索引，存储该元素在 dense 数组中的下标位置；未存在的元素对应位置值无意义。
• count（元素计数）：记录当前集合中元素的总数，dense[0..count-1] 为有效元素。

// 双向映射
sparse[key] = index;
dense[index] = key;

关键前提：元素必须是0 到 maxVal 之间的整数（有界全集），sparse 数组大小为 maxVal + 1。

实现

private int[] _sparse;
private int[] _dense;

private int _count;

public bool Contains(int key)
{
    return key < _sparse.Length && _sparse[key] < _count &&  _dense[_sparse[key]] == key;
}

public bool Add(int key)
{
    if (Contains(key)) return false;
    EnsureCapacity(key);
    var index = _count++;
    _sparse[key] = index;
    _dense[index] = key;
    return true;
}

// swap + pop
public bool Remove(int key)
{
    if (!Contains(key)) return false;
    var index = _sparse[key];
    var lastKey = _dense[--_count];
    _sparse[lastKey] = index;
    _dense[index] = lastKey;
    return true;
}

public void Clear() => _count = 0;

总结

除了前文所述的稀疏集的所有操作皆是O(1)，稀疏集主要优势还在于高效遍历，如果只是判断是否存在，其实一个稀疏数组甚至bool[]就行了，但是由于稠密数组的存在，我们在遍历有效数据的时候，就可以直接遍历稠密数组的前count个元素，这是cache-friendly的！此外稀疏集还有几点需要注意：

• 稀疏集需要元素是有界整数，并且要尽可能小，可以采取将 递增Id + 池化 的方式。
• 不可以仅仅通过稀疏数组判断是否存在，它的作用只是映射，实际容器大小在count里，数据在dense里，需要进行比对
• 稀疏数组和稠密数组的数组大小不一样，稀疏数组一般要大得多，两者分别独立扩容是个好主意

稀疏字典

dense里之前存的是key也就是那个有界整数，实际上它可以存任何类型，特别是对ECS游戏来说，它可以用来存组件结构体，这样可以充分利用其缓存友好的特点。但是这就会产生一个问题，sparse存index映射到dense；dense存key映射回sparse，这可以帮助我们在删除元素的时候压缩dense，不会让dense出现“空洞”，但是如果存的是任意类型的值，就无法找到dense映射回sparse的信息了，为此需要引入一个新的数组（或者在dense里存pair）。

// 双向映射 + 稠密数据
sparse[key] = index;
denseKey[index] = key;
denseValue[index] = value

实现

dense引入两个数组，_denseKeys存反向映射的key，_denseValues存真实数据。

private int[] _sparse;
private int[] _denseKeys;
private T[] _denseValues;

private int _count;

public bool Contains(int key)
{
    if (key < 0 || key >= _sparse.Length) return false;
    var index = _sparse[key];
    return index >= 0 && index < _count && _denseKeys[index] == key;
}

public bool Add(int key, T value)
{
    if (Contains(key)) return false;
    EnsureCapacity(key);
    _sparse[key] = _count;
    _denseKeys[_count] = key;
    _denseValues[_count] = value;
    ++_count;
    return true;
}

public bool Remove(int key)
{
    if (!Contains(key)) return false;

    var index = _sparse[key];
    var lastIndex = _count - 1;
    var lastKey = _denseKeys[lastIndex];

    if (index != lastIndex)
    {
        // swap + 覆盖
        _denseValues[index] = _denseValues[lastIndex];
        _denseKeys[index] = lastKey;
        _sparse[lastKey] = index;
    }
    
    // 清理
    _sparse[key] = None; // reset
    _denseValues[lastIndex] = default!;
    
    --_count;
    return true;
}

// 两组数组有不同的扩容机制
private void EnsureCapacity(int key)
{
    if (_sparse.Length <= key)
    {
        var oldSparseCap = _sparse.Length;
        var newSparseCap = oldSparseCap;
        while (newSparseCap <= key)
            newSparseCap <<= 1;
        Array.Resize(ref _sparse, newSparseCap);
        Array.Fill(_sparse, None, oldSparseCap, newSparseCap - oldSparseCap);
    }
    if (_denseKeys.Length <= _count)
    {
        var newDenseCap = Math.Max(_denseKeys.Length + MinimumIncrement, _denseKeys.Length << 1);
        Array.Resize(ref _denseKeys, newDenseCap);
        Array.Resize(ref _denseValues, newDenseCap);
    }
}

总结

连续内存、cache命中高，增删改查O(1)，遍历方便。这个结构对于特定问题例如处理ECS组件的存储非常适配。本文涉及的完整代码都在Github上

稀疏字典变体（寄存柜）

稀疏数据需要有界整数key，如果我们懒得去外部维护key generator，又想让我们的数据连续存储，随要随取，并且不介意由内部生成key借由外部保存，那就可以针对稀疏字典进行一些变化：请求存储数据时会在内部生成key并返回给你，作为外部句柄，存储方需要记住自己的句柄，在释放的时候传递进去。

就像去超市买东西，我们会将手头的东西value存到外面的柜子里，机器会给我们凭据key，走的时候将凭据key还回去就能拿回东西value。

实现

private int[] _sparse;		// key -> denseIndex
private int[] _free;		// 收集回收key（new）
private int[] _denseKeys;	// denseIndex -> key
private T[] _denseValues;	// denseIndex -> value

private int _count;				// 当前实际存储的个数
private int _allocatedCount;	// 已经提供过的key（只增不减）（new）
private int _freeCount;			// 当前复用池的元素个数（new）

public int Add(T value)
{
    var key = _freeCount > 0 ? _free[--_freeCount] : _allocatedCount++;
    EnsureCapacity(key);
    var index = _count++;
    _sparse[key] = index;
    _denseKeys[index] = key;
    _denseValues[index] = value;
    return key;
}

public bool Remove(int key)
{
    var index = _sparse[key];
    if (index < 0) return false;

    var lastIndex = _count - 1;
    if (index != lastIndex)
    {
        var swappedKey = _denseKeys[lastIndex];
        _denseKeys[index] = swappedKey;
        _denseValues[index] = _denseValues[lastIndex];
        _sparse[swappedKey] = index;
    }

    --_count;
    _sparse[key] = None;
    _free[_freeCount++] = key;
    // 其实可以不重置
    _denseKeys[lastIndex] = None;
    _denseValues[lastIndex] = default!;
    return true;
}

总结

这里free的思想让我想起C# Dictionary，不同的是Dictionary是用_freeList和_freeCount两个int来维护空闲位置，因为它的_entries本身是struct Entry类型，是一个链表结构；而在这里是没有链表的，所以用额外的一个free[]数组来存储空闲位置。此外Dictionary的_freeList维护的是包含value的Entry数组；而这里的_free维护的是sparse槽位。