Search code examples
c#concurrencysortedlistconcurrentdictionary

Is ConcurrentDictionary, a "concurrent" version of SortedList?

I would like to understand the Computational Complexity of a ConcurrentDictionary vers SortedList (Which is O(logarithmic(n))), is a ConcurrentDictionary just a concurrent synchronized implementation of a SortedList? or do these data structures vary? among one another?

Solution

  • ConcurrentDictionary<T,U> is a concurrent version of a Dictionary<T,U>. It does not sort by keys like a SortedList<T,U>. The complexity is closely related to a Dictionary<T,U>'s complexity, so fetches approach O(1).

    SortedList<T,U> has O(log n) complexity for most fetch operations since it's walking the internal sorted structure.