How does Dictionary search a particular key value out of huge amount of data?

Question

I have a very specific question about C hsarp Dictionary. Suppose you have 100000 Data in a Dictionary

var dictionary = new Dictionary<string, int>();

And you have already filled up the dictionary using ...

 dictionary.Add("car", 1);
 dictionary.Add("apple", 2);
...
...

Now suppose you are searching a particular string in dictionary

if (dictionary.ContainsKey("apple"))
  {
     // then do this
  }

My question here is, How Dictionary search for this particualr value out of those many keys? Is it going through linear Search. But msdn claims that dictionary searching complexity is close to O(1) LinkMSDN

What I know about Dictionary is that it doesn't have any internal search / sort algorithm. link

Can anyone please explain how dictionary stored its values in memory and how does retrieving of the values happenned from system point of view. I know being a high level programmer we don't need to think about all these features of .Net but it is good to know. Actually I am curious to know. MSDN says it uses hashtable, but there is no explanation.

Answer 1

From the same link in your question you can see:

Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.

I believe you need to read about hash table.

Probably a good starting point would be: Hash Tables - Data Structures