CODEWITHSUNDEEP
calgorithmperformancedata-structureshashmap
Sreeraj Chundayil
Sreeraj Chundayil

Reputation: 5859

Linear Probing vs Chaining

In Algorithm Design Foundations,Analysis, and Internet Examples by Michael T. Goodrich ,Roberto Tamassia in section 2.5.5 Collision-Handling Schemes the last paragraph says

These open addressing schemes save some space over the separate chaining method, but they are not necessarily faster. In experimental and theoretical analysis, the chaining method is either competitive or faster than the other methods, depending upon the load factor of the methods.

But regarding the speed previous SO Answer says exact opposite.

Upvotes: 0

Views: 1904

Answers (1)

Anirudha Kulkarni
Anirudha Kulkarni

Reputation: 48

Linear probing wins when the load factor = n/m is smaller. That is when the number of elements is small compared to the slots. But exactly reverse happen when load factor tends to 1. The table become saturated and every time we have to travel nearly whole table resulting in exponential growth. On the other hand Chaining still grows linearly.

Linear probing vs chaining

Upvotes: 1

Related Questions