closed hashing.pptx

Double Hashing

1. Subject- Data Structures-I( CO203 ) Unit III- Closed Hashing

2. Open Addressing/Closed Hashing: Separate chaining requires additional memory space for pointers. With this method, a hash collision is resolved by  probing , or searching through alternative locations in the array until an empty bucket is found. As all the elements are stored inside the table, a large memory space is needed for open addressing. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 2

3. There are three different popular methods for open addressing techniques. These methods are − Linear Probing Quadratic Probing Double Hashing DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 3

4. Linear Probing In this method, hash address of an identifier x is obtained If collision occurs, the identifier is place in the next empty slot after its home bucket If slot hash(x) % S is full, then we try (hash(x) + 1) % S If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 4

5. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 5

6. Table size=11 Hash function: h(x)= x mod 11 Insert keys:20,30,2,13,25,24,10,9 DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 6 h(20)= 20 % 11=9 h(30)= 30 % 11=8 h(2)= 2 % 11 =2 h(13)= 13 % 11=2 h(25)= 25 % 11=3 h(24)= 24 % 11=2 h(10)= 10 % 11=10 h(9)= 9 % 11=9 1 2 3 4 5 6 7 8 9 10 2 30 20 1 2 3 4 5 6 7 8 9 10 2 13 30 20 1 2 3 4 5 6 7 8 9 10 2 13 25 30 20 1 2 3 4 5 6 7 8 9 10 2 13 25 24 30 20 Insert 13 Insert 25 Insert 24 1 2 3 4 5 6 7 8 9 10 2 13 25 24 30 20 10 Insert 10 1 2 3 4 5 6 7 8 9 10 9 2 13 25 24 30 20 10 Insert 9

7. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 7 Let us see the following example to get better idea. If we have some elements like {15, 47, 23, 34, 85, 97, 65, 89, 70}. And our hash function is h(x) = x mod 7.

8. Advantages : Simple to implement. Best case time complexity=O(1) Disadvantages : If an element is not found at computed location. Searching goes in linear way. Hash table may become Full. Make clustering: many consecutive elements form groups. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 8

9. #define MAX 10 int insert_lb ( int key) { j=key % MAX; for(i=0;i < MAX ; i++) { if( ht [j]== -1) { ht [j]=key; DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 9 return(j); } j=(j+1)%MAX; } return(-1); } Procedure to insert key in hash table

10. Procedure to search key in hash table DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 10 int search_lb () { cout <<“Enter the key to be search”; cin >>key; j= key % MAX; for(i=0;i< MAX;i ++) { if( ht [j]==key) return(j); else j=(j+1)%MAX; } return -1; }

11. Linear Probing with Chaining In this method, another field get added into the table. In this field, the address of the colliding data can be stored with the first colliding element in the chain table, without replacement. Records can be easily located. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 11

12. For example , consider elements: 131, 3, 4, 21, 61, 6, 71, 8, 9  DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 12 1 2 3 4 5 6 7 8 9 -1 -1 131 -1 -1 -1 3 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 h(131)= 131%10=1 h(3)= 3%10=3 h(4)= 4%10=4 h(21)= 21%10=1 h(61)= 61%10=1 h(6)= 6%10=6 h(71)= 71%10=1 h(8)= 8%10=8 h(9)= 9%10=9 1 2 3 4 5 6 7 8 9 -1 -1 131 2 21 5 3 -1 4 -1 61 -1 -1 -1 -1 -1 -1 -1 -1 -1 Insert 21,61 1 2 3 4 5 6 7 8 9 -1 -1 131 2 21 5 3 -1 4 -1 61 -1 6 -1 -1 -1 -1 -1 -1 -1 Insert 6 1 2 3 4 5 6 7 8 9 -1 -1 131 2 21 5 3 -1 4 -1 61 7 6 -1 71 -1 -1 -1 -1 -1 Insert 71 1 2 3 4 5 6 7 8 9 -1 -1 131 2 21 5 3 -1 4 -1 61 7 6 -1 71 -1 8 -1 9 -1 Insert 8,9

13. From the example, you can see that the chain is maintained from the number who demands for location 1. First number 131 comes, we place it at index 1. Next comes 21, but collision occurs so by linear probing we will place 21 at index 2, and chain is maintained by writing 2 in chain table at index 1. Similarly next comes 61, by linear probing we can place 61 at index 5 and chain will maintained at index 2. Thus any element which gives hash key as 1 will be stored by linear probing at empty location but a chain is maintained so that  traversing the hash table will be efficient.   DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 13

14. Insert following keys into hash table with linear probing with chaining without replacement method. Use H(x)= x % 10 function 0,1,4,7,64,89,11,33,55 Use H(x)= x % 10 function 10,12,20,18,15 Use H(x)= x % 8 function 11,32,41,54,33,1 Use H(x)= x % 10 function DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 14

15. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 15 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9

16. Disadvantages: 1. Main purpose of hashing is not achieved, because all records are not mapped at correct position or mapped at wrong position/address. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 16

17. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 17 void insertwor ( int b[][2]) { int r,s,t,a ; printf ("\n Enter Data"); scanf ("% d",&a ); s= a % MAX; if(b[s][0]==-1) b[s][0]=a; else { while(1) { printf ("\ nTrue Collision Occurs"); getch (); if(b[s][1]== -1) { t=s; while(b[s][0]!=-1) { s=(s+1)%MAX; if(s==t) { printf ("Overflow"); break; } }

18. if(s!=t) { b[s][0]=a; b[t][1]=s; } break; } //if end else s=b[s][1]; }//while end }//else end } DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 18

19. void displaywor ( int b[][2]) { int i,r,s,t,a ; printf ("\ nINDEX \ tDATA \ tCHAIN "); for(i=0;i< max;i ++)  { if(b[i][0]!=-1) { printf ("\ n%d ",i); DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 19 printf ("\ t%d ",b[i][0]); //if(b[i][1]!=-1) printf ("\ t%d ",b[i][1]); } } getch (); }

20. void searchwor ( int b[][2]) { int r,s,a ; printf ("Enter Data Which U Want To Search"); scanf ("% d",&a ); s= a%MAX ; while(1) { if(b[s][0]==a) break; s=b[s][1]; DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 20 if(s==-1) { printf ("Not Found"); break; } }//end of while else { printf ("\ n Index Is % d:",s ); printf ("\ n Data Is % d:",b [s][0]); printf ("\n Index Which Is Chained From It :% d",b [s][1]); } }

21. Linear Probing with Replacement In this method, if another identifier ‘Y’ is occupying the position of an identifier ‘X’, X replaces it and then ‘Y’ is relocated to a new position. e.g. 11,32,41,54,33 First 3 will get placed at address 1,2,3,4. but when 33 need to be placed it position is occupied by 41. Therefore 33 replaces 41 and 41 inserted in new empty bucket i.e. 5 and chain from element 11 at position 1 is modified DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 21

22. 11,32,41,54,33,22 DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 22 1 2 3 4 5 6 7 8 9 -1 -1 11 3 32 -1 41 -1 54 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 4 5 6 7 8 9 -1 -1 11 5 32 -1 33 -1 54 -1 41 -1 -1 -1 -1 -1 -1 -1 -1 -1 Insert 33 1 2 3 4 5 6 7 8 9 -1 -1 11 5 32 6 33 -1 54 -1 41 -1 22 -1 -1 -1 -1 -1 -1 -1 Insert 22

23. Insert following data 12,1,4,3,7,8,10,2,5,14 using linear probing with chaining with replacement . Calculate average cost or no. of comparisons DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 23 1 2 3 4 5 6 7 8 9 10 -1 1 -1 12 6 3 -1 4 9 5 -1 2 -1 7 -1 8 -1 14 -1 Avg. Cost= (1+1+1+1+1+1+1+2+1+2)/no. of buckets =12/10 =1.2

24. Pseudo-code to insert Data in Linear probing with replacement DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 24

25. The load factor for an open addressing technique should be 0.5. For separate chaining technique, the load factor is 1. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 25