Hashing

[Hafsa Tariq]

I don't get the concept of collision. 

Is collision is number of keys mapped on same location ?   

if it is according to the above question : 

Total number of collision in linear probing= 0

Total number of collision in chaining = 2 (03,86 is mapped on index 3 ) & (19,337 is mapped on index 10 )

Correct if I'm wrong please. 

  

[Hafsa Tariq]

*correct me if I'm wrong 

--
You received this message because you are subscribed to the Google Groups "DSFAST2015" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dsfast2015+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/dsfast2015/2092c3e0-a83e-4670-903b-12a483c62d3d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Regards

Hafsa Tariq Javed

[Hassan Mirza]

in linear probing , we get collision at index 3 and at index 0. for 86 , whose mode is 3. we get collision because there is already 03 at index 3. so we add 1, according to rule of linear probing, and place 86 at index 4. similarly we got collision for 337 and place it at index 0 after implementing rule. At the end we get collision for 38 , at index zero. so we continuously adding 1, because all the coming indexes are full. so finally we reached at index 6, for 38.
 
On Sunday, June 7, 2015 at 1:44:23 PM UTC+5, Mehreen Saeed wrote:

Hafsa 

Total number of collisions would be the same in both cases. If a key is mapped to an index which is already occupied we have a collision. 

Mehreen

-------- Original message --------
From Hafsa Tariq <hafsata...@gmail.com>
Date: 07/06/2015 10:09 (GMT+05:00)
To dsfas...@googlegroups.com
Subject Re: Hashing

To view this discussion on the web visit https://groups.google.com/d/msgid/dsfast2015/CADaqFdFCDCqCNt8tMqdwyyMcOJEW1Z6PB_OVG%3DhBK_mccad9%2Bg%40mail.gmail.com.

[Saira Anwaar]

if a key is mapping on index which is already occupied then we have a collision...so while resolving that collision ...if again this type of situation happens (key is mapping to already occupied index ) then again those cases will be considered as collisions ?

[Hassan Mirza]

yes! again those cases will be considered as collision.An above example,we get collision for 38 , at index zero. so we continuously adding 1, because all the coming indexes are full. so finally we reached at index 6, for 38.

[Saira Anwaar]

No. of collisions during resolution of collision would be added to total number of collisions or not ?

[Saira Anwaar]

because mam is saying that number of collisions in both cases (linear and chaining) would be same but

No. of collisions (linear probing) = 8

and no. of collisions (chaining ) = 2 

[courses...@gmail.com]

Hafsa, sorry I did not see your example carefully.  The number of collisions in this example for chaining is two and for linear probing is 8.  Saira's answer is correct.  For linear probing count the number of entries that are already occupied so when inserting 38 there are 6 collisions, resulting in a total of 8 collisions. 

Hafsa, please confirm you understand this.

Mehreen

[Mehreen Saeed]

Hafsa and Saira

Please see my correction, yes for linear probing add one to the collision if the array is already occupied at that index. 

Mehreen

-------- Original message --------
From Hafsa Tariq <hafsata...@gmail.com>

Date: 07/06/2015 17:20 (GMT+05:00)
To Mehreen Saeed <courses...@gmail.com>
Subject Re: Hashing

Ma'am, Is Total number of collision = number of times each entry collide with any other entry ? 

 

[Saira Anwaar]

ok mam, i got it. Thank u :) 

[Saira Anwaar]

Mam in chaining, if a key is mapping to the index which is already occupied by TWO keys so will the collision will be considered as one ? because i think that collision doesn't depend upon the number of keys occupying a specific index... am i correct ?

On Sunday, 7 June 2015 18:35:56 UTC+5, Mehreen Saeed wrote: