并发SortedList或O(log n)并发集合

Question

我需要从ASP.NET MVC应用程序中缓存数据库中的大量数据,并希望使用SortedList.我知道.NET 4.0添加了并发集合,但没有排序集合.我当时正在考虑使用SynchronizedCollection,但是即使是读取它也是密集使用锁(如果我没有记错的话),所以我正在寻找其他选项.基本上我需要一个具有O(log n)访问复杂性的并发集合.

编辑 - 基于Greg答案的代码

void WrappedAdd(TKey k, TValue v)
{
  var copy = new SortedList<TKey, TValue>(_sortedList);
  copy.Add(k, v);
  _sortedList = copy;
}

Answer 1

你的要求很模糊，所以我不太清楚你想要什么。该集合应该有索引吗？键值语义？

我不确定这是否符合您的需求，但您可以使用新的 Microsoft不可变集合库。目前，它可以在 NuGet 上作为预览版使用。它包含排序集合（排序集和字典）等。

这些集合本身并不是并发的（事实上，并发不是问题；它们不能被修改）。但是，您可以通过包装它们并在写入期间使用锁来在并发设置中使用它们。读取是线程安全的，因为唯一的变化是分配引用，这是一个原子操作，因此保证您获得尽可能最新的结果。

它们是基于树的，因此大多数操作都是log n.

public class ConcurrentWrapper<TKey, T> {
    ImmutableSortedDictionary<TKey, T> _inner;

    public void Add(TKey key, T item) {
        lock (_inner) {
            _inner = _inner.Add(key, item);
        }
    }

    public T Get(TKey key) {
        return _inner[key];
    }
}