Measuring lookup time in List and SortedDictionary?

Question

C++ / C#

Hello, please explain why there is such a difference in the search time in the list and in the dictionary. What have I done wrong? Data in the picture with 5000 elements in the collection

Answer 1

Ran the test through BenchmarkDotNet:

public class TestClass
    {
        public static List<int> list = new(Enumerable.Range(0, 1_000_000));
        public static Dictionary<int, int> dict = Enumerable.Range(0, 1_000_000).ToDictionary(x => x, x => x);
        public static SortedDictionary<int, int> sorted = new(Enumerable.Range(0, 1_000_000).ToDictionary(x => x, x => x));

        [Benchmark]
        public void List_First()
        {
            list.Contains(0);
        }

        [Benchmark]
        public void List_Middle()
        {
            list.Contains(500_000);
        }

        [Benchmark]
        public void List_Last()
        {
            list.Contains(1_000_000);
        }

        [Benchmark]
        public void List_NoMatch()
        {
            list.Contains(-1);
        }

        [Benchmark]
        public void Dictionary_First()
        {
            dict.ContainsKey(0);
        }

        [Benchmark]
        public void Dictionary_Middle()
        {
            dict.ContainsKey(500_000);
        }

        [Benchmark]
        public void Dictionary_Last()
        {
            dict.ContainsKey(1_000_000);
        }

        [Benchmark]
        public void Dictionary_NoMatch()
        {
            dict.ContainsKey(-1);
        }

        [Benchmark]
        public void Sorted_First()
        {
            sorted.ContainsKey(0);
        }

        [Benchmark]
        public void Sorted_Middle()
        {
            sorted.ContainsKey(500_000);
        }

        [Benchmark]
        public void Sorted_Last()
        {
            sorted.ContainsKey(1_000_000);
        }

        [Benchmark]
        public void Sorted_NoMatch()
        {
            sorted.ContainsKey(-1);
        }
    }

Results: Everything is clear

with List - linear search is used. The further the element is in the list, the longer it takes to search for it. The test results confirm this.
Dictionary Source Code .
If we look at the implementation of the ContainsKey method , we see that the key is searched for by HashCode. That is, the usual Dictionary uses the structure of the Hash table to store the keys, the search for which is very fast. In the test, we see that Dictionary is the undisputed leader.
SortedDictionary Sorce Code .
If we look at the implementation of the ContainsKey method , we see here that the SortedDictionary stores keys with the structureSortedSet .
SortedSet , in turn, is based on a binary tree, that is, to search for an element, the Binary Search algorithm is used, which is faster than Linear, but inferior to the Hash Table. Which is confirmed by the tests.
Conclusion:
If you need a quick search by key, it is most efficient to use the Dictionary collection .