Collision resolution.pptx

Collision resolution

1. Subject- Data Structures-I( CO203 ) Unit III- Collision Resolution Strtergies

2. Collision Resolution Strategies If the element to be inserted is mapped with the same location where an element is already inserted then collision occurs and it must be resolved. Open Hashing: Allows record to be stored in unlimited space(which can be a hard disk). It places no limitation in the size of tables. Records are partitioned into b buckets. Each bucket in the hash table is header of the linked list of records mapped to that buckets. e.g. separate chaining. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 2

3. Closed Hashing: uses fixed space for storage and thus limits the size of hash table. In this technique, hash table keeps the elements in the bucket itself.no. of records depends on the no. of slots in bucket. It involves open addressing techniques like Linear probing, Quadratic probing, Rehashing etc. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 3

4. Separate Chaining(Open Hashing): Separate list of all elements mapped to the same value is maintained. The idea is to make each bucket of hash table point to a linked list of records that have same hash function value. It is used when there is no limit on memory space. Let us consider a simple hash function as “ key mod 7 ” and sequence of keys as 50, 700, 76, 85, 92, 73, 101. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 4

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

6.  in practice the table size can be significantly large and the hash function can be even more complex, also the data being hashed would be more complex and non-primitive, but the idea remains the same. Advantages:   1) Simple to implement. We require a good hash function to guarantee even distribution of the values. 2) Hash table never fills up, we can always add more elements to the chain.  3) Less sensitive to the hash function or load factors.  4) It is mostly used when it is unknown how many and how frequently keys may be inserted or deleted.  DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 6

7. Disadvantages:   1) Cache performance of chaining is not good as keys are stored using a linked list. Open addressing provides better cache performance as everything is stored in the same table.  2) Wastage of Space (Some Parts of hash table are never used)  3) The lookups/inserts/updates can become linear [O(N)] instead of constant time [O(1)] if the hash function has too many collisions. 4) Uses extra space for links.  DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 7

8. Operations on Hash Table: 1.Initialize(): headers of all lists are set to NULL. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 8 #define MAX 10 struct node { int prn ; char name[10]; char name[10]; struct node *next; } node * ht [MAX]; void initialize() { int i; for(i=0;i< MAX;i ++) { ht [i]=NULL; }

9. Insert()- insert element at the end link list DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 9 void insert() { int addr,key,name ; node * ptr ,*temp; cout <<“enter student prn ”; cin >> prn ; cout <<“enter name”; cin >> name; temp=new node; temp-> prn = prn ; temp->name=name; addr =key % MAX; if( ht [ addr ]==NULL) { ht [ addr ]=temp; else { ptr = ht [ addr ]; while( ptr ->next!=NULL) { ptr = ptr ->next; } ptr ->next=temp; } }

10. e.g. 0,1,4,7,11,24,67,33,34,77,53 No. of bucket=10 DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 10 1 2 3 4 5 6 7 8 9 700 NULL e.g. 50,700,76,85,92,73,101 size of table is 7 50 85 92 NULL 73 101 NULL 76 NULL

11. Search() -> search an element in the hash table DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 11 node * search() { int addr,key ; cout <<“Enter the element to be search”; cin <<key; addr = key%MAX ; ptr = ht [ addr ] while( ptr !=NULL && key!= ptr ->data) { ptr = ptr ->next; } if(key== ptr ->data) { cout <<“Key Found”; return( ptr ); } return NULL; }

12. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 12 void display() { hash * ptr ; for(i=0;i< MAX;i ++) { ptr = ht [i]; while( ptr !=NULL) { cout << ptr -> prn <<“\t”<< ptr ->name<<“->”; ptr = ptr ->next; } } }

13. DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 13 Delete() { int addr ; node * ptr ,* prev ,*temp; cout <<“enter data to be deleted”; cin >>key; addr = key%MAX ; prev = ptr = ht [ addr ] ; if( ptr ->data==key) { prev = prev ->next; ht [ addr ]= prev ; delete( ptr ); } else { while( ptr ->data!=key && ptr ->next!=NULL) { prev = ptr ; ptr = ptr ->next; } if( ptr ->data==key) { prev ->next= ptr ->next; delete( ptr ); } }//end of else } //end of function

14. Time Complexity: Search= O(1+ α ) where α is loading factor Insert/Delete: O(1+ α ) DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 14