浅谈——我在C#中发现并实现了高性能随机集合

数据结构选型的核心思路

双结构互补原则

• 采用Dictionary<T, HashSet<int>>和List<T>组合，前者存储元素与索引的映射关系，后者支持快速随机访问。

• 优先初始化容量减少扩容

• 值类型键值需考虑内存布局

• 使用TryGetValue避免二次查找

重复元素处理方案

• 每个值对应索引集合时

// 创建索引池
private readonly Dictionary<int, HashSet<int>> valIndices = new();
// 插入时记录
if (!valIndices.TryGetValue(val, out var set)) {
    set = new HashSet<int>();
    valIndices[val] = set;
}
set.Add(data.Count);

关键操作的实现细节

插入操作的性能陷阱

• 避免连续调用Add方法

• 预判扩容阈值

// 预分配容量示例
public void EnsureCapacity(int expected) {
    if (data.Capacity < expected) {
        int newCapacity = (int)(data.Capacity * 1.5);
        data.Capacity = Math.Max(newCapacity, expected);
    }
}

删除操作的索引同步

• 实现"交换-删除"模式时需注意

// 安全的元素交换
void SwapRemove(int index) {
    int lastIdx = data.Count - 1;
    if (index != lastIdx) {
        T last = data[lastIdx];
        data[index] = last;
        
        // 更新哈希表映射
        var lastSet = valIndices[last];
        lastSet.Remove(lastIdx);
        lastSet.Add(index);
    }
    data.RemoveAt(lastIdx);
}

C#特有的优化策略

内存访问模式优化

• 结构体封装降低GC压力

public struct ElementWrapper {
    public int Value;
    public int Generation;
}
// 使用值类型集合
private List<ElementWrapper> data;

随机数生成器选择

• System.Random：吞吐量高但线程不安全

• ThreadLocal：线程隔离方案

• RNGCryptoServiceProvider：高安全性但速度慢

private static readonly ThreadLocal<Random> threadRand = 
    new(() => new Random(Environment.TickCount * Thread.CurrentThread.ManagedThreadId));

public T GetRandom() {
    int index = threadRand.Value.Next(data.Count);
    return data[index];
}

并发场景下的处理

读写锁的应用模式

private readonly ReaderWriterLockSlim rwLock = new();

public void Add(T item) {
    rwLock.EnterWriteLock();
    try {
        // 插入操作
    }
    finally {
        rwLock.ExitWriteLock();
    }
}

public T GetRandom() {
    rwLock.EnterReadLock();
    try {
        // 随机访问
    }
    finally {
        rwLock.ExitReadLock();
    }
}

无锁编程尝试

• 利用Interlocked操作实现原子更新

// 计数器原子操作
private int version;

public void Remove(T item) {
    Interlocked.Increment(ref version);
    // ...其他操作
}

调试与测试

状态一致性验证

[Conditional("DEBUG")]
void ValidateState() {
    foreach (var kv in valIndices) {
        foreach (int idx in kv.Value) {
            Debug.Assert(data[idx].Equals(kv.Key));
        }
    }
}

性能压力测试

• 使用BenchmarkDotNet进行基准测试

[SimpleJob(RuntimeMoniker.Net60)]
public class CollectionBenchmarks {
    private RandomizedCollection<int> collection;

    [IterationSetup]
    public void Setup() {
        collection = new RandomizedCollection<int>();
        // 预填充测试数据
    }

    [Benchmark]
    public void InsertBenchmark() {
        collection.Insert(DateTime.Now.Millisecond);
    }
}

生产环境

内存碎片预防

• 定期调用List.TrimExcess()

• 监控Large Object Heap使用

• 采用对象池复用集合实例

异常处理规范

• 自定义集合异常类型

• 添加详细的错误上下文

public class CollectionConsistencyException : Exception {
    public CollectionConsistencyException(string message) 
        : base($"State invalid: {message}. Count={Count}, HashCount={indexMap.Count}") 
    {
    }
}