Dictionary element accessing

Question

Question

Must looping through all C# Dictionary elements be done only through foreach, and if so why?

Or, I could ask my question as: can Dictionary elements be accessed by position within the Dictionary object (i.e., first element, last element, 3rd from last element, etc)?

Background to this question

I'm trying to learn more about how Dictionary objects work, so I'd appreciate help wrapping my mind around this. I'm learning about this, so I have several thoughts that are all tied into this question. I'll try to present in a way that is appropriate for SO format.

Research

In a C# array, elements are referenced by position. In a Dictionary, values are referenced by keys.

Looking through the documentation on MSDN, there are the statements

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

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

"Retrieving a value by using 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 reference to using a foreach statement to loop through and return elements. But there is no reference to using a for statement, or for that matter while or any other looping statement.

Also, I've noticed Dictionary elements use the IEnumerable interface, which seems to use foreach as the only type of statement for looping functions.

Thoughts

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

If this is so, why is there a .Count property that returns the number of key/value pairs, yet nothing that lets me reference these by nearness to the total? For example, .Count is 5, why can't I request key/value pair .Count minus 1?

How is foreach able to loop over each element, yet I have no 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 utilizing foreach? Can I not tell, without mapping elements to a collection, if a key is the first key in a Dictionary, or the last key?

This SO question and the excellent answers touch on this, but I'm specifically looking to see if I must copy elements to an array or other enumerable type, to access specific elements by position.

Here's an example. Please note I'm not looking for a way to specifically solve this example - it's for illustration purposes of my questions only. Suppose I want to add all they 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 would I copy each key to outStr using the above method? It appears I would have to use foreach. But what Dictionary methods or properties exist that would let me identify where an element is located at, within a dictionary?

If you're still reading this, I also want to point out I'm not trying to say there's something wrong with Dictionary... I'm simply trying to understand how this tool in the .NET framework works, and how to best use it myself.

If order is important use some other collectiontype than a Dictionary like a List, Stack, Queue, Array or [whathaveyou](https://msdn.microsoft.com/en-us/library/System.Collections.Generic(v=vs.110).aspx). Use a dictionary when an O(1) lookup key=>value is required. I don't see why you'd be interested in the `"Count-1"`'th element for example; if you are a Dictionary is *not* the collectiontype you want to use. — RobIII, Apr 21 '15 at 16:10
The order is undefined, so which value is at a specific index is also undefined. The only reason I could see wanting to get a specific index is for random access of the elements, and there is probably a better way to do that. — clcto, Apr 21 '15 at 16:13
`With Dictionary, how would I copy each key to outStr using the above method?` Presonally I wouldn't use that method. `var list = dictionary.Select(k => k.Key).ToList();` is simpler. — Ulric, Apr 21 '15 at 16:18
If you have a collection of *`strings`* and want both indexed access and hashed lookup, you can use [`NameValueCollection`](https://msdn.microsoft.com/en-us/library/system.collections.specialized.namevaluecollection%28v=vs.110%29.aspx). But there's no generic version (I've always wondered why). — dbc, Apr 21 '15 at 16:18
@Ulric, there is already a `Keys` property; `dictionary.Keys.ToList()` is even simpler. — clcto, Apr 21 '15 at 16:19
You might look at [Generic NameValueCollection Implementation](http://www.codeproject.com/Articles/19823/Generic-NameValueCollection-Implementation). Note that this boxes value types. — dbc, Apr 21 '15 at 16:23
@cicto Doh! I'd forgotten about that. Thanks for the correction. :) — Ulric, Apr 21 '15 at 16:24
@Robill, et all: appreciate the comments, but let me clarify: the question isn't about how to use Dictionary for ordering - it's about the Dictionary object itself. It's more of a question about how the framework works, not about how to best approach a programming goal. — Aaron Thomas, Apr 21 '15 at 17:00
@dbc - you've asked what I'm trying to figure out, thank you! Can I repeat in my own words? How is Dictionary set up in the system, so it does not offer both indexed access and hashed lookup? — Aaron Thomas, Apr 21 '15 at 17:02
Why not look at the [code](http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs) and find out? And my close vote was because this question is too broad for [so]. Also, note that it's a .NET Dictionary, not a C# dictionary. — John Saunders, Apr 21 '15 at 17:09
Really count is of no value if you cannot access by position? — paparazzo, Apr 21 '15 at 17:19
@JohnSaunders link to the code was helpful, thank you. For future questions, how could I improve? All the SO requirements are met. — Aaron Thomas, Apr 21 '15 at 17:19
See [ask]. Your question is basically about "poking around" and not about a specific problem that you're having. Questions that are about "I'm curious about ..." don't fit well on [so], as any number of answers might satisfy your curiosity (or not). — John Saunders, Apr 21 '15 at 18:35

D Stanley · Answer 1 · 2015-04-21T16:27:16.703

Say you have four cars of different colors. And you want to be able to quickly find the key to a car by its color. So you make 4 envelopes labelled "red", "blue", "black", and "white" and place the key to each car in the right envelope. Which is the "first" car? Which is the "third"? You're not concerned about the order of the envelopes; you're concerned about being able to quickly get the key by the color.

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

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

If this is so, why is there a .Count property that returns the number of key/value pairs, yet nothing that lets me reference these by nearness to the total? For example, .Count is 5, why can't I request key/value pair .Count minus 1?

You can still measure the number of items even thought there's no order. In my example you know there are 4 envelopes, but there's no concept of the "third" envelope.

How is foreach able to loop over each element, yet I have no access to individual elements in the same way?

Because foreach use IEnumerable, which just asks for the "next" element each time - the underlying collection determines what order the elements are returned in. You can pick up the envelopes one by one, but the order is irrelevant.

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

You can infer it by using foreach and counting how many elements you have before reaching the one you want, but as soon as you add or remove an item, that position may change. If I buy a green car and add the envelope, where in the "order" would it go?

I'm specifically looking to see if I must copy elements to an array or other enumerable type, to access specific elements by position.

Well, no, you can use Skip and Take, but there's no way to predict what item is at that location. You can pick up two envelopes, ignore them, pick up another one and call it the "third" envelope, but so what?

score 3 · Accepted Answer · answered Apr 21 '15 at 16:58

Several correct answers here, but I thought you might like a short version :)

Under the hood, the Dictionary class has a private field called buckets. It's just an ordinary array which maps integer positions to the objects you've added to the Dictionary.

When you add a key/value pair to the Dictionary, it calculates a hash value for your key. The hash value gets used as the index into the buckets array. The Dictionary uses as many bits of the hash as it needs to ensure that the index into the buckets array doesn't collide with an existing entry. The buckets array will be expanded as needed due to collisions.

Yes, it's possible via reflection (which allows you to extract private data fields) to get the 3rd, or 4th, or Nth member of the buckets array. But the array could be resized at any time and you're not even guaranteed that the implementation details of Dictionary won't change.

Timothy Shields · Answer 3 · 2015-04-21T16:16:01.800

2

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

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

edited Apr 21 '15 at 16:16

answered Apr 21 '15 at 16:14

Timothy Shields

75,459
18
120
173

This should be a comment on D Stanley's answer; it doesn't answer the question. – Dan J Apr 21 '15 at 16:15

score 2 · Answer 4 · answered Apr 21 '15 at 19:39

Looping through a dictionary does not need to be done using foreach, but the terms 'first,' and 'last' are meaningless in terms of a dictionary, because order is not guaranteed and is in no way related to the order items are added to your dictionary.

Think of it this way. You have a bag that you are using to store blocks, and each block has a unique label on it. Throw in a block with the labels "Foo," "Bar," and "Baz." Now, if you ask me what the count of my bag is, I can say I have 3 blocks in it and if you ask me for the block labeled "Bar" I can get it for you. However, if you ask me for the first block, I don't know what you mean. The blocks are just a jumble inside my bag. If, instead you say 'foreach' block, I'd like to take a photo of it, I'll hand you each block, 1 by 1. Again, the order isn't guaranteed. I'm just reaching into my bag and pulling out each block until I've gotten each one.

You can also ask for a collection of all the keys in a dictionary, then use each key to access the items in a dictionary. However, once again, the order of the keys is not guaranteed and, in theory, could change every time you access it (in practice, the .NET key order is normally pretty stable).

There's a lot of reasons why a dictionary is stored like this, but the key thing is dictionaries have to have unspecified order in order to have both O(1) insertion and O(1) access. An array, which has a specified order has O(1) access (you can get the n'th item in one step), but insertions are O(n).

score 1 · Answer 5 · answered Apr 21 '15 at 16:13

There is a large number of collections available in the .Net framework. You have to analyse your requirements and decide which collection to use:

Do you need Key/Value pairs or just Items?
Is it important that items are sorted?
Do you need fast insertion or just add at start/end of collection?
Do you need fast retrieval: O(1) or O(log n)?
Do you need an index i.e. acces to items by an integer position?

For most combinations of these requirements there exists a specialized collection.

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

Dictionary element accessing

5 Answers5