0

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.

Community
  • 1
  • 1
Sreeraj Chundayil
  • 5,548
  • 3
  • 29
  • 68
  • 2
    "depending upon the load factor of the methods" is perhaps the key idea. If you have a very sparse hashmap, you probably don't want to iterate over the entire thing just in order to fetch a key. However, if your map is stuffed with elements (load factor is in the 85-90-100% order), then the constant factor reduced by better cache locality can outweigh the theoretically smaller asymptotic complexity of the linked list lookup (which can be constant if the number of collisions is bounded). – The Paramagnetic Croissant Jun 06 '15 at 13:49
  • 1
    It also depends on the size of your keys. For example, a list pointer for chaining is an enormous overhead if all you're doing is storing a hash table of ints (64-bit pointer for 32-bit integrals, e.g.). It's a trivial overhead that often makes up for the lack of probing if you're storing keys that are a contiguous kilobyte each. Another thing is that these theoretical discussions often assume a linked list has no spatial locality. Very efficient ones are often back these by a contiguous allocator which gives back the spatial locality that one would normally lose with a linked structure. –  Jun 07 '15 at 11:32

1 Answers1

1

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

fcdt
  • 2,371
  • 5
  • 14
  • 26
Anirudha Kulkarni
  • 48
  • 7