## CodingBison

Python dictionaries provide a mechanism to store (key, value) pairs. With dictionaries, we can retrieve a value using its key. This is in contrast to a list, where elements are retrieved based on indices. Like lists, the stored values do not need to be of the same type. The same applies to dictionary keys as well.

We can define a dictionary by enclosing key/value pairs within a pair of braces, where each key is separated from its value using a colon. Thus, 'varDict = {"zebra": "Equus quagga", "guanaco": "Lama guanicoe"}' defines a dictionary (varDic) that has two key/value pairs. Alternatively, we can also start with an empty dictionary (as in 'varDict = {}') and then add elements to it (as in 'varDict["zebra"] = "Equus quagga"').

The following figure shows a Python dictionary (varDict) with three key/value pairs.

Figure: A Python Dictionary

Like lists, dictionaries are also mutable. However, when it comes to dictionary keys, they must be immutable! Python immutable types are numbers, strings, and tuples. For simpler types of keys, we can use numbers and strings. For cases, where the key is a collection of values, we can use tuples. For example, if we want to store a certain property that varies with geometric coordinates like (x, y, z), then we can use a tuple to identify the input geometric coordinate and map it to a value in the dictionary.

Like lists, we can use the len() function to get a count of total elements present in a dictionary.

Let us begin with a simple example that uses a dictionary. It starts with an empty dictionary and then, assigns some key/value pairs to it.

``` [user@codingbison]\$ python3
Python 3.2.1 (default, Jul 11 2011, 18:55:33)
[GCC 4.6.1 20110627 (Red Hat 4.6.1-1)] on linux2
>>>
>>> varDict = {}
>>> print(type(varDict))
<class 'dict'>
>>>
>>> varDict["zebra"] =  "Equus quagga"
>>> varDict["guanaco"] = "Lama guanicoe"
>>> varDict["tiger"] = "Panthera Tigris"
>>>
>>> print(varDict)
{'tiger': 'Panthera Tigris', 'guanaco': 'Lama guanicoe', 'zebra': 'Equus quagga'}
>>> print(len(varDict))
3
>>> print(varDict["zebra"])
Equus quagga
>>>
```

Do not count on ordering of elements in the hashtable. The dictionary uses an internal order to store the same. That is why in the above example, when we print the varDict, order is not the same as in which the elements were added.

Deleting an element from a dictionary is simple. Like lists and tuples, we can use the del operator to remove a key/value pair from the dictionary.

``` >>> varDict = {}
>>> varDict["zebra"] =  "Equus quagga"
>>> varDict["guanaco"] = "Lama guanicoe"
>>> varDict["tiger"] = "Panthera Tigris"
>>>
>>> print(varDict)
{'tiger': 'Panthera Tigris', 'guanaco': 'Lama guanicoe', 'zebra': 'Equus quagga'}
>>> print(len(varDict))
3
>>> del varDict["zebra"]
>>> del varDict["tiger"]
>>>
>>> print(varDict)
{'guanaco': 'Lama guanicoe'}
>>> print(len(varDict))
1
>>>
```

We can use the "if/in" to verify if a key exists in the dictionary. In earlier versions of Python prior to Python 3, dictionaries had has_key() method to do the same. However, with Python 3, this method has been removed in favor of the "if/in" construct.

If we access a key that does not exist, then Python throws a KeyError. Therefore, it is a good idea to check whether a key exists before accessing it.

``` >>> varDict = {"zebra": "Equus quagga", "guanaco": "Lama guanicoe"}
>>>
>>> if "tiger" in varDict:
...     print(varDict["tiger"])
... else:
...     print('The key "tiger" does not exist')
...
The key "tiger" does not exist
>>>
>>> print(varDict["tiger"])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'tiger'
>>>
```

Lastly, Python dictionaries use hashtable to store a value based on the key and of O(1). For cases, where lookup is a bottleneck, dictionaries are better than using lists, since lists have a lookup time of the order of O(n). However, if the hashtable becomes dense, then this lookup time goes up and for worst case, it can become O(n). The good thing is that for small to medium number of entries in the hashtable, the lookup stays close to O(1), which is faster.