Know that you understand how a hash table works it's time for us to learn about Hasek. 2
But before doing that. 3
Let's briefly look at the set interface that has set implements. 4
We know the tech interface extends the collection interface and it models a mathematical set which means 5
up unlike a list a set can not how duplicate is due to this. 6
It is useful when uniqueness matters are also fast lookups matter. 7
We only discussed about how a hash table helps that Fosler cups on Hassid is based on Hostin as it internally 8
uses hash map he called up the list interface element position wasn't was the idea that is insertion 9
order is important but with set insertion order does not matter. 10
But what matters is fast lookups and uniqueness sockets it is a subway interface offset and it can additionally 11
be useful for sorting the elements. 12
So in addition to uniqueness on fossil lookups sort set will also help with sorting the elements unlike 13
list set interface does not add any new methods on top of what it inherits from the collection interface 14
. 15
However due to the fact that it does not allow duplicate it just places additional requirements on some 16
of the inherited methods and also the constructors for example for the I don't admit that it explicitly 17
states that duplicates are not allowed. 18
Now let's look at Hasek as the name implies it is a hash table based implementation of a second duffus 19
an alley. 20
It uses a hash map which stores key value based hash map will be discussed later. 21
But since Hachette starts on the individual objects those objects will be stored Eskies while an empty 22
object will be stored as a value not an empty object. 23
It is actually an instance of the object class. 24
If you're interested you can decode the source code of the augmented in-house set. 25
It also allows one non-value on here or its typical use cases. 26
It is useful when the need is rapid lookup rapid insertion and rapid deletion. 27
And we already know this from our discussion on hash table incisional that should not matter too. 28
If we want to use Hachigian finally does better than our IList If remove all or retain all operations 29
are to be used frequently. 30
If you recall our discussion from idlest Lawson they said that agreement on what it did it through each 31
element of the collection would remove those elements that are present in the input collection an index 32
of idlest each the more operation has a linear time complexity Gudu element. 33
Yes but with Hasek each animal would be constant. 34
So it is better than idlest not to look at a demo or has set OK for this demo. 35
I have created this new class called us said demo and it is added to the collections package. 36
And this class has this method called us Hassidim. 37
So we are going to defend this method and this particular Demel on some code has already been created 38
here. 39
So we will also extend that so fast let's create a set of strings so it will be set of string. 40
So let's also import a set on how Shekh let's just do can go shuffle. 41
So always remember to program to an interface. 42
Ok we already discussed that. 43
And one of the effective delite terms also to come unstuck. 44
OK. 45
So that way if you program to an interface you can always change the implementation. 46
Now let's go ahead and add a couple of strings to this 47
. 48
So it's going to be a B. 49
And let's also add another string quite a non that's run this. 50
So we're simply spending the set one and it is only printing A and B. 51
So the second is not getting at it because it's a duplicate. 52
And we know that Hassid does not allow duplicate. 53
So that's why it has set of strings non It's creator has set off this custom plus called book. 54
OK so book is defined at the bottom here and it has three feet slightly altered on either on that are 55
also getters and setters for that. 56
And there is also a constructor which will take the same fuse as the input parameter. 57
And here in this class we are creating two instances of the book and we are passing the same arguments 58
for the for the book name for the author and also the ear. 59
It is basically the year publication. 60
So we have two books here and we are creating this new Haslet instance and we're adding the books to 61
this. 62
And we're simply printing it. 63
So if Iran does so here it is. 64
But this is not readable because it is printing the object references so. 65
I'd like to string method here in the book. 66
It's going to source said Jondrette to string on let's use all of the fields here. 67
So here if you go down. 68
So here had a two string mattered. 69
Now let me run it now as you can see it has printing both the books and the corresponding three rallies 70
. 71
But here we have a duplicate here. 72
So here. 73
But the objects are logically equal. 74
OK. 75
So has said Normally we use it only for only if we want uniqueness. 76
So if we want if we do not want the second element to be added because it is a duplicate because it 77
is logically equal then in that case we need to do more. 78
So right now we know that has set is based on hash map and don't only uses map on hash map and then 79
it is based on hash hash table and promote hash table discussion we know that it uses the hash code 80
it uses it has a hash function on the hash function uses the hash code mattered in order to in order 81
to hash into the hash table right. 82
In order to find the correct bucket number. 83
Now in this case if the second element is a duplicate then it needs to have the same hash quarter as 84
a hostile limit. 85
But in this case both of these objects then have different hash scorched because the hash code method 86
is defined in the Object class so when Hatchard invokes the hash code method on Book 1 and Book to both 87
of them will be different because the hash code motard typically the way it is implemented is it and 88
some memory address or off the corresponding object after converting it into an int representation. 89
OK so both of them are actually two different objects. 90
So both of them have two different memory addresses and because of that. 91
So we get different values but it is written by the hash called method and that has matter is in the 92
Object class. 93
So what we need to do is we need to override it so that hardboard these instances we get the same value 94
same value is written so that we should really not add the second second block. 95
So let's do that. 96
Let's go ahead and override the hash code matter. 97
So here is the public record and so on. 98
And it's a hash. 99
Or let's say that I do the same. 100
Very tender. 101
I mean let's let's just use data to identify the duplicate. 102
So in this case a hash could really use that title will invoke the Hoshko matter on Titan. 103
So far since but since the titles of the books or seen this this particular statement in rockish and 104
rendered on the same hash good for both the invocations. 105
OK so now we're on it. 106
But then the second book is still getting entered. 107
The reason for that is because we have all read under the hash code mattered. 108
So both of them have the same hash cord and they get to the same bucket. 109
But what happens is this particular book the book one has been added to the linked list in the linked 110
list. 111
Now the second book also get has to the same bucket then but hash table will try to check if this is 112
actually equal to that and for that equals method is used. 113
We have the equal muttered in the Object class. 114
It is defined there. 115
So that needs to be overridden also. 116
So if it is not overridden so has table will actually be using the equals method from the Object class 117
on Dodik was murdered by the by default. 118
Well Paul Hoffman equality operation. 119
So when we when it does an equality operation it compares the object references. 120
OK. 121
An object offenses are obviously different because they're both are two different objects. 122
So we need to also override the equals matter and that is already done here. 123
So let me just uncommon this but the equals method for the Hoshko we are using title for the equals 124
just for this example we can use either an author. 125
So let me run it now. 126
Now you can see that the second book is not it. 127
OK. 128
So what needs to do what needs to be done is the hash code matter needs to be overridden and also the 129
equals method has to be overridden. 130
Because a hash board they get mapped to the same hash but the second object will also be mapped at the 131
same bucket when Hastert performs the equals operation. 132
It compares it with the book one and both of them have the same ear and the same author. 133
So it would read on a true and because of got it it's not going to read the second book. 134
Now even in the first example here when we were using strings so the string also here string is also 135
an object but string also has you know if you look at the source code you will see that it has already 136
been bought hash called method as well as the second method which is the equals method. 137
So because of that it did not add the second the second the duplicate. 138
So this is what we have. 139
And that's actually common this odd bit of this because they can be auto generated. 140
So if you're going to source here and here it is generated hash code unequals and it is asking if you 141
need to use all entry fees or. 142
But all three fees for both ultimate's. 143
So here you can see that this is the hash code metadata that has been auto generated and this is the 144
equals method. 145
So these are very different from what we have written earlier. 146
So the Hoshko method is using some some interior some int variables also. 147
So this is based on the best practice. 148
So what we need and what we know it was very very basic Hoshko method but this is like based on some 149
best practices. 150
So this is actually a research area itself. 151
HALPERT behind the hash. 152
Hash functions. 153
So so mathematicians on Twitter dical computer scientists work on that. 154
So this is how it is. 155
So eclipse is using the best practice. 156
In fact next we are going to briefly discuss an item from authoritative Java and it also discusses about 157
this exact same kind of formula and it is. 158
It is already implemented by eclipse so it is very important to use a good hash code matter. 159
And in the item that we are going to discuss it seems the String class used a bad hash code method prior 160
to Jalapa and because of that it gave lot of issues. 161
When lot of strings were added to hash tables. 162
Ok so it is very important to use a good hash function and this is a good hash function which is Auto 163
generator. 164
The target is now let's head back to the slide and let's just look at the item there. 165
And here is Item 9 from Effective Java which is all this. 166
All right Hoshko matter. 167
When you override equals and this happens to be a common in w question. 168
So if you want to treat two different objects as logically equal you must go right but equals on Hoshko 169
methods. 170
This or that or writing only Haskell method was not helpful in preventing that duplicate from getting 171
added. 172
Similarly if only equals was overridden but not caused matter. 173
Then it is very likely that the duplicate object will be stored in a completely different bucket. 174
In fact the contract of Hoshko method explicitly states that if two objects are equal according to their 175
equal Medek then calling the corresponding hash code methods must also produce the same injuries. 176
Let's actually review this in the Hoshko that's contract. 177
OK here is a Hoshko method from the object class. 178
And here is what we discussed earlier. 179
You can also read it later. 180
It's as if two objects are equal. 181
According to the equals method. 182
Then calling the hash code method on each of the two objects must produce the same integer result. 183
OK so that's what the effective delite also says and it also says that if two objects are unequal according 184
to the equals method then the Hoshko method can still produce the same and degenerate business. 185
OK that's what this particular statement that Turquand says. 186
OK so if the objects are not equal then the houseboat can still produce the same integer reasons. 187
However this last statement recommends that for unequal objects it says it is better for the hash court 188
method to produce distinct integer results so that rate would improve the performance of hash tables 189
. 190
So that is what is recommended but there is no requirement that it has to be like that. 191
The hash quote motard candidate and the same value even for unequal objects. 192
So there is no requirement from the Java language specification. 193
It is dependent on the Java language implementation but typically they the hash code method uses the 194
memory address so the objects are equal. 195
Obviously it would read under different hash Goertz indistinct Oshkosh on that as how that is the good 196
way to implement but it is not required from the language of the specification. 197
So that's about it. 198
So we looked at Hasek and it is useful when uniqueness on Fosco cups matter but not in social order 199
. 200
Now if you want to insert objects of your own class and if you want to maintain uniqueness and logically 201
equal objects then make sure to override both hash code as well as Eclipse method. 202
Thank you