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.