Dictionaries
A dictionary (map or hashtable) is a data structure representing a collection of pairs of key/values. You can access all values by their key. All values can be of any type (Int, String, Objects, …). Still, the keys have to be hashable (all primitive types implement this protocol). Dictionaries don’t guarantee the ordering.
You must wonder why keys have to be hashable. Let’s say that hashable transform any object into an integer that will use to define where the value is stored. The better the hashing is better the int will be unique.
Each dictionary is composed of an array of buckets (each bucket will be a linked list, to learn more about it, please refer to its article). Let’s say we have only three buckets with our previous example; we will use the bucket at index 1. Because this is a limited number of arrays, we need to use a modulo of the key’s hash.
Because of the non-unicity of hashing and the modulo, that will lead us to index collisions. It means that two different keys will end up in the same bucket. Once we have identified the bucket, we need to check into that bucket linearly until finding the right key.
While a dictionary is one of the most used data structures, we should use it when we need key access to its value. For example, we want to count the number of occurrences of a character within a string. On the contrary, if you want only to check an element’s presence, please look at the Set data structure.
To set a new key/value pair.
You can easily iterate over a dictionary, but it does not guarantee the order.
You can get all keys, or all values, then sort them; you will be able to get always the same order but might not get the same as the elements adding order.
The number of buckets is called capacity; a well-sized dictionary leads to a very good average performance O(1), while a single bucket will lead to a simple list performance O(n).
Time complexity:
- key access: O(1),
- set: O(1),
- delete: O(1),
- contains: O(1),
- Iterate: O(n),
- isEmpty: O(1),
- count: O(1).