Is ConcurrentDictionary, a “concurrent” version of

Question

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?

Answer 1

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.

Answer 2

I believe that ConcurrentDictionary<K,V> is a thread-safe analog of Dictionary<K,V> and both should have complexity O(1). They don't provide key sorting, order is not guaranteed.