How dictionary do operation like array with O(1) complexity
To reduce the time complexity of your program, you might use a dictionary rather than an array. Because accessing, adding, or removing any elements from a simple list required O(n) or greater than time. But the same operation can be performed by the dictionary in python with O(1) time.
When I came to know about this concept, first the question ‘Why’ came to my mind. Why dictionary is exceptional than a list data structure? If you have the same sorts of questions in your mind, you can go through this article. Otherwise, leave it.
In short, to reduce the time complexity, we can use hashmap which is implemented in the dictionary in python.
Dictionary in python is built with a hash table and uses SipHash open addressing collision resolution method, where sipHash is mainly used for hashing. It can store value in key-value pairs. When we try to access any value from a dictionary, it goes for a lookup for a specific address it stores on storage.
If you are new to the word Hashing, in short, I can tell you that Hashing is an encrypting process where any key is transforming into another specific fixed-size value. And they are stored separately. When more than one key is overlap with other encrypted keys, it’s called a collision. To eliminate the collision among the hashed value, python use sipHash as a hash function method and reduce the possibility to overlap any single value. After the update of Python 3.4, it changes its hashing method previous Fowler-Noll-Vo hash function to sipHash. They found some loopholes in security and performance in Fowler-Noll-Vo hash function, that’s why they changed it.
Maybe you are wondering to see hashmap or hashing.
Now, look at the main context of this article. How does Dictionary do any operation in O(1) complexity? By google definition “A HashMap is a data structure implementing a key-value pair and is used in certain languages, e.g. Java, whereas a dictionary is an equivalent data structure used in other languages such as Python, although Java also has a Dictionary type as well.”
That means, every key in the dictionary is generated by this hash function. When we try to access it, it directly goes to the specific address and processes the result. By default, the values are set as None. When any value does not exist in that dictionary, the value associated with any input key is None. That’s why it shows None message to the caller.
Here is a simple problem solution by Hashmap in python. If you look so closely, you can get the key concept of this article.
Now, why did the dictionary consider a hash function? Maybe this question came to your mind at the beginning of the article. The Dictionary data structure in python stores value in key-value pairs. The key is stored in the computer storage by encrypting it using sipHash algorithm that helps to track and find it so fast. In sort, Dictionary in python is processed through it.
Now, another question. How does the dictionary work on 0(1) order? The dictionary try to access a value by calling the key value of that data. When it tries to access the value, it already knows the encryption process and algorithm of Key encryption, and simply finds it with Bigo of O(1) time. That’s why it only takes O(1) time to access any element in the dictionary.
Reference:
https://docs.python.org/3/tutorial/datastructures.html#dictionaries
