How does quadratic probing work

How could we qualify one algorithm is better than another? Primary concern could be the growth of runtime as input set becomes larger. The runtime can be dependent on compari- sons made, number of statements executed and varying im- plementations on different machines. Some programs or algorithms perform just fine with a small set of data to be processed. But they may perform very poorly with a large data set. Here we are focusing on the rate of growth of required computations as the quantity of data grows.

Hash function is expected to be independent of the size of the table, but as collision is inevitable, that property is rarely achieved. As we have seen, the efficiency of linear probing reduces drastically as the collision increases.

Because of the problem of primary clustering, clearly, there are tradeoffs be- tween memory efficiency and speed of access. Quadratic probing reduces the effect of clustering, but intro- duces another problem of secondary clustering. While prima- ry and secondary clustering affects the efficiency of linear and quadratic probing, clustering is completely avoided with dou- At best case, each of the technique works at O 1.

But this is only achieved when there is no collision. But as collision oc- curs, linear probing tends to be less efficient so is quadratic probing and double hashing. Hashing is a search method used when sorting is not needed and when access time is of essence. Though Hashing is an effi- cient method of searching and insertion, there is always time- space trade off.

When memory is not limited, a key can be used as a memory address, in that case, access time will be reduced. And when there is no time limitation, we can use sequential search, so there is no need of using a key as a memory address, thus, memory is minimized. Hashing — gives a balance between these two extremes — a way to use a reasonable amount of both memory and time. The choice of a hash function depends on: 1.

The nature of keys and the 2. The distribution of the numbers corresponding to the keys. However, this is not the case with quadratic probing unless you take care in the choosing of the table size. For example consider what would happen in the following situation:. In order to guarantee that your quadratic probes will hit every single available spots eventually, your table size must meet these requirements:.

Double Hashing is works on a similar idea to linear and quadratic probing. Use a big table and hash into it. Whenever a collision occurs, choose another spot in table to put the value. The difference here is that instead of choosing next opening, a second hash function is used to determine the location of the next spot.

The probe sequence for k 2 is 29, then 30, then 33, then Thus, while k 2 will probe to k 1 's home position as its second choice, the two keys' probe sequences diverge immediately thereafter. Try inserting numbers for yourself, and demonstrate how the probe sequences for diverge by inserting these numbers into a table of size 0, 16, 32, 15, Unfortunately, quadratic probing has the disadvantage that typically not all hash table slots will be on the probe sequence.

For many hash table sizes, this probe function will cycle through a relatively small number of slots. If all slots on that cycle happen to be full, this means that the record cannot be inserted at all! For example, if our hash table has three slots, then records that hash to slot 0 can probe only to slots 0 and 1 that is, the probe sequence will never visit slot 2 in the table.

Thus, if slots 0 and 1 are full, then the record cannot be inserted even though the table is not full! A more realistic example is a table with slots.