Hashing | Set 3 (Open Addressing) | GeeksforGeeks
Hashing | Set 3 (Open Addressing) | GeeksforGeeks
Explanation for the article: http://quiz.geeksforgeeks.org/hashing…
This video is contributed by Illuminati.
Content
1.24 -> Hello friends!
2.24 -> And, welcome to GeeksforGeeks.
4.96 -> In this tutorial we are going to cover Open
Addressing, which is one of a collision resolving
12.169 -> technique in hashing.
15.849 -> Before we begin with this tutorial we would
strongly advise you to be aware of these following
23.01 -> terms.
24.01 -> We have covered all these topics in our previous
videos on hashing,so you may pause this one
32.8 -> and have a look at them first.
37.13 -> So lets begin with Open Addressing.
41.2 -> Open Addressing is a collision resolving technique
in hashing and the special thing about it
48.93 -> is that all the keys are stored in hash table
itself.
54.85 -> Here the size of table has to be greater than
or equal to the number of keys that need to
61.89 -> be hashed.
64.57 -> The hash function that we use specify an order
of slots to probe instead of giving just a
72.18 -> single slot.
74.75 -> Now we have few techniques of probing,they
are linear probing, quadratic probing and
84.09 -> double hashing.
85.439 -> We will see all of them in detail and we will
study them for the following operations.
95 -> The operations are insert, search and delete.
101.909 -> So lets start with Linear Probing.
105.03 -> In linear probing, we linearly probe for next
slot.The increment of slot after every try
114.619 -> is generally 1.
117.39 -> The basic function hi is some hash function
Hash(X) plus iteration sequence 'i' modulo
128.86 -> HashTableSize.
131.22 -> This will give the slot to probe.
134.16 -> As an example consider these,
First we calculate h0, if it is empty we insert
144.01 -> our key else if full we calculate h1.
154.31 -> h1 is again Hash(X) + 1 modulus HashTableSize,
this will in most cases give the immediate
162.07 -> next slot, if it is full we calculate h2 and
so on.
170.93 -> So far we have seen the mathematical aspect
of probing , lets also have some hands on
177.68 -> through an example.
179.24 -> Consider the following keys on which we need
to perform some operations using linear probing.
189.07 -> Lets also have our hash table.
193.03 -> Notice that our hash table has 11 slots which
is greater than our number of keys which are
202.85 -> 4.
203.89 -> Now for each slot we have defined 3 states,
a slot is either empty,as we can see here
213.52 -> initially
a slot can be occupied,
219.07 -> and a slot can have a deleted element.
223.98 -> These states are necessary for our search
operation as we will see ahead.
230.89 -> So lets start with inserting our keys.
235.02 -> h0 is 7 modulo 11 which is 7, we insert this
key on index 7.
245.74 -> Note how the color representing state of the
slot has changed to occupied.
252.97 -> Next we insert 36.Here h0 is 3, so we insert
the key at index 3.
262.949 -> Next we insert 18.We calculate h0 which comes
out to be 7.
272.259 -> Now collision occurs as our 7th index is already
taken, so what we do is we calculate h1.
283.4 -> h1 comes out to be 8, since index 8 is empty
we put key 18 there.
294.139 -> Next we insert 62, h0 is 7 which is occupied
so a case of collision.
304.08 -> We therefore calculate h1, which is 8 and
also occupied.
309.15 -> We then calculate h2, it comes out to be 9
, since 9 is empty we can put 62 there.
321.15 -> We are done with inserting keys and therefore
we can say that the basic idea is to keep
328.36 -> probing until an empty slot is found.
332.879 -> Once an empty slot is found, insert key there.
339.719 -> Now we see search operation.
341.91 -> Lets say we want to search key 18.
347.82 -> The idea for search is, keep probing until
slot’s key doesn’t become equal to key
355.199 -> being searched or an empty slot is reached.
360.099 -> We calculate h0, key at h0 is not equal to
18 and also the slot is not empty so we calculate
373.699 -> h1.
375.309 -> Key at h1 equals to 18 so we break as we have
found our element.
385.229 -> Next we see the delete operation.This operation
is interesting as if we simply delete a key,
394.949 -> then search may fail.
397.41 -> So if we have to delete key 18, its slot should
be marked as deleted and not empty.
406.099 -> So here we make a note that ,we can insert
a key at a slot with deleted state but our
414.15 -> search operation should not stop on this slot.
417.74 -> Next we move on to Quadratic Probing.
422.8 -> The basic difference is that here the increment
is quadratic, instead of i we have i^2.
433.259 -> Notice the increment is 0, 1 , 4, 9 and so
on.
440.509 -> Lets again see it with the same example.
445.389 -> We insert key 7, since h0 is empty we insert
it.
454.729 -> Next we insert 36 , h0 is 3 and index 3 is
empty so we insert it.
465.62 -> Next we insert 18, h0 is 7 and 7 is already
occupied.
474.87 -> Since a collision has occurred we calculate
h1.
479.309 -> h1 comes out to be 8, since it is empty we
insert 18 at index 8.
489.389 -> Next we insert 62.h0 is 7 which is occupied.
497.03 -> Since a collision has occurred we calculate
h1.
501.569 -> h1 is 8 which is again occupied, we therefore
calculate h2.
509.279 -> h2 comes out to be 0, since slot with index
0 is empty we insert 62 there.
520.289 -> With this we have inserted all the keys.
524.229 -> Next search and delete operations uses the
same idea as we have done in linear probing
532.529 -> so we skip them.
535.04 -> Lets see another technique which is also known
as Double Hashing.
540.97 -> In double hashing we use another hash function
and the general function is first hash function
550.28 -> plus i*second hash function modulo table size.
557.94 -> The only difference with previous methods
is that here we are using two hash functions
564.39 -> instead of one,
however the other idea for insert, search
571 -> and delete operation remains the same.
575.949 -> Now lets compare the three methods that we
have learn so far.
581.62 -> The first method was linear probing.
585.87 -> It is easy to implement,
has the best cache performance,
591.769 -> and suffers from clustering i.e many consecutive
elements form groups and it starts taking
600.36 -> time to find a free slot or to search an element.
605.97 -> The next method was quadratic probing.
609.69 -> It has average cache performance
and in this clustering also occurs in a very
618.46 -> less amount.
620.12 -> Last method was double hashing.
623.69 -> It has worst cache performance.
627.639 -> There is no clustering of keys in this method.
631.75 -> And it also involves more computation time.
637.399 -> Lets finally look at the complexity of Open
Addressing.
643.06 -> For this we define load factor alpha which
is n/m.
648.2 -> Here m are the number of slots in our hash
table and
654.17 -> n are the number of keys that need to be inserted
in our table.
660.319 -> So the worst case complexity comes out to
be O(1/(1 - α)),
666.85 -> which is basically an upper bound on the expected
number of trials required for a success.
675.98 -> With this, we come to an end of this tutorial.
680.949 -> If you have any doubts or suggestions please
leave them in the comment section below.
686.519 -> Thanks for watching!
Source: https://www.youtube.com/watch?v=Dk57JonwKNk