Implement a HashTable | Separate Chaining Collision Resolution Technique | Part 2 | Implementation
Aug 15, 2023
Implement a HashTable | Separate Chaining Collision Resolution Technique | Part 2 | Implementation
► ►Personal queries? - Follow me on LinkedIn - https://www.linkedin.com/in/dinesh-va … https://github.com/dinesh-varyani/ds- …https://www.youtube.com/user/hubbersp …https://www.youtube.com/playlist?list …http://www.hubberspot.com https://www.facebook.com/dinesh.varyani/ https://www.instagram.com/dinu.varyani/ Get complete free course on Data Structures and Algorithms at - • Data Structures and Algorithms in Jav… . https://www.youtube.com/user/hubbersp …https://play.google.com/store/apps/de …https://github.com/dinesh-varyani/ds- …http://www.hubberspot.com
Content
3.21 -> Hello everyone. So in our previous video we
discussed about initial implementation of
9 -> hash table. We saw the structure of hash
table. And we also saw that how it uses hash
16.02 -> nodes internally. Now in this video we'll
simply code for the internal structure of
21.48 -> hash table. And in upcoming videos, we will
see the different operations performed by
27.03 -> hash table and then we'll test it working in
the main method. So, here I have created one
32.85 -> classes hash table. Now, as we discussed,
hash table consists of few instance
39.03 -> variables, one is array of hash node, which
we term as buckets. And as it is using the
50.49 -> hash node class internally here we will
create another class hash node. And as we
63.09 -> already discussed, that this hash node class
will have three members
70.47 -> one would be our key. So this can be generate
type. The second member would be value. And
90 -> this can also be any gender type. So here,
for the demo purpose, I'm using the key as
99.99 -> integer and value as string.
102.15 -> And the third member would be the reference
to the next hash node. And it will have a
117.66 -> constructor which will take two things T
handle value, we will assign the key to this
140.19 -> dot key and value to distort value. So here
the hash table consists of an array of hash
152.76 -> node, which we call as buckets. It also has
our integer variable number of buckets, which
164.25 -> is also capacity. And it also has an integer
type size, which is nothing but number of key
177.54 -> value pairs, an edge table or number of hash
nodes in hash table. So basically, in a hash
197.58 -> table, the number of hash nodes represents
the size of the hash table. And here we will
203.46 -> provide a constructor to our hash table
class.
213.12 -> So when we will create an instance of hash
table, it will simply call the parameterised
221.46 -> constructor providing our default capacity.
So here we will create one more constructor
239.49 -> which will take a capacity. so here we can
provide a customized capacity by calling this
248.16 -> constructor. And if you call this
constructor, it will create a hash table with
253.83 -> a default capacity of 10. So here, what we'll
do is two number of buckets, we will assign
263.4 -> the capacity. And now number of bucket is
holding the capacity. So what we'll do, we
269.85 -> will create the RF hash node whose length
would be the value stored in the number of
283.44 -> buckets. So here when we will create the
instance of hash table, let's say with the
289.05 -> capacity we provide, so the number of buckets
will hold that capacity and the array of hash
295.62 -> node will be of size, which represents the
number of buckets Usually at the start, when
302.76 -> there are no hash notes in a hash table, the
size will be zero. So this is what happens
318.96 -> when we first initialize or create the
instance of hash table. Now here you can see
325.35 -> that this is an initial implementation of
hash table. So in a hash table, there are
330.3 -> many operations. So one of the operation is
that we want to know the size of the hash
338.91 -> table at how many key value pairs are there.
So we provide a method has size. And here, we
348.54 -> simply return the size. One more method we
provide is Boolean, we check whether the hash
359.13 -> table is empty or not. So we provide the
method as is empty. And here, if the size is
371.58 -> equal to zero, then we return true stating
that hash table is empty. And if sizes not
378.81 -> equal to zero, we are returning false. So
friends, in our upcoming video, we will look
384.72 -> into the primary operations of a hash table,
which is put, which basically put a key value
397.83 -> pair in a hash table. So the parameters are
key, and value. So this method basically
410.16 -> takes in a key value pair, and it simply puts
that key value pair in our hash table. So we
419.37 -> will discuss about this method in greater
detail in our upcoming videos. So this is one
423.93 -> of the primary operations the other operation
is get. So this method simply takes in a key
440.19 -> and returns the corresponding value
associated with it. So for timing, I'm simply
446.34 -> returning null to compile this method, so
here, whatever the key value pairs are stored
453.54 -> in hash table, so if we want to get any value
associated with a key, we simply pass key
460.44 -> here and we get its corresponding value. And
one more method is renew, where we pass the
472.32 -> key and that key value pair will be removed
and the value associated with that key will
479.64 -> be returned. So when we call get the key
value pair remains in the hash table, we only
486.75 -> get the value out of the hash table. But when
we do remove that key value pair is
492.66 -> completely removed from the hash table and
its corresponding values returned. So here
498.21 -> these are the three main operations which are
being performed by hash table. And all these
504.3 -> three methods have a time complexity of
often, which is the average time complexity
511.5 -> of a hash table.
513.93 -> So for and this was basically an initial
implementation of a hash table. In our
520.53 -> upcoming videos, we will see all this primary
operations in great detail. So for an in
529.44 -> case, if you find this information useful,
then please like this video, and if you're
534.9 -> new to my channel, then please subscribe to
my channel so that you never miss any update.
540.09 -> Thanks, have a nice day.
Source: https://www.youtube.com/watch?v=dIew1UascBo
