Of course I mean data structure. From what I know, dictionary works as an array that uses hash methods to convert keys into indexes (thus O(1) time complexity). But to achieve that, data must be stored in one long chunk of memory. Therefore, if I have dictionary with, let’s say, ten values, I need indexes from range 0-9. How can hash method achieve that?
In: 0
Lets say you start with an array with 1000 cells.
When you want to add an item, you calculate the hash value and get a certain number, say 487572671. The problem is that the number can be much larger than 1000. So what do you do? You divide the number by 1000 and take the remainder, which is between 0 and 999, e.g. 671. So you put the item in cell #671 in the array.
Now, this was an oversimplification, so a couple of extra things:
1. If it’s a dictionary then you put both the key and the value in the array. That way when you look for an item, you can check if the key matches the key you are looking for.
2. When the array becomes too populated you need to resize it. Basically you create a larger array and move all the items from the old one to the new one.
3. A collision (two keys that get put in the same place in the array) can be handled in one of two ways:
In *open hashing* you can store more then one item in each cell of the array, using a list. When you look for an item you just look at the list of items in the appropriate cell and check if the item matches one of them.
In *closed hashing* you “hop” between occupied cells until you find one that isn’t occupied. For example if 671 is occupied, you can try 672. If that one’s occupied you try 674, then 678, then 686 (in this example we double the hop size with each step).
A dictionary is an abstract concept, also called a map—a container that maps keys to values.
It *could* be (and often is) implemented as a hash table / hash map, in which case you could achieve amortized O(1) insertion / lookup times.
Latest Answers