How do I access the nth item in a dictionary or hash?

Question

I have a dictionary of keys and values, for example:

{
    fred: 1,
    dave: 2,
    lily: 3
}

How do I get the 2nd element in the dictionary - {dave:2} in this case?

---

Background: I've seen this question asked so many times on SO in one form or another, so I thought I'd write a Q&A page as a community wiki that folks can be referred to and which might hopefully become the canonical answer for this question.

This Q&A applies to dictionaries as they are implemented in many different languages. Different languages use different names to refer to what is essentially the same data structure - for example they're called hashes in Perl, dictionaries in Python. In Objective-C they're instances of the NSDictionary or NSMutableDictionary classes.

Answer 1

In a nutshell, you can't - because dictionaries are unordered collections of key/value pairs. The order in which you populate a dictionary is not retained in memory. Here's a simple example in Python:

>>> dict = { 'a': 1, 'b': 2, 'c': 3 }
>>> dict # show the value of dict in memory
{'a': 1, 'c': 3, 'b': 2}

As you can see, although the dictionary is initialised with keys in the order a, b, c, printing the value of the dictionary shows them ordered a, c, b. Even that ordering is not retained in memory; as you add more key/value pairs to a dictionary the ordering in the above expression will continue to change.

Why is this?

Dictionaries are optimised for fast storage and retrieval of a value based on a unique key. The implementation varies from one language to the next but typically it works something like this:

• the dictionary is backed by a standard array of N elements
• on storing a key/value pair, the key is put through a function that transforms it into an integer (a "hashing function" - hence the name "hash" for this data structure in Perl). A simple hashing function for ASCII string keys might be to add up the ASCII values of each character. (Note: that's not a good hashing algorithm - just an example of a simple one!)
• the integer is then divided by the size of the array, and the remainder of that division is used as an index into the array
• if the array element at that index is already populated then one of a variety of techniques is used to resolve the clash (e.g. the contents of the array element are themselves an array to which the new value along with its unhashed key are appended)
• retrieval works in the same way as storage: take the key, use it to derive an array index, then retrieve the value associated with that key
• the backing array can be resized as the dictionary grows: on resizing the array, each element in the dictionary has its hash value divided by the new array size, resulting in a new remainder, i.e. a new location in the backing array.

Answer 2

I am newbie here, so can not add a comment yet.....But this is actually a comment to the above answer by Simon.

Useful Question & Nice Answer, Simon. You could have added another section to the answer, saying, Hence, the only way this question makes sense is, if we take an approach like the following examples

• sort(dict) and then obtain the n-th item of this new sorted dictionary. This will produce the exact same dictionary n-th item every time, even if the underlying array grows.
• enumerate( dict ) and obtain the n-th key in the dictionary