File size: 19,176 Bytes

2e5dac7

1
00:00:06,000 --> 00:00:10,000
Hello, adjustments in this lesson, we're going to learn another implementation of map interface,

2
00:00:10,000 --> 00:00:16,000
let us dream that we are going to learn in detail such interfaces as sort of map and navigable map.

3
00:00:17,000 --> 00:00:20,000
This would help us a lot in understanding of dreama behavior.

4
00:00:20,000 --> 00:00:25,000
And at the end of the lesson, we'll have practice with three map and I'll show you how you can use

5
00:00:25,000 --> 00:00:31,000
this map with keys that are implements comparable interface and with keys that don't implement comparable

6
00:00:31,000 --> 00:00:32,000
interface.

7
00:00:32,000 --> 00:00:38,000
We are going to learn what the minority is, what red black minority is and why big ol notational three

8
00:00:38,000 --> 00:00:42,000
map for its major operations is all of luck.

9
00:00:42,000 --> 00:00:48,000
And let's start and to start with, I'd like to jump to the source code of the sort of map interface

10
00:00:48,000 --> 00:00:53,000
to investigate what message I introduce that here is the source code of sorts of map interface.

11
00:00:53,000 --> 00:00:55,000
It extends map interface.

12
00:00:55,000 --> 00:01:02,000
As you can see here, the first method here in our list is compared to this message of return comparatives

13
00:01:02,000 --> 00:01:08,000
that is used in map to source keys or now if such comparator is absent and MAP uses natural ordering

14
00:01:08,000 --> 00:01:09,000
of keys.

15
00:01:10,000 --> 00:01:16,000
To be honest, this method was not used by me and I think it is not very popular because if you use

16
00:01:16,000 --> 00:01:21,000
some comparator to source keys in the map, that means you have the reference to this computer already

17
00:01:21,000 --> 00:01:25,000
somewhere in your program and there is no need to get it from the map.

18
00:01:25,000 --> 00:01:28,000
And in keys are sorted according to natural order.

19
00:01:28,000 --> 00:01:32,000
And there is no sense to call this method because now will be returned.

20
00:01:32,000 --> 00:01:37,000
But now you at least known about this method and can use it someday in the future when this will be

21
00:01:37,000 --> 00:01:38,000
named.

22
00:01:38,000 --> 00:01:41,000
The next method here is some map.

23
00:01:41,000 --> 00:01:45,000
I would even say that it is similar to subleased from Liste interface.

24
00:01:45,000 --> 00:01:47,000
The principle applied is the same here.

25
00:01:47,000 --> 00:01:55,000
We have to specify a key from inclusively and key to exclusively and we will get new sorted map in response.

26
00:01:55,000 --> 00:02:01,000
It is also worth to mention that the majority of methods and so that map potentially Mistral class cost

27
00:02:01,000 --> 00:02:08,000
exception in the case keys can't be cost to comparable interface or in case there is no comparison available

28
00:02:08,000 --> 00:02:08,000
in this map.

29
00:02:09,000 --> 00:02:14,000
Besides, with exceptions, there are also a few more potential exceptions that are pretty straightforward.

30
00:02:14,000 --> 00:02:17,000
Not pass now as Massata argument.

31
00:02:17,000 --> 00:02:22,000
In case you don't want to catch Northpoint exception and do not pass from Ki's that is greater than

32
00:02:22,000 --> 00:02:25,000
Tukey to not get a legal argument exception.

33
00:02:25,000 --> 00:02:27,000
The next method is HapMap.

34
00:02:27,000 --> 00:02:30,000
It returns the view of the map that is less than key given.

35
00:02:30,000 --> 00:02:36,000
For example, if you to retrieve all entries at the last and some specific key you can use.

36
00:02:36,000 --> 00:02:39,000
This method to map works in the opposite way.

37
00:02:39,000 --> 00:02:44,000
It returns the view of the map that contains entries with keys that are greater than or equal to the

38
00:02:44,000 --> 00:02:48,000
keys that will be passed as method argument here also.

39
00:02:48,000 --> 00:02:53,000
So that map provides the massive that allows us to access first and Laskey.

40
00:02:53,000 --> 00:02:57,000
That in turn will allow us to retrieve value from map by this key.

41
00:02:57,000 --> 00:03:01,000
That's why we have first massive that returns the lowest key.

42
00:03:01,000 --> 00:03:07,000
And Laskey, Massachusetts returns the highest key key said the method similar to the one we have in

43
00:03:07,000 --> 00:03:08,000
our map interface.

44
00:03:08,000 --> 00:03:15,000
But with clarifications to its implementation, the set that will be returned has iterator that returns

45
00:03:15,000 --> 00:03:17,000
the keys in ascending order.

46
00:03:17,000 --> 00:03:19,000
Well, this method returns collections.

47
00:03:19,000 --> 00:03:26,000
That has iterator, that returns the values in ascending order of the corresponding case and last method

48
00:03:26,000 --> 00:03:27,000
here that is also familiar to you.

49
00:03:27,000 --> 00:03:34,000
That is entry, said Estrogen's entries in ascending key order that's so massive that introduced and

50
00:03:34,000 --> 00:03:35,000
studied map interface.

51
00:03:35,000 --> 00:03:40,000
Let's move further and look at the popular interface that extends the solid map interface.

52
00:03:40,000 --> 00:03:42,000
I'm talking about navigable map.

53
00:03:42,000 --> 00:03:45,000
Here is the source code of navigable map interface.

54
00:03:46,000 --> 00:03:49,000
Let's look through the massive data declared here and I will give my comments.

55
00:03:50,000 --> 00:03:56,000
The main feature of this map is that it returns the closest matches for given search Target's main message

56
00:03:56,000 --> 00:04:00,000
that they introduced in this interface and created to reach this goal.

57
00:04:00,000 --> 00:04:04,000
For example, here's the first matter now at least lower entry.

58
00:04:04,000 --> 00:04:10,000
It returns an entry that is key value mapping associated with the greatest key that is strictly less

59
00:04:10,000 --> 00:04:11,000
than the given key.

60
00:04:12,000 --> 00:04:16,000
I'm going to show you this massive difference, the demo in a few minutes to make you understand how

61
00:04:16,000 --> 00:04:17,000
this method works.

62
00:04:17,000 --> 00:04:22,000
On example, lower key, Masset returns not entry, but on the key.

63
00:04:22,000 --> 00:04:25,000
It returns the greatest keys that is typically less than the given.

64
00:04:25,000 --> 00:04:28,000
Key to next method is floor entry.

65
00:04:28,000 --> 00:04:34,000
It is different from low entry because it returns key value mapping associated with the greatest key.

66
00:04:34,000 --> 00:04:40,000
That is not strictly less of the key, but is a less than or equal to the given keys that will be passed

67
00:04:40,000 --> 00:04:43,000
as method argument for key regions.

68
00:04:43,000 --> 00:04:47,000
Not entry, but only key according to the logic that we have just discussed.

69
00:04:48,000 --> 00:04:53,000
Celan entry regions entry associated with the Leskie greater than or equal to the given key.

70
00:04:54,000 --> 00:05:00,000
I always do analogy for myself with the real ceiling in my house to remember the logic for this matter.

71
00:05:00,000 --> 00:05:03,000
So this message should return the.

72
00:05:03,000 --> 00:05:08,000
That is right on my ceiling or above it, but not the element from the next floor.

73
00:05:08,000 --> 00:05:14,000
That's why it is set about liste entry greater than or equal to the given key.

74
00:05:14,000 --> 00:05:16,000
Does it make more sense now?

75
00:05:17,000 --> 00:05:24,000
Holmes's understanding will help you the same as it helps me see key returns key according to the ceiling

76
00:05:24,000 --> 00:05:31,000
logic that we have just talked about, the next Masad higher entry written entry with the key that is

77
00:05:31,000 --> 00:05:33,000
strictly greater than the given key.

78
00:05:34,000 --> 00:05:40,000
In this particular case, I always want to get aliment from the next floor, the disclosers and other

79
00:05:40,000 --> 00:05:41,000
elements to my ceiling.

80
00:05:42,000 --> 00:05:47,000
This this example, in case we want to continue a real life analogy with the house that we started during

81
00:05:47,000 --> 00:05:50,000
the learning of previous Masset hierarchy.

82
00:05:51,000 --> 00:05:54,000
I believe you already understood the way how these methods are structured here.

83
00:05:55,000 --> 00:06:00,000
Also, navigable map will provide you fast access to the first entry in the map.

84
00:06:00,000 --> 00:06:07,000
That is the answer was at least key to yet it just called for a center method and also access will be

85
00:06:07,000 --> 00:06:10,000
provided to the last element in the tree to get it.

86
00:06:10,000 --> 00:06:17,000
Jesco last entry here you can find a method similar to those that you saw in Q and DEC interfaces.

87
00:06:17,000 --> 00:06:21,000
We can get and remove first entry from the map for that pole.

88
00:06:21,000 --> 00:06:22,000
First entry.

89
00:06:22,000 --> 00:06:27,000
MassArt exists and we can get and remove last entry from the map by Colin Powell.

90
00:06:27,000 --> 00:06:32,000
Last entry, take into account the navigable map is sorted map.

91
00:06:32,000 --> 00:06:35,000
We also can get navigable map in reverse order.

92
00:06:35,000 --> 00:06:37,000
We have to call Distending Map.

93
00:06:37,000 --> 00:06:44,000
In this case we also can get navigable set and the standard set by the method name and believe it is

94
00:06:44,000 --> 00:06:48,000
clear that order of keys in the he said is reversed.

95
00:06:49,000 --> 00:06:55,000
He said life message that we also saw in sort of map, but it works with additional MassArt parameters.

96
00:06:55,000 --> 00:07:02,000
In this case, developer can specify whether we want from key inclusively or not the same as we stookey

97
00:07:02,000 --> 00:07:07,000
that the level of flexibility that is added in addition to some map from sorted map interface.

98
00:07:08,000 --> 00:07:15,000
We also have had map and tail map massas declared in this interface with only one difference that we

99
00:07:15,000 --> 00:07:20,000
can specify boolean flag to include or exclude the key from the result.

100
00:07:21,000 --> 00:07:26,000
And the last three matters here are equivalent to the ones that are declared in solid map interface.

101
00:07:26,000 --> 00:07:28,000
Now it is time to practice a bit.

102
00:07:29,000 --> 00:07:32,000
And for the sake of the demo, I prepared the file with examples.

103
00:07:32,000 --> 00:07:37,000
I will also share it with you so that you could practice and run the code on your computer.

104
00:07:38,000 --> 00:07:44,000
Let me run the program and walk you through the console output here and declare the variable of navigable

105
00:07:44,000 --> 00:07:51,000
map type and initialize it with three map object, three map extents, observe map and implements navigable

106
00:07:51,000 --> 00:07:51,000
map.

107
00:07:52,000 --> 00:07:57,000
It is considered as the most popular implementation of navigable and sorted map interfaces.

108
00:07:58,000 --> 00:07:59,000
For the sake of the demo.

109
00:07:59,000 --> 00:08:03,000
I just put integers and strings into this map like this.

110
00:08:03,000 --> 00:08:09,000
And here you can see different examples of me using the first entry, lower entry, floor entry, higher

111
00:08:09,000 --> 00:08:11,000
entry and Celan entry methods.

112
00:08:11,000 --> 00:08:18,000
I used three as a key for all Magidson and locations so that you could see the difference here.

113
00:08:18,000 --> 00:08:24,000
You can see that even despite the order in which we put entries when we retrieve first entry, we got

114
00:08:24,000 --> 00:08:32,000
one because integer object implements comparable interface and integer objects know how to compare themselves

115
00:08:32,000 --> 00:08:33,000
with the other integers.

116
00:08:34,000 --> 00:08:36,000
Does it make sense now?

117
00:08:36,000 --> 00:08:42,000
When I call lower entry, I receive two because the condition for this method is that entry with the

118
00:08:42,000 --> 00:08:45,000
greatest key that is strictly less will be returned.

119
00:08:46,000 --> 00:08:51,000
But when I call floor entry for keys three, I receive entry with the key three because condition is

120
00:08:51,000 --> 00:08:57,000
different and it allows the key would be equal to the one even as method argument.

121
00:08:58,000 --> 00:09:04,000
Similar story with higher entry and Celan entry, but in another direction here, a printed map and

122
00:09:04,000 --> 00:09:06,000
you can see that it is ordered.

123
00:09:06,000 --> 00:09:11,000
I can easily get map in descending order by calling the standing map method.

124
00:09:11,000 --> 00:09:15,000
And here you can see in console's at all entries assaulted in the reverse order.

125
00:09:16,000 --> 00:09:22,000
Now the thing that you should remember is that we will throw class cost exception in case you would

126
00:09:22,000 --> 00:09:25,000
put objects that don't implement comparable interface.

127
00:09:26,000 --> 00:09:28,000
But what to do in such cases?

128
00:09:28,000 --> 00:09:34,000
We have to pass comparator to the three map constructor that is going to be used to compare keys inside

129
00:09:35,000 --> 00:09:40,000
here I created one more map where our keys will be of type products that we used for our online store

130
00:09:40,000 --> 00:09:44,000
creation and our values would be of type user.

131
00:09:44,000 --> 00:09:50,000
But the type of the value does not make a big difference since Shorten is performed by keys.

132
00:09:50,000 --> 00:09:56,000
And here you can see that I created object of comparison that we implemented during one of our homeworks

133
00:09:56,000 --> 00:09:58,000
and put this object in constructor here.

134
00:09:59,000 --> 00:10:05,000
Now I add few entries here and when I printed to console each key from you, I you can see that all

135
00:10:05,000 --> 00:10:09,000
of them are sorted in order that is defined by our comparator.

136
00:10:10,000 --> 00:10:14,000
That's why three map is often used to sort map by its case.

137
00:10:14,000 --> 00:10:21,000
That said, regarding examples of how you can use to map the next things that I'd like to talk about

138
00:10:21,000 --> 00:10:25,000
is performance of three map and how Swardson is implemented in this container.

139
00:10:26,000 --> 00:10:31,000
The first thing that is worth to mention is that we map is not based on hash table.

140
00:10:31,000 --> 00:10:34,000
It is based on red, black, self balanced binary tree.

141
00:10:35,000 --> 00:10:42,000
That's why complexity of algorithms for main operations like get put remove is a big O of logarithm

142
00:10:42,000 --> 00:10:48,000
at the dive into the details and explain what an algorithm is I and to try to explain it in these words.

143
00:10:49,000 --> 00:10:50,000
The performance is not linear.

144
00:10:50,000 --> 00:10:56,000
That means it doesn't depend on a number of elements in the map in one to one proportion.

145
00:10:56,000 --> 00:11:01,000
But performance is Calan as we have more elements to visualize this in your head.

146
00:11:02,000 --> 00:11:03,000
Take a look at this slide.

147
00:11:03,000 --> 00:11:09,000
You can see the visualization of mapping between number of elements and times that it takes for specific

148
00:11:09,000 --> 00:11:12,000
operations mapped to the connotation.

149
00:11:12,000 --> 00:11:18,000
You also can find the core of the algorithm and on the picture how this makes things clearer.

150
00:11:19,000 --> 00:11:23,000
How is this achieved because of the red black self balance binary tree.

151
00:11:23,000 --> 00:11:24,000
Let's learn.

152
00:11:24,000 --> 00:11:25,000
What is it?

153
00:11:25,000 --> 00:11:30,000
Let me start from explaining what a binary tree is in simple words.

154
00:11:30,000 --> 00:11:37,000
This is such an algorithm that consists of the nodes or leaves that source links to notes that are greater

155
00:11:37,000 --> 00:11:40,000
on the right and notes that are less on the left.

156
00:11:40,000 --> 00:11:46,000
This tree has the root and that's why we can say that all elements that are greater than the root are

157
00:11:46,000 --> 00:11:51,000
stored on the right and all elements that are less than the root are stored on the left.

158
00:11:52,000 --> 00:11:57,000
That's why when I need to find a specific element, I don't iterate over all elements.

159
00:11:57,000 --> 00:12:00,000
I go only to show this past.

160
00:12:00,000 --> 00:12:02,000
I have to go to find the elements that I need.

161
00:12:03,000 --> 00:12:06,000
One potential problem you can see in binary tree.

162
00:12:07,000 --> 00:12:08,000
The problem is.

163
00:12:08,000 --> 00:12:14,000
Defines the root of the tree in case will define the root and all foreign elements will be greater than

164
00:12:14,000 --> 00:12:16,000
the root and will be placed on the right.

165
00:12:17,000 --> 00:12:23,000
Then I will get linked list and performance of main operations will be worse than in binary three and

166
00:12:23,000 --> 00:12:24,000
will be linear.

167
00:12:24,000 --> 00:12:30,000
What to do in this case, it might be a good idea to recalculate the root of the tree on regular basis,

168
00:12:30,000 --> 00:12:36,000
to have the same or almost the same number of elements on the right and on the left side of the root.

169
00:12:37,000 --> 00:12:45,000
That the moment when red black tree comes into the game, each node stores an extra to and caller used

170
00:12:45,000 --> 00:12:50,000
to ensure that the tree remains approximately balanced urine insertions or deletions.

171
00:12:50,000 --> 00:12:58,000
That also ensures because of the algorithm and complexity for main operations with red black tree tracking,

172
00:12:58,000 --> 00:13:04,000
the color of each node requires only one bit of information overload because there are only two colors.

173
00:13:05,000 --> 00:13:07,000
Does it make sense now?

174
00:13:07,000 --> 00:13:11,000
You know how sordidness performed into map and how it works inside.

175
00:13:12,000 --> 00:13:14,000
That's all what I wanted to share with you.

176
00:13:14,000 --> 00:13:16,000
Let's recap what we have learned today.

177
00:13:17,000 --> 00:13:20,000
Labellers sorted map interface and navigable map interface.

178
00:13:21,000 --> 00:13:24,000
Now, you know, nattered that are declared in these interfaces.

179
00:13:24,000 --> 00:13:29,000
Also we had the practice Westry map and now you know how you can use it.

180
00:13:29,000 --> 00:13:33,000
We learned what a binary tree is and what a red black binary tree is.

181
00:13:34,000 --> 00:13:40,000
Now, you know why performance of major operations of tree map has logarithmic connotation.

182
00:13:40,000 --> 00:13:41,000
That's it for today.

183
00:13:42,000 --> 00:13:45,000
Thanks a lot for your attention and see you in the next lesson.