hash tables quadratic probing we've seen that clusters can occur in the linear probe approach to open addressing once cluster formsit tends to grow larger items that hash to any value in the range of the cluster will step along and insert themselves at the end of the clusterthus making it even bigger the bigger the cluster getsthe faster it grows it' like the crowd that gathers when someone faints at the shopping mall the first arrivals come because they saw the victim falllater arrivals gather because they wondered what everyone else was looking at the larger the crowd growsthe more people are attracted to it the ratio of the number of items in table to the table' size is called the load factor table with , cells and , items has load factor of / loadfactor nitems arraysizeclusters can form even when the load factor isn' high parts of the hash table may consist of big clusterswhile others are sparsely inhabited clusters reduce performance quadratic probing is an attempt to keep clusters from forming the idea is to probe more widely separated cellsinstead of those adjacent to the primary hash site the step is the square of the step number in linear probeif the primary hash index is xsubsequent probes go to + + + and so on in quadratic probingprobes go to + + + + + and so on the distance from the initial probe is the square of the step numberx+ + + + + and so on figure shows some quadratic probes it' as if quadratic probe became increasingly desperate as its search lengthened at first it calmly picks the adjacent cell if that' occupiedit thinks it may be in small clusterso it tries something cells away if that' occupiedit becomes little concernedthinking it may be in larger clusterand tries cells away if that' occupiedit feels the first tinges of panic and jumps cells away pretty soonit' flying hysterically all over the placeas you can see if you try searching with the hashdouble workshop applet when the table is almost full the hashdouble applet with quadratic probes the hashdouble workshop applet allows two different kinds of collision handlingquadratic probes and double hashing (we'll look at double hashing in the next section this applet generates display much like that of the hash workshop appletexcept that it includes radio buttons to select quadratic probing or double hashing