File size: 12,136 Bytes

2e5dac7

1
00:00:05,000 --> 00:00:10,000
Hello, dear students in this class, and we are going to talk about one more implementation of map

2
00:00:10,000 --> 00:00:16,000
interface linked hash map, we're going to understand how the hash map is different from hash map will

3
00:00:16,000 --> 00:00:20,000
review structure of link, hash map and we'll review methods that it has.

4
00:00:21,000 --> 00:00:26,000
I'm going to explain to you what the cash is and how we can implement our own cash with the help of

5
00:00:26,000 --> 00:00:27,000
the hash map.

6
00:00:27,000 --> 00:00:32,000
Also, we'll learn how to implement logic that would keep fixed number of elements in our linked hash

7
00:00:32,000 --> 00:00:33,000
map object.

8
00:00:33,000 --> 00:00:36,000
Let's start to understand how linked hash map work.

9
00:00:36,000 --> 00:00:38,000
Let's look at this slide.

10
00:00:38,000 --> 00:00:44,000
First of all, what we have to understand is that hash map is also implemented on the base of hash table.

11
00:00:44,000 --> 00:00:47,000
Then hash map has projectable iteration order.

12
00:00:48,000 --> 00:00:49,000
How is this achieved?

13
00:00:49,000 --> 00:00:53,000
It is achieved because of the support of double placed inside.

14
00:00:53,000 --> 00:00:54,000
On the screen.

15
00:00:54,000 --> 00:00:59,000
You can see the image that represents the structure of each bucket and hash table and in addition to

16
00:00:59,000 --> 00:01:03,000
that, the properties that allows us to link elements in both directions.

17
00:01:04,000 --> 00:01:10,000
That's why when we insert each new entry in the hash map, each entry now is about the next and previous

18
00:01:10,000 --> 00:01:15,000
entry that allows us to iterate over this data structure with predictable order.

19
00:01:16,000 --> 00:01:20,000
There are also a few more differences in length hash map that I would like to show you in the source

20
00:01:20,000 --> 00:01:20,000
code.

21
00:01:21,000 --> 00:01:24,000
Here is a source code of linked hash map class.

22
00:01:24,000 --> 00:01:29,000
Notice that it extends hash map class and implements map interface.

23
00:01:29,000 --> 00:01:35,000
I'd like to draw attention to the special constructor that also takes Boolean Flag as one of the arguments.

24
00:01:35,000 --> 00:01:41,000
This documentation set that we have to pass through for access, order and force for insertion order.

25
00:01:41,000 --> 00:01:47,000
When I read this first time for me it is not obvious what is the difference between axis order and insertion

26
00:01:47,000 --> 00:01:47,000
order.

27
00:01:48,000 --> 00:01:51,000
I would say that these are two a different order mechanism.

28
00:01:51,000 --> 00:01:58,000
By default it is insertion order, but we can set access order by passing through into this constructor

29
00:01:59,000 --> 00:01:59,000
access.

30
00:01:59,000 --> 00:02:05,000
So the strategy will ensure that order of iteration of elements is the order of in which the elements

31
00:02:05,000 --> 00:02:10,000
were last accessed from the list recently accessed, the most recently accessed.

32
00:02:10,000 --> 00:02:13,000
You might be wondering when this can be used.

33
00:02:13,000 --> 00:02:18,000
I know that the things are better learned when you know that you can apply your knowledge and practice

34
00:02:19,000 --> 00:02:22,000
access order maybe come in handy when you want to implement cache.

35
00:02:23,000 --> 00:02:23,000
Probably.

36
00:02:24,000 --> 00:02:25,000
You heard those words the first time.

37
00:02:25,000 --> 00:02:27,000
Let me explain you what a cache is.

38
00:02:28,000 --> 00:02:35,000
Cash is a hardware or software component that stores data so that future requests for that data can

39
00:02:35,000 --> 00:02:36,000
be served faster.

40
00:02:36,000 --> 00:02:42,000
The data stored in the cache might be as a result of an earlier computation or a copy of data stored

41
00:02:42,000 --> 00:02:43,000
elsewhere.

42
00:02:43,000 --> 00:02:48,000
For example, you can always keep in cache information about products that attribute most of the times

43
00:02:49,000 --> 00:02:52,000
to save time on retrieving all information for product details.

44
00:02:52,000 --> 00:02:53,000
Page.

45
00:02:53,000 --> 00:02:59,000
We can just store these products in cash and retrieve them only when it is needed to be cost effective

46
00:02:59,000 --> 00:03:03,000
and to enable efficient use of data caches must be relatively small.

47
00:03:04,000 --> 00:03:09,000
That's why there are several content eviction policies that keep size of the cache fixed.

48
00:03:09,000 --> 00:03:12,000
Sometimes it is also called cache replacements.

49
00:03:12,000 --> 00:03:13,000
Algorithms.

50
00:03:14,000 --> 00:03:19,000
Once a cash flow algorithm should choose which items to discard to make room for the new ones.

51
00:03:20,000 --> 00:03:23,000
There really a lot of different election policies.

52
00:03:23,000 --> 00:03:27,000
Some of them are first in, first out, last in, first out.

53
00:03:28,000 --> 00:03:33,000
You already know what FCF oh, and LIFO means last recently used.

54
00:03:34,000 --> 00:03:38,000
According to the strategy, we discard elements that were not used for a long time.

55
00:03:38,000 --> 00:03:43,000
The logic that stands behind that is in the case element is not used.

56
00:03:43,000 --> 00:03:48,000
There is no science to keep it in cash and it is better to substitute it with a new element.

57
00:03:49,000 --> 00:03:56,000
And in case here is a good new element already in the element that counts as usage and element is moved

58
00:03:56,000 --> 00:04:00,000
on the new place in this data structure to not be removed.

59
00:04:01,000 --> 00:04:03,000
By the way, this is one of the most popular ones.

60
00:04:04,000 --> 00:04:10,000
You're going to have a homework to implement your own cache with the help of the hash map most recently

61
00:04:10,000 --> 00:04:11,000
used the eviction strategy.

62
00:04:12,000 --> 00:04:15,000
It works in the opposite way from least recently use cache.

63
00:04:15,000 --> 00:04:17,000
Among the other eviction strategies.

64
00:04:17,000 --> 00:04:24,000
It is also possible to mention random replacement, least frequently used, least frequently recently

65
00:04:24,000 --> 00:04:25,000
used, etc..

66
00:04:26,000 --> 00:04:31,000
So I believe now when you know what the cache is, you can imagine how we can use length hash laced

67
00:04:31,000 --> 00:04:32,000
to implement cache.

68
00:04:33,000 --> 00:04:39,000
The Access Order EnLink hash map allows us to implement LRU cache an easy way, but what else?

69
00:04:39,000 --> 00:04:42,000
We need to implement cache with the help of the cache map.

70
00:04:43,000 --> 00:04:49,000
We need to set the size of our cash and then cache map can help us to support fixed size of our cache.

71
00:04:50,000 --> 00:04:56,000
How not to get back to the source code in the source code of link Hashmat we can find Remove Alessandri

72
00:04:56,000 --> 00:04:57,000
remastered.

73
00:04:57,000 --> 00:05:03,000
This method is invoked by Puth and put all methods after incertain and you entry into the map.

74
00:05:03,000 --> 00:05:08,000
And in case this message returns through, that means maps should remove its earliest entry.

75
00:05:09,000 --> 00:05:12,000
You can see that it has protected access modifier.

76
00:05:12,000 --> 00:05:18,000
That means it is not available by default outside of this package and outside of this class and its

77
00:05:18,000 --> 00:05:19,000
child classes.

78
00:05:19,000 --> 00:05:25,000
The idea is, in case you have to implement cash, we have to override this method and implement the

79
00:05:25,000 --> 00:05:29,000
rule that would tell us when we have to remove the Elvis element.

80
00:05:29,000 --> 00:05:30,000
Does it make sense?

81
00:05:31,000 --> 00:05:35,000
And prepare, for example, to show you this, here is a class that extends length.

82
00:05:35,000 --> 00:05:42,000
Hashmat, I also declared filled with a name capacity that contains the value of max elements in the

83
00:05:42,000 --> 00:05:46,000
current map, how elements will be removed automatically.

84
00:05:46,000 --> 00:05:49,000
I will let little hash map to handle or remorse.

85
00:05:50,000 --> 00:05:56,000
What I have to do is to override or remove Alessandri and return true when elements should be removed

86
00:05:56,000 --> 00:05:56,000
from map.

87
00:05:57,000 --> 00:06:04,000
So when the size of map will become more than capacity, then we have to remove the our capacity by

88
00:06:04,000 --> 00:06:06,000
default is three elements.

89
00:06:06,000 --> 00:06:11,000
Now, let me create the object of the current class and add four entries here.

90
00:06:11,000 --> 00:06:14,000
By default, I insertion order.

91
00:06:14,000 --> 00:06:20,000
And that means that when I add force element, the first one should be removed here.

92
00:06:20,000 --> 00:06:21,000
Aberrant elements to cancel.

93
00:06:22,000 --> 00:06:25,000
Let me run the program to show you console output.

94
00:06:25,000 --> 00:06:28,000
And here we can see that the first entry is removed.

95
00:06:29,000 --> 00:06:35,000
Now you have enough information that will help you to implement your homework from the public interface

96
00:06:35,000 --> 00:06:36,000
that link Hashmat provides.

97
00:06:36,000 --> 00:06:43,000
There is no massive that present in this class and absent in hash map since this class extends Hashmat.

98
00:06:43,000 --> 00:06:48,000
That means all methods that were reviewed and Hashmat lesson and that were reviewed during the review

99
00:06:48,000 --> 00:06:53,000
of map interface are also available for objects of the hash map type.

100
00:06:53,000 --> 00:06:56,000
That's why we want to review those methods again.

101
00:06:57,000 --> 00:07:00,000
So that's all what I wanted to share with you regarding the hash map.

102
00:07:01,000 --> 00:07:06,000
Now let's recap what we have learned today in this lesson we reviewed and in fact, map class.

103
00:07:07,000 --> 00:07:11,000
We learned how law enforcement works and what are key features of this type.

104
00:07:11,000 --> 00:07:17,000
Now we know what the difference between insertion, order and access order is and how to change the

105
00:07:17,000 --> 00:07:18,000
smooth inline hash map.

106
00:07:19,000 --> 00:07:21,000
After that, we learned what a cache is.

107
00:07:22,000 --> 00:07:27,000
Now, you know, the theory of different election policies and you know that Lenfest map can be used

108
00:07:27,000 --> 00:07:28,000
to create LRU cache.

109
00:07:29,000 --> 00:07:34,000
Also, we learned how to override the method that would keep constant number of elements.

110
00:07:34,000 --> 00:07:35,000
EnLink hash map.

111
00:07:35,000 --> 00:07:37,000
Now I suggest reviewing your homework.

112
00:07:38,000 --> 00:07:43,000
You have to implement Alario Cash on the basis of little cash map here.

113
00:07:43,000 --> 00:07:46,000
I provided you with an interface that you have to implement.

114
00:07:46,000 --> 00:07:52,000
According to this task, you have to implement three methods yet that returns value by key on minus

115
00:07:52,000 --> 00:07:54,000
one in case the key is not found.

116
00:07:55,000 --> 00:08:01,000
Good method that should put key value pair of jeans or update the value for key if such already exists

117
00:08:02,000 --> 00:08:07,000
and set capacity method that sets maximum number of elements that can be stored in cash.

118
00:08:08,000 --> 00:08:12,000
Try to use knowledge that you gained in this lesson to implement this task.

119
00:08:12,000 --> 00:08:16,000
I also share my solution for this task in attachments to this lesson.

120
00:08:16,000 --> 00:08:19,000
After you're done, you can compare two solutions if you wish.

121
00:08:20,000 --> 00:08:21,000
That's all for today.

122
00:08:22,000 --> 00:08:23,000
Thanks a lot for your attention.

123
00:08:23,000 --> 00:08:25,000
See you in the next lesson.