About secondary clustering in hash tables

Question

Although quadratic probing eliminates primary clustering, elements that hash to the same position will probe the same alternate cells. This is known as secondary clustering. Simulation results suggest that it generally causes less than an extra probe per search.

Above is text snippet from algorihms book from Mark Allen Wessis book.

My question can some one explain with example what is secondary clustring and what does author mean by "Simulation results suggest that it generally causes less than an extra probe per search".

Thanks!

Answer 1

Secondary clustering is defined in the piece of text you quoted: instead of near the insertion point, probes will cluster around other points.

"Simulation results suggest that it generally causes less than an extra probe per search" means someone tried to insert or find lots of data in a hash table with quadratic probing, and found that, on average, less than two probes were needed to find the right spot in the hash table. (One probe is of course the minimum needed to insert or find anything in a hash table.)