1 00:00:00,990 --> 00:00:02,100 Hi there. 2 00:00:02,280 --> 00:00:09,360 Now let's look at link has said that is another set implementation as the name linked has set implies 3 00:00:09,470 --> 00:00:09,720 . 4 00:00:09,840 --> 00:00:17,800 It uses a hash table as well as a linked list in its implementation of the set interface which has set 5 00:00:17,930 --> 00:00:25,200 below that element insertion order is not because of how alert linked has it has a doubly linked list 6 00:00:25,290 --> 00:00:32,250 running through its elements which helps in preserving the order off in certain elements but that doesn't 7 00:00:32,250 --> 00:00:33,530 mean that it is slow. 8 00:00:33,690 --> 00:00:40,440 It extends has set on it has almost asfast us hash Hachette sleights known as would be due to the expense 9 00:00:40,440 --> 00:00:43,540 of maintaining a linked list. 10 00:00:43,560 --> 00:00:50,400 So just like has said look up insertion and deletion operations are supported in constant time not on 11 00:00:50,400 --> 00:00:57,780 like a house set linked has set permits only one element unintentionally It uses a linked hash map which 12 00:00:57,780 --> 00:00:59,180 we will look at later. 13 00:00:59,220 --> 00:01:05,910 Recall that set uses hash map internally and this one uses a linked Hashima on preset which we will 14 00:01:05,910 --> 00:01:08,530 discuss later uses a tree mapping identity. 15 00:01:08,970 --> 00:01:14,070 So all these implementations internally use corresponding map implementations. 16 00:01:14,070 --> 00:01:20,010 Let's actually take a quick look at the sourcecode to see how linked Hassett instantiates a linked hash 17 00:01:20,010 --> 00:01:21,700 map. 18 00:01:23,040 --> 00:01:25,980 OK here we are in the grip code Web site and this is the link. 19 00:01:25,990 --> 00:01:31,420 Has a class on this is the constructor and it is in the super constructor. 20 00:01:31,530 --> 00:01:35,820 So it is invoking the constructor in the superclass which is the Hasson. 21 00:01:36,270 --> 00:01:39,800 OK so let's look at that particular constructor under just passing three values. 22 00:01:39,800 --> 00:01:41,290 One is the capacity. 23 00:01:41,370 --> 00:01:45,190 The second one is the load factor and the third one has some boolean value. 24 00:01:45,480 --> 00:01:47,270 So let's go into hierarchy here. 25 00:01:47,580 --> 00:01:54,310 Let's click on has said OK this is a high set and it's going to outline. 26 00:01:54,810 --> 00:02:00,900 And this is the constructor so there are multiple overloaded constructors and this one with the three 27 00:02:00,900 --> 00:02:02,960 parameters is the one that is invoked. 28 00:02:03,090 --> 00:02:06,370 Kremlin has seen on here it is. 29 00:02:06,420 --> 00:02:11,480 So the first parameter is capacity second is load factor and third the caller does dummy. 30 00:02:11,490 --> 00:02:15,130 So it is used only do under load the constructor. 31 00:02:15,180 --> 00:02:19,040 OK so if it is not used then we have two identical constructors. 32 00:02:19,380 --> 00:02:22,260 So it's only use for the sake of overloading. 33 00:02:22,320 --> 00:02:24,030 You can construct it already. 34 00:02:24,030 --> 00:02:27,210 And here we are invoking the linked hash map. 35 00:02:27,280 --> 00:02:33,600 OK we are instantiating encash map on passing initial capacity unload factor and dummy variable is simply 36 00:02:33,690 --> 00:02:34,610 ignored. 37 00:02:35,010 --> 00:02:40,220 Now let's head back to the sleights we already discuss these. 38 00:02:40,230 --> 00:02:44,110 These are the typical use cases we would want to use a linked headset. 39 00:02:44,250 --> 00:02:50,900 If we want first look up insertion and deletion but that insertion order Pozzo. 40 00:02:51,050 --> 00:02:51,650 OK. 41 00:02:51,960 --> 00:02:58,640 Finally similar to a headset link has set is also better than our eldest If remove all are written. 42 00:02:58,650 --> 00:03:05,940 All operations are will be used frequently now although some of the operations Silverlink hasard can 43 00:03:05,940 --> 00:03:13,110 be slightly slower than Hassid linked has it can be slightly faster when it comes to iterating the elements 44 00:03:13,110 --> 00:03:14,130 . 45 00:03:14,450 --> 00:03:20,730 And that's because it addition with the link has set is dependent on the size of the SEC due to the 46 00:03:20,730 --> 00:03:22,710 use of doubling. 47 00:03:23,220 --> 00:03:27,850 Whereas in the case of Hasek's it duration is dependent on the capacity. 48 00:03:27,850 --> 00:03:34,530 Now if you recall capacity is nothing but the number of buckets in the hash table that is a odysseys 49 00:03:35,010 --> 00:03:41,910 as we know that has table in Donelly users on our IT has set the actual number of elements would be 50 00:03:41,910 --> 00:03:43,760 less than the capacity. 51 00:03:43,980 --> 00:03:50,700 But it still depends on the capacity and length has it duration has nothing to do with that capacity 52 00:03:51,240 --> 00:03:57,890 but with only the number of actual elements due to the usage off doubly linked list. 53 00:03:58,160 --> 00:04:06,930 Now in under a minute let's do a quick demo of linked has set a new method called Link Hassidim all 54 00:04:07,020 --> 00:04:15,420 has been added with a set class and here all we are doing as fast we are instantiating it has set and 55 00:04:15,420 --> 00:04:16,930 we are adding these three elements. 56 00:04:16,980 --> 00:04:18,970 So the has set has strengths. 57 00:04:19,050 --> 00:04:20,960 So we are adding these three elements at large. 58 00:04:20,970 --> 00:04:24,480 John and Anita and simply we are printing the Hasson. 59 00:04:24,750 --> 00:04:25,020 OK. 60 00:04:25,020 --> 00:04:26,380 So these are three elements. 61 00:04:26,730 --> 00:04:29,340 And then we are creating a lint has set here. 62 00:04:29,600 --> 00:04:30,310 OK. 63 00:04:30,330 --> 00:04:34,570 And we are simply adding the same elements on we are printing the length Hasen. 64 00:04:34,920 --> 00:04:36,560 So let's just go ahead and run it. 65 00:04:36,570 --> 00:04:40,670 And so we can see the difference between the two sets. 66 00:04:40,680 --> 00:04:47,500 Now he has said is printing John-Roger non-adult although the order of arding is large. 67 00:04:47,520 --> 00:04:49,410 John I and Anita. 68 00:04:49,450 --> 00:04:56,160 OK so the order is not preserved as we know in a has set but when it comes to link has set the order 69 00:04:56,160 --> 00:04:56,800 is preserved. 70 00:04:56,880 --> 00:05:03,190 You can see that Roger John and Anita are being displayed in the same order as Douban in-circuit. 71 00:05:03,450 --> 00:05:09,600 So that's that one did you have it linked has you got the benefits of Hosack but at the same time you 72 00:05:09,600 --> 00:05:12,470 also have the insertion order preserved. 73 00:05:12,780 --> 00:05:15,670 OK so it is just slightly smaller than ḥasan. 74 00:05:16,110 --> 00:05:18,710 So that's about it that's about Lane has. 75 00:05:18,870 --> 00:05:19,620 Thank you. 76 00:05:19,680 --> 00:05:21,270 See you in the next lesson.