Hello, the students in this lesson, we are going to learn how hash tables work and an example of hash
map will learn how to use maps.
This is important because a lot of the most popular map implementations are based on the hash tables
to understand how hash tables work and how to override equals and hash code methods.
In our times today, we'll have practice with hash map.
You're going to learn what the capacity of hash map is and what load factor is.
I'll share with you the best practices of selecting keys for map urines and lesson.
We are going to answer the question what immutable objects are.
Also, I will show you how you can search entries in your Mambi keys and by values.
Let's start.
Probably you already know from the previous lessons that it takes constant amount of time from hash
map to perform its major operations like get both remove and connotation for major operation of hash.
Map is all of one, but what implementation brings are such performance.
This is because Hashmat the same as Linc's hash map, concurrent hash map and hash table use hash tables
to store and retrieve data.
And for us it is important to understand how hash tables work so that we could use and tune our hash
map when needed for better performance.
Let's learn what hash table is and try to explain hash table in very simple words that are easy to understand.
I can explain it in the Wikipedia language, but I won't.
In simple words, hash table consists of buckets or also sometimes they called slots where you might
put any value.
I want you also to learn things on example.
So we would discuss also a few things that are specific for hash map implementation.
By default, hash map object has initial capacity of sixteen buckets.
That means that at the beginning when we only created hash map object, we have sixteen buckets.
Load factor is equal to zero point seventy five.
What is the load factor.
Load factor is a value that tells when our hash table has to be resized and increased inside the hash
map type you would find in variable with the name threshold.
That is a result of multiplication of capacity and load factor.
So 16 times zero point seventy five equals to twelve.
That means that when twelve buckets will store some value, our hash map will be resized.
After similar situation of hash map source code, we would find that threshold is doubled when we need
to increase our hash map.
One new threshold has reached.
A hash table is rehashed so that the hash table has approximately twice the number of brackets.
Can you understand what capacity and load factor is?
A hash map has specific constructor that allows you to pass integer value to initialize capacity and
flow, add value to initialize load factor in case you want to tune Hashmat performance.
But in real life, default values are used most often.
OK, let's move on now.
Let's imagine that I want to put new entry in my hash map here.
You can see that I have entries that consist of the key and value.
Let it be some string object, key one here and some value.
OK, what happens next after that hash function is applied to compute index of a bucket of the key hash
code, Masset is invoked on the key object.
After we received hash code, we may perform module separation and the reminder would be the index of
a bucket.
After that I place key to the bucket and associated the value with that key.
And after that, each new element is placed in a new bucket.
Based on this, can you understand why adding elements in the hash map always took a constant amount
of time?
Because to put element we need to define bucket for that element and just put it there.
And the separation doesn't depend on a number of elements.
OK, what happens in Case to Case has the same hash called?
The situation may happen because of the hash collision.
I will explain in detail why this might happen a bit later.
For now, just take as a fact that theoretically two different objects may have the same hash code.
According to the flow that I have described, the elements would be put in the same back.
It is a true yes, it is inside.
Each bucket linked list is created.
This is not double list.
It is connected only in one direction.
And it looks like this element in the bucket has reference to the next object with one exception.
In general version eight additional improvement was introduced in performance of hash tables in case
type of key object implements comparable interface.
That means keys might be sorted and in case there are multiple objects in one bucket, there is no link
list with its all of end.
That is linear algorithm complexity.
Instead of the list, there is a binary tree that brings us all of logarithm and complexity of the algorithm.
Does it make sense?
Let's move forward.
To understand why the treatment of animals stay constant amount of time, let me show you how element
is retrieved from the hash map to retrieve elements from the map.
We paskey object.
Hash function is applied to the key.
This allows to define the bucket.
After bucket is defined, keys are checked for quality.
Why?
As you already know, there might be two different objects with the same hash.
That's why algorithm should call equals Masset to compare to objects.
And in the case there are multiple objects in one bucket, algorithm will check a quality until it finds
the match.
That's why it is said that hash code and equals method and work in PR..
Can you stand now on each step hash code and equals method is used.
Awesome.
Now imagine that we have times where we have overridden hash quote masset and hash code returns constant
value.
Imagine that has got message.
Just looks like this on one all the times.
What that would mean for the hash map.
That means that bucket for all objects of this type would be the same.
And instead of taking advantage of hash table and constant amount of time for retrieving elements,
we would get linear time because all elements will be stored in one bucket.
That is exactly the reason why we need to override hash code functions that would return the most unique
integer.
Now let's talk about the requirements for hash code and equals mass.
That should be during the methods overriding the three major requirements that hash could function should
meet Zaya multiple invocation of hash code.
MassArt must consistently return the same integer.
The second requirement if two objects are equal, that means if equal message returns true, then the
hash code also should be equal.
What another statement is follows from this rule that fields that that used to compare objects and feel
that they used to calculate hash.
Code of the object should be the same.
Does it make sense?
And the search requirement includes two objects are not equal.
It is possible that hash codes will be the same.
Let me comment on the statement.
Probably you are wondering how this may happen.
It is an easy mass rule.
Hypothetically, the set of objects is infinite.
We can create as much objects as our hip size will allow us.
And as we increase keep size, we can create even more objects than before.
Whereas Hershkowitz value is not infinite, it exists only within the integer range, no more and no
less.
That's why, hypothetically, hedgcock collisions may happen.
Hash collisions.
That is a state when two different objects that are not equal have the same hash.
Could hope that things are clearer now.
Now let's talk about rules that equals that should meet equals mass should meet five rules.
Zaya equals mass.
It should be reflexive.
This means that for any non non reference value x X equals X should return.
True.
That is obvious.
But still it is worth to mention for complete understanding equals mass.
That should be symmetric.
This means that for any non non reference values, X and Y X equals Y should be true if and only if
Y equals X returns.
True.
Equals mass, it shouldn't be transitive for any non reference value is X, Y and Z.
If X equals Y returns true and Y equals that return true, then X equals Z should return true equals
mass.
It should be consistent for any nominal reference values X and Y, multiple invocations of X equals
Y should be consistent.
And last but not the list requirement is that for any non reference value x x equals now should return
false.
A bit later today during the practice, we'll review how to override hash code and equals MassArt.
Let's start our practice exercises, we have in now theoretical knowledge right now to understand the
next examples.
Before the lesson, I prepared a file with examples that will help you to understand how maps work.
Let me run the program and walk you through council output.
Here I declare a map very similar to collection and types.
Map type is also parametrized.
Hope you don't skip lessons about least implementations where I explained on the high level how Diament
operator works.
We're also going to learn genetics and a separate lesson.
So don't worry much about that.
Handyman's operator specifies that keys in this map would have integer type and values and this map
would have string type I initialize.
This object was a reference to the Hashmat object.
If we want to put entries in the map, you can see example here, I just called Put Masset and pass
integer and string.
If I want to get a map, I have to use key.
For example, if I want to retrieve string one, I just want to get MassArt like this and console.
You can see that we printed the values that is associated with the key take into account key set returns,
the implementation of that interface.
And we already know that that extends collection.
That in turn extends iterable.
This means I can use foreach loop to iterate over elements.
And here I printed all keys to console the next thing I want to show you is an example how you might
iterate over all entries in MAP.
I take entries said from my map here and specify in variable here of map entry type since entry interface
is declared inside map interface.
From the syntax standpoint, I have to put DOT here.
My entry will be parametrized by integer and string that the same types that keys and values have.
In my map you can see that I use central variable to retrieve key and value.
Here also damos of the get on the fourth method, I want to draw your attention that in case our entry
exists in the map, like entry was a key for default, value won't be returned even in case the value
is not, the default value will be returned only in case the entry doesn't exist.
And that was entry was the key five.
Would have absolute mass, it will put value associated with the key in case if he is not already associated
with the value or associated with it now and here you can see that I call this method for the entry
was key for and after that, I checked what the value is updated and it was successfully updated.
And now let me show you a few examples that are related to old maps that are implemented on the basis
of hash tables.
Imagine that we have some type called default product and default user.
If you don't remember these types, they are from your previous homework about implementation of online
store.
Let me read map work.
Use will be of type user and values will be of type product.
I create the false user object and the full product object.
Now let me put one entry to the map.
Now imagine that in some other part of my program I retrieve user from the database or receive user
information from the front end and I create the new Java object, but with the same state for my John
Smith user.
And after that I want to get product objects for this user from the map by my user key I receive now
known how hash tables work.
Can you understand why I receive now and why my product value is lost in my map?
Post the media for a second and try to answer this question.
Let me answer this.
This is because hash function is applied for the user object.
But what value is returned?
Schenkkan So you can see what has caused massive returns for my user object and user copy object.
They're different.
That means I have to override hash code message in user class so that it will constantly return the
same hash code for equal users to save time.
During the lesson I created one more implementation of user interface that overrides hash code and equals
method.
Let's look at it.
So here you can see that I have hash code and equals method overridden.
How to override method.
Personally, I use Eclipse for that.
In most of the cases I press hotkeys alz shift as in case you forgot hotkeys just press mouse right
click source and find here generate hash code and equals.
Eclipse asks whether I need to override this method one more time.
Taking into account I already have this method.
I will click here to show user interface of eclipse here can you can choose fields that you want to
use for equals and has called massive.
Please pay attention that you will now want to use static fields in equals and hash code methods.
Can you understand why?
Because static fields are related to the class itself rather than to object of this class.
And in case you will use static fields for calculating hash code or equals, these masses wouldn't meet
the requirements which we talked about in this lesson.
Here's one checkbox that I usually check is to use methods from object class.
This makes our methods written in a different way.
That takes less lines of code than without using objects class.
There is also one another checkbox that you might want to select.
Sometimes I will show you the difference.
So here you just click generate and methods are generated.
I will cancel because I already generated masjids.
Here's a hash code method.
Optionally, you can investigate how hash method is implemented.
You can see that I call hash method on object class and pass all fields that I want to be taken into
account to compute the hash of the object.
Now, multiple invocation of code method and different objects.
All the channels, the same integer value here is our equals method.
At the beginning we check equality by references if references as a same religion.
True, if objects that we pass to the method is now, then we return false.
Now I get class of the current object and get class of the object that we got from that argument.
And potentially you can use here instance of operator, for example, in the case it is not critical
for you that objects are created on the basis of different classes, sometimes for use.
The fact that two different objects are compatible with type and have the same state is enough to tell
that both of them are equal.
But it depends personally in most cases.
I use that clause here, but I have to warn you that you might want to use instances of operator here
to check compatibility and that is also fine.
After this check, we can cast object to the current class type and check for quality field by field
in case all state from the other object is the same as state of this object, then very trencher.
Can you understand now why the set of fields that we use in equals and hash code MassArt should be the
same?
Great.
Let's get back to our demo file now.
We create the object of our type that overrides hash code and equals method, we put it.
As a key in our map and map it against our product.
After that, I read the same copy of our user analysis that we did previous time, and now I want to
get my product by the key.
And here it is.
I managed to retrieve product from a map because my hash table was managed to find the right market
and the value in it.
Now imagine that for some reasons, the state of the user is changed in the database.
Let's imagine that John Smith decided to change his email address and now he uses new email domain.
Lets retrieve that product again and then consult with him.
Now, can you understand why?
Because in our case, we use all fields of user to compute hash code, as you remember.
And when email was changed, hash code also was changed.
But the object that is used for key in the map still uses the old email and definitely our hash map
can't find the right market was our key to return a product.
That's why it is recommended to use immutable objects for keys.
What are immutable objects?
The objects, the state of which is never changed after its creation.
The example of a mutable type is strength.
This object is designed in the way that there is no any method that can change state of the original
object after its creation.
The intention to replace method, for example, it should replace some characters with others.
You would notice that this method returns new objects of string, but not modifies the previous one.
In case you use mutable keys and hash map, pay extra attention that the key is stable, but usually
is a string or integer.
Objects are used as keys.
I believe we learned a lot about hash tables and the last thing that I would like to share with you
is to show you how to sort my bike keys and values.
Here is a separate file with the examples of maps stored in the same hash map.
Object is created here with a similar data set as we had in previous example.
Now, if you remember from the last about map interface we have comparing bickie and comparing Vivarium
assets in our entry type to search entries in the map, you already know that list interface has search
method, musical action.
Nawzad interface has sought MassArt.
That's why we have to use the latest object and create variable of this type parametrized by entry type.
That in turn is parametrized by integer and string.
Probably you notice that I use just entry word in this file.
That is because I have a statement here for map entry time.
After that I create a real E object and pass to the constructor and reset of my map.
Now I can search elements in this list and enter type has default method that returns comparator to
source entries by key.
I want to shuffle elements before Soden to make sure that certain work is expected to shuffle elements
and your special message from collections class with utility methods nonwar will review this class in
the separate lesson.
Right now I will use only one method from that class for the demo purposes.
I print shuffled elements to console to prove that they are not sorted.
After that, I saw the elements and print source at least to the console.
Let me run the program and here you can see that all elements and least assorted now.
Awesome.
Just want to pay attention.
This sort only four keys that implements comparable interface if your key doesn't implement comparable
Xeros overloaded version of comparing by key method that also takes Comparator as an argument.
And we already had separate lesson and homework regarding Khambatta.
That's why I will not stop on this.
In case you would face issues, let me know and write in comments.
I will help you to source my keys.
It is also super easy to create an object of three map and add entries to that map.
To put all entries to three map.
I use special constructor that takes any map as an argument.
We are going to have separate lesson about sorted map and three map.
But you already familiar with key features of this interface and class from the map Iraqi lesson and
take into account.
We are talking about sorting of elements.
It was dimension to the map here and last but not least for today, is how to search your map by values.
We again shuffle entries before sorting.
After that, we use comparator that can be created by entry type.
And again, this comparing by value method has overloaded versions.
That takes Comparator as an argument that is in case your values don't implement comparable.
And here we print list of entries sorted by value.
You remember that to convert an array of entries to map, we have a special method of entries, but
they use it efficiently.
We have to understand functional from.
Ramin Anjelah, so conversion looks something like this.
This is one of the options I showed you that just to make you understand that I remember everything
and I want to separate lessons in the way you would understand.
Amerson Don't worry.
We will cover the topic separately in other lessons.
Right now, I want to recap what we have learned today.
In this lesson, we learned how hash tables work.
Now you know how to override equals and hash code masset and water requirements exist for these methods.
Today, we had a lot of practice with Hashmat.
You main message and how to work with Hashmat.
Also, we learned what immutable objects are and understood why immutable objects and good keys for
our maps.
And at the end of the lesson we learned how to search Mambi keys and Beverley's.
I believe this was extremely fruitful lesson.
Thanks a lot for your attention.
See you in the next lesson.