CODEWITHSUNDEEP
hashtablecollision
Frank Palmasani
Frank Palmasani

Reputation: 185

I am creating a Hash Table that uses nodes to chain. What is a collision?

I can't seem to get an answer that I understand. What is a collision when you have a hash table that uses linked nodes?

Is the collision +1 for every index that you must pass to get to the index needed for that node you are adding?

I know that collisions are unavoidable, I have learned that much through my research but I haven't been able to figure out what constitutes a collision when dealing with a hash table that has linked nodes.

My program after finding its proper place in the array (array of pointers to nodes), sticks the new node at the front. Each element points at a node that points at another node, I have essentially multiple linked lists. So, does the collision count only include the first node of the element where the new node belongs because I stick it at the front, or does it include every single node in the linked list for that element.

for example, if the name "Smith" goes to the element [5], which also has 5 other nodes that are linked together, and I add it to the front, how would I decide what the collision count is?

Thanks for any help!

Upvotes: 0

Views: 145

Answers (1)

n0p
n0p

Reputation: 3496

A collision is when 2 distinct entries produces the same output through the Hash function.

Say your (poorly designed) hash function H consists in adding all the digits of a number:

5312 -> 5 + 3 + 1 + 2 = 11
1220 -> 1 + 2 + 2 + 0 = 5

So H(5312) = 11 and H(1220) = 5

H has a lot of collisions (this is why you should not use it):

H(4412) = 4 + 4 + 1 + 2 = 11
H(9200) = 9 + 2 + 0 + 0 = 11
etc...

Upvotes: 1

Related Questions