Hello.
In this video, we will discuss the last interview question about connections.
What is a dictionary?
A dictionary is a data structure representing a collection of key value pairs.
Each key in the dictionary must be unique.
Let's declare a dictionary representing the mapping from the country name to its currency.
In this case, both key and the value are strings, but that's not a rule, let's declare a dictionary
with a mapping from the currency name to its value expressed in U.S. dollars.
We can use the collection equalizer instead of adding the developers to the dictionary one by one.
Remember, that kiss in the dictionary must be unique.
This means an attempt to add a new value under the same key will draw an exception.
When using the other method, which the duplicated key an exception is thrown, on the other hand,
if I used the index are the old value would simply be updated.
This time, no exception is thrown and the updated value is presented to the council.
The use cases for dictionaries are endless.
Whenever we need any kind of not being there, most likely the best choice.
Let me give you a very simple example.
Here we have a collection of employees.
Each employee has a department he or she works in and the salary property.
We want to create a method that calculates what is the average salary in each department.
The result of this method should be a mapping from department to the average salary mappings are best
represented.
We've dictionaries.
I will use the links grouped by method to group the employees by department and then calculate the average
salary for each group.
Then I will transform the result into a dictionary using the two dictionary method.
Let's make sure this works as expected.
It seems like the result is correct, and the dictionary is a perfect data structure to represent it.
Now let's take a look under the hood of dictionaries.
The underlying data structure of a dictionary is a hash table.
A hash table is basically an array of linked lists.
We can imagine it like this.
Each element in the least because a value.
And the key object for which the hash code is calculated.
The placing of the developer is not random in this array.
The index is calculated like this.
This naturally gives a number between zero and R0 size minus one, which is a valid index in.
When an item is inserted into the hash table, it's hash code is calculated.
We learned about hash codes in the previous lecture.
Then the index in the array is calculated using this formula.
Finally, the key value power is added to the list stored under the given index.
This means under a certain index, objects with different hash codes can be stored.
But what happens if we add a new key value power to the dictionary, and the key has the same hash code
as some other key that is already stored in it?
Well, the dictionary must ask this is this actually the same key, or is it a different key that accidently
has the same hash code?
There is one method that can answer this question that equals method.
If two keys have the same hash codes and the equals method returns true for them, it means it's actually
the same key.
Then one of the two things will happen if the key value pair was added with the other method, which
expects that the key is not yet present in the dictionary.
An exception will be thrown if the key value per se is set with the index, or it will simply update
the value under the key.
But if the new and the old key have the same hash codes, but the equals method returns false four,
then it means there are actually two different keys that had the same hash called by accident.
In this case, the dictionary stores the new key value pair under the same index.
Remember, under each index there is a link to East, and the dictionary will put a new developer at
its end.
When we try to retrieve the value under this key again, the dictionary will quickly calculate the hash
code and based on this hash, the index in the array of linked lists.
Then it will iterate the list looking for an object with the same key.
So the key for which the equals method returns true if compared with the key for which we try to retrieve
the value because the equals method is needed in case of hash code conflicts to properly identify the
key.
We should always override it when overriding the good hash code method so their implementations are
consistent.
For example, if good hash code method returns the Social Security number for a person object, it means
we consider this number the person's identifier.
The equals method should also only compare the Social Security numbers.
Calculating the hash code is, or at least should be very fast.
Accessing the right element at a given index is extremely fast.
This means as long as the list under each index is small.
Accessing the dictionary value under a given key should be super fast, and this is the main power of
dictionaries.
So how big are the lists stored under each index?
Well, it depends on two factors.
What is the size of the array that represents the hash table?
This is something we don't control.
The dictionary itself adjusts this size.
The other factor is how often the hash codes for different objects are the same.
If, for example, we implemented the hash code method for some type us simply returning one, it would
mean that all hash codes will be duplicated.
There will be only one element in the array representing the hash table, and this element will be a
very long list of developers.
In other words, in this particular case, the performance of the dictionary will be similar to the
performance of other used.
This is the reason for which the hash functions should be uniformly distributed.
The fewer hash code conflict, the better.
The dictionaries performance Let's summarize a dictionary is a data structure representing a collection
of key value pass.
Each key in the dictionary must be unique.
When a key is added to the dictionary.
The dictionary calculates its hash code using the get hash called method.
It uses these hash codes to properly replace the value for the given key in the hash table.
That is the underlying data structure of a dictionary.
Dictionaries are a very common topic during the interview, so you can be asked some related questions.
For example, what is a hash table?
A hash table is a data structure that stores values in an array of corrections.
The index in the area is calculated using the hash code.
It allows quick retrieval of objects with given hash code.
A hash table is the underlying data structure of the dictionary.
Will the dictionary work correctly if we have hash code conflicts for two of its keys?
Yes.
The dictionary still can tell which key is which using the equals method, so it will not mistake them
only because they have the same hash codes.
Why should we override the equals method when we override the good housecoat method?
Because the equals method is needed for the dictionary to distinguish two keys in case of the hash code
conflict?
And because of that, its implementation should be in line with the implementation of the hash code
method.
For example, if the hash code method returns the Social Security number for a person object, it means
we consider this number the person's identifier.
The equals method should also only compare the Social Security numbers.
All right, that's it in this lecture.
Thanks for watching and see you in the next one.