Access to dictionary item

Question

Question

Do I need to scroll through all the elements of the C # Dictionary only through foreach , and if so, why?

Or, I could ask my question how: is it possible to get Dictionary elements by position inside the Dictionary object (i.e. the first element, the last element, the third from the last element, etc.)?

Background information on this subject.

I am trying to learn more about how Dictionary objects work, so I will be grateful for the help in this. I find out about this, so I have a few thoughts that are all related to this issue. I will try to present in a way that is suitable for the SO format.

Study

In a C # array, elements refer to a position. In Dictionary values ​​refer to keys.

Looking through the documentation on MSDN , there are instructions

"For enumeration purposes, each element in the dictionary is treated as a KeyValuePair structure representing the value and its key. The order in which the elements are returned is undefined."

So, it would seem that since order items are returned in undefined format, there is no way to access items by position. I also read:

"Getting the value with its key is very fast, close to O (1), because the Dictionary class is implemented as a hash table."

Looking at the documentation for the HashTable .NET 4.5 class , there is a link to using the foreach for looping and return elements. But there is no reference to using the for statement, or, for that matter, while or any other loop statement.

In addition, I noticed that Dictionary elements use the IEnumerable interface, which apparently uses foreach as the only type of statement for loop functions.

Thoughts

So, does this mean that Dictionary elements cannot be accessed by "position", as arrays or lists can?

If so, why is there a .Count property that returns the number of key / value pairs, but nothing that allows me to refer to their proximity to the total? For example .Count is 5, why can't I request a key / value .Count minus 1?

How foreach can iterate over each element, but I do not have access to individual elements in the same way?

Is there no way to determine the position of an element (key or value) in a Dictionary object without using foreach ? May I not say without binding the elements to the collection if the key is the first key in the Dictionary or the last key?

This SO question and excellent answers relate to this, but I specifically look to see if I need to copy elements to an array or other enumerated type to allow access to certain elements by position.

Here is an example. Please note that I am not looking for a way to specifically solve this example - this is only to illustrate my questions. Suppose I want to add all the keys in a Dictionary<string, string> object to a comma-separated list, with no comma at the end. With an array I could do:

 string[] arrayStr = new string[2] { "Test1", "Test2" }; string outStr = ""; for (int i = 0; i < arrayStr.Length; i++) { outStr += arrayStr[i]; if (i < arrayStr.Length - 1) { outStr += ", "; } } 

With Dictionary<string, string> , how can I copy each key to outStr using the above method? It looks like I would have to use foreach . But what are the methods or properties of the Dictionary that would allow me to determine where the element is located inside the dictionary?

If you are still reading this, I also want to indicate that I am not trying to say that something is wrong with the Dictionary ... I am just trying to understand how this tool works in the .NET platform, and how best to use it myself .

Answer 1

Some correct answers here, but I thought you might like the short version :)

Under the hood, the Dictionary class has a private field called buckets . This is just a regular array that matches integer positions with objects added to the Dictionary .

When you add a key / value pair to the Dictionary , it calculates the hash value for your key. The hash value is used as an index in the buckets array. Dictionary uses as many hash bits as necessary so that the index in the buckets array buckets not collide with an existing entry. An array of buckets will expand as needed due to collisions.

Yes, this is possible thanks to reflection (which allows you to retrieve private data fields) to get the 3rd, 4th or Nth member of the buckets array. But the array can be changed at any time, and you do not even guarantee that the details of the Dictionary implementation will not change.

Answer 2

Say you have four cars of different colors. And you want to quickly find the car key by its color. Thus, you make 4 envelopes with the words "red", "blue", "black" and "white" and put the key in each car in the right envelope. What is a "first" car? What is the "third"? You are not worried about the order of the envelopes; You are worried that you can quickly get the key by color.

So, does this mean that dictionary elements cannot be accessed by "position", since arrays or lists can?

Not directly, no. You can use Skip and Take , but all they will do is iterate over until you get to the nth element.

If so, why is there a .Count property that returns the number of key / value pairs, but nothing that allows me to refer to them in proximity to the total? For example .Count is 5, why can't I request a key / value pair .Count minus 1?

You can still measure the number of elements, even assuming that there is no order. In my example, you know that there are 4 envelopes, but there is no concept of a “third” envelope.

How is foreach able to iterate over each element, but I don't have access to individual elements in the same way?

Because foreach uses an IEnumerable that simply asks for the “next” item each time, the base collection determines in what order the items are returned. You can pick up envelopes one at a time, but the order does not matter.

Is there no way to determine the position of an element (key or value) in a Dictionary object without using foreach?

You can infer using foreach and counting how many elements you have before you reach the one you want, but as soon as you add or remove an element, this position can change. If I buy a green car and add an envelope, where will it go in “order”?

I specifically look to see if I need to copy elements to an array or another enumerated type in order to access certain elements by position.

Well, no, you can use Skip and Take , but there is no way to predict which element is in this place. You can take two envelopes, ignore them, pick up another one and call it the “third” envelope, but what?

Answer 3

In addition to D Stanley's answer, I would like to add that you should check out SortedDictionary<TKey, TValue> . It stores key / value pairs in a data structure that stores ordered keys.

 var d = new SortedDictionary<int, string>(); d.Add(4, "banana"); d.Add(2, "apple"); d.Add(7, "pineapple"); Console.WriteLine(d.ElementAt(1).Value); // banana 

Answer 4

Looping through a dictionary does not have to be done using foreach, but the terms “first” and “last” do not make sense in terms of the dictionary, because the order is not guaranteed and is in no way associated with order items added to your dictionary.

Think of it this way. You have a bag that you use to store the blocks, and each block has a unique label on it. Throw the block with the words "Foo", "Bar" and "Baz". Now, if you ask me what the account of my bag is, I can say that I have 3 blocks, and if you ask me about the block with the inscription “Bar”, I can get it for you. However, if you ask me about the first block, I do not know what you mean. Blocks are just a mess inside my bag. If instead you say “foreach” block, I would like to take a picture, I will give you each block, 1 to 1. Again, the order is not guaranteed. I just sit in my bag and take out each block until I get each.

You can also request a collection of all the keys in the dictionary, and then use each key to access items in the dictionary. However, again, the order of the keys is not guaranteed and can theoretically change each time you access it (in practice, the order of the .NET keys is usually pretty stable).

There are many reasons why a dictionary is stored in this way, but the key thing is that dictionaries must have an unspecified order in order to have both O (1) and O (1) access. An array having the indicated order has O (1) access (you can get the nth element in one step), but the inserts are O (n).

Answer 5

The .Net structure has a large number of collections. You should analyze your requirements and decide which collection to use:

• Do you need Key / Value pairs or just elements?
• Is it important to sort items?
• Do you need a quick insert or just add to the beginning / end of the collection?
• Do you need a quick search: O (1) or O (log n)?
• Do you need an index, i.e. access to elements by integer position?

For most combinations of these requirements, there is a specialized collection.

In your case: Key / Value and acces pairs via index: SortedList