Hello, adjustments in this lesson, we're going to learn another implementation of map interface,
let us dream that we are going to learn in detail such interfaces as sort of map and navigable map.
This would help us a lot in understanding of dreama behavior.
And at the end of the lesson, we'll have practice with three map and I'll show you how you can use
this map with keys that are implements comparable interface and with keys that don't implement comparable
interface.
We are going to learn what the minority is, what red black minority is and why big ol notational three
map for its major operations is all of luck.
And let's start and to start with, I'd like to jump to the source code of the sort of map interface
to investigate what message I introduce that here is the source code of sorts of map interface.
It extends map interface.
As you can see here, the first method here in our list is compared to this message of return comparatives
that is used in map to source keys or now if such comparator is absent and MAP uses natural ordering
of keys.
To be honest, this method was not used by me and I think it is not very popular because if you use
some comparator to source keys in the map, that means you have the reference to this computer already
somewhere in your program and there is no need to get it from the map.
And in keys are sorted according to natural order.
And there is no sense to call this method because now will be returned.
But now you at least known about this method and can use it someday in the future when this will be
named.
The next method here is some map.
I would even say that it is similar to subleased from Liste interface.
The principle applied is the same here.
We have to specify a key from inclusively and key to exclusively and we will get new sorted map in response.
It is also worth to mention that the majority of methods and so that map potentially Mistral class cost
exception in the case keys can't be cost to comparable interface or in case there is no comparison available
in this map.
Besides, with exceptions, there are also a few more potential exceptions that are pretty straightforward.
Not pass now as Massata argument.
In case you don't want to catch Northpoint exception and do not pass from Ki's that is greater than
Tukey to not get a legal argument exception.
The next method is HapMap.
It returns the view of the map that is less than key given.
For example, if you to retrieve all entries at the last and some specific key you can use.
This method to map works in the opposite way.
It returns the view of the map that contains entries with keys that are greater than or equal to the
keys that will be passed as method argument here also.
So that map provides the massive that allows us to access first and Laskey.
That in turn will allow us to retrieve value from map by this key.
That's why we have first massive that returns the lowest key.
And Laskey, Massachusetts returns the highest key key said the method similar to the one we have in
our map interface.
But with clarifications to its implementation, the set that will be returned has iterator that returns
the keys in ascending order.
Well, this method returns collections.
That has iterator, that returns the values in ascending order of the corresponding case and last method
here that is also familiar to you.
That is entry, said Estrogen's entries in ascending key order that's so massive that introduced and
studied map interface.
Let's move further and look at the popular interface that extends the solid map interface.
I'm talking about navigable map.
Here is the source code of navigable map interface.
Let's look through the massive data declared here and I will give my comments.
The main feature of this map is that it returns the closest matches for given search Target's main message
that they introduced in this interface and created to reach this goal.
For example, here's the first matter now at least lower entry.
It returns an entry that is key value mapping associated with the greatest key that is strictly less
than the given key.
I'm going to show you this massive difference, the demo in a few minutes to make you understand how
this method works.
On example, lower key, Masset returns not entry, but on the key.
It returns the greatest keys that is typically less than the given.
Key to next method is floor entry.
It is different from low entry because it returns key value mapping associated with the greatest key.
That is not strictly less of the key, but is a less than or equal to the given keys that will be passed
as method argument for key regions.
Not entry, but only key according to the logic that we have just discussed.
Celan entry regions entry associated with the Leskie greater than or equal to the given key.
I always do analogy for myself with the real ceiling in my house to remember the logic for this matter.
So this message should return the.
That is right on my ceiling or above it, but not the element from the next floor.
That's why it is set about liste entry greater than or equal to the given key.
Does it make more sense now?
Holmes's understanding will help you the same as it helps me see key returns key according to the ceiling
logic that we have just talked about, the next Masad higher entry written entry with the key that is
strictly greater than the given key.
In this particular case, I always want to get aliment from the next floor, the disclosers and other
elements to my ceiling.
This this example, in case we want to continue a real life analogy with the house that we started during
the learning of previous Masset hierarchy.
I believe you already understood the way how these methods are structured here.
Also, navigable map will provide you fast access to the first entry in the map.
That is the answer was at least key to yet it just called for a center method and also access will be
provided to the last element in the tree to get it.
Jesco last entry here you can find a method similar to those that you saw in Q and DEC interfaces.
We can get and remove first entry from the map for that pole.
First entry.
MassArt exists and we can get and remove last entry from the map by Colin Powell.
Last entry, take into account the navigable map is sorted map.
We also can get navigable map in reverse order.
We have to call Distending Map.
In this case we also can get navigable set and the standard set by the method name and believe it is
clear that order of keys in the he said is reversed.
He said life message that we also saw in sort of map, but it works with additional MassArt parameters.
In this case, developer can specify whether we want from key inclusively or not the same as we stookey
that the level of flexibility that is added in addition to some map from sorted map interface.
We also have had map and tail map massas declared in this interface with only one difference that we
can specify boolean flag to include or exclude the key from the result.
And the last three matters here are equivalent to the ones that are declared in solid map interface.
Now it is time to practice a bit.
And for the sake of the demo, I prepared the file with examples.
I will also share it with you so that you could practice and run the code on your computer.
Let me run the program and walk you through the console output here and declare the variable of navigable
map type and initialize it with three map object, three map extents, observe map and implements navigable
map.
It is considered as the most popular implementation of navigable and sorted map interfaces.
For the sake of the demo.
I just put integers and strings into this map like this.
And here you can see different examples of me using the first entry, lower entry, floor entry, higher
entry and Celan entry methods.
I used three as a key for all Magidson and locations so that you could see the difference here.
You can see that even despite the order in which we put entries when we retrieve first entry, we got
one because integer object implements comparable interface and integer objects know how to compare themselves
with the other integers.
Does it make sense now?
When I call lower entry, I receive two because the condition for this method is that entry with the
greatest key that is strictly less will be returned.
But when I call floor entry for keys three, I receive entry with the key three because condition is
different and it allows the key would be equal to the one even as method argument.
Similar story with higher entry and Celan entry, but in another direction here, a printed map and
you can see that it is ordered.
I can easily get map in descending order by calling the standing map method.
And here you can see in console's at all entries assaulted in the reverse order.
Now the thing that you should remember is that we will throw class cost exception in case you would
put objects that don't implement comparable interface.
But what to do in such cases?
We have to pass comparator to the three map constructor that is going to be used to compare keys inside
here I created one more map where our keys will be of type products that we used for our online store
creation and our values would be of type user.
But the type of the value does not make a big difference since Shorten is performed by keys.
And here you can see that I created object of comparison that we implemented during one of our homeworks
and put this object in constructor here.
Now I add few entries here and when I printed to console each key from you, I you can see that all
of them are sorted in order that is defined by our comparator.
That's why three map is often used to sort map by its case.
That said, regarding examples of how you can use to map the next things that I'd like to talk about
is performance of three map and how Swardson is implemented in this container.
The first thing that is worth to mention is that we map is not based on hash table.
It is based on red, black, self balanced binary tree.
That's why complexity of algorithms for main operations like get put remove is a big O of logarithm
at the dive into the details and explain what an algorithm is I and to try to explain it in these words.
The performance is not linear.
That means it doesn't depend on a number of elements in the map in one to one proportion.
But performance is Calan as we have more elements to visualize this in your head.
Take a look at this slide.
You can see the visualization of mapping between number of elements and times that it takes for specific
operations mapped to the connotation.
You also can find the core of the algorithm and on the picture how this makes things clearer.
How is this achieved because of the red black self balance binary tree.
Let's learn.
What is it?
Let me start from explaining what a binary tree is in simple words.
This is such an algorithm that consists of the nodes or leaves that source links to notes that are greater
on the right and notes that are less on the left.
This tree has the root and that's why we can say that all elements that are greater than the root are
stored on the right and all elements that are less than the root are stored on the left.
That's why when I need to find a specific element, I don't iterate over all elements.
I go only to show this past.
I have to go to find the elements that I need.
One potential problem you can see in binary tree.
The problem is.
Defines the root of the tree in case will define the root and all foreign elements will be greater than
the root and will be placed on the right.
Then I will get linked list and performance of main operations will be worse than in binary three and
will be linear.
What to do in this case, it might be a good idea to recalculate the root of the tree on regular basis,
to have the same or almost the same number of elements on the right and on the left side of the root.
That the moment when red black tree comes into the game, each node stores an extra to and caller used
to ensure that the tree remains approximately balanced urine insertions or deletions.
That also ensures because of the algorithm and complexity for main operations with red black tree tracking,
the color of each node requires only one bit of information overload because there are only two colors.
Does it make sense now?
You know how sordidness performed into map and how it works inside.
That's all what I wanted to share with you.
Let's recap what we have learned today.
Labellers sorted map interface and navigable map interface.
Now, you know, nattered that are declared in these interfaces.
Also we had the practice Westry map and now you know how you can use it.
We learned what a binary tree is and what a red black binary tree is.
Now, you know why performance of major operations of tree map has logarithmic connotation.
That's it for today.
Thanks a lot for your attention and see you in the next lesson.