until reach ing the desired entry or an empty bucket (or returning back to where we started fromadditionallyour algorithm for put( ,vshould remember an available cell encountered during the search for ksince this is valid place to put new entry ( ,vthuslinear probing saves spacebut it complicates removals even with the use of the available marker objectlinear probing suffers from an additional disadvantage it tends to cluster the entries of the map into contiguous runswhich may even overlap (particularly if more than half of the cells in the hash table are occupiedsuch contiguous runs of occupied hash cells causes searches to slow down considerably quadratic probing another open addressing strategyknown as quadratic probinginvolves iteratively trying the buckets [( ( )mod ]for , , where ( = until finding an empty bucket as with linear probingthe quadratic probing strategy complicates the removal operationbut it does avoid the kinds of clustering patterns that occur with linear probing neverthelessit creates its own kind of clusteringcalled secondary clusteringwhere the set of filled array cells "bouncesaround the array in fixed pattern if is not chosen as primethen the quadratic probing strategy may not find an empty bucket in even if one exists in facteven if is primethis strategy may not find an empty slotif the bucket array is at least half fullwe explore the cause of this type of clustering in an exercise ( - double hashing another open addressing strategy that does not cause clustering of the kind pro duced by linear probing or the kind produced by quadratic probing is the double hashing strategy in this approachwe choose secondary hash functionh 'and if maps some key to bucket [ ]with ( )that is already occupiedthen we iteratively try the buckets [( ( )mod nnextfor , , where (jj '(kin this schemethe secondary hash function is not allowed to eval uate to zeroa common choice is '(kq ( mod )for some prime number alson should be prime moreoverwe should choose secondary hash function that will attempt to minimize clustering as much as possible these open addressing schemes save some space over the separate chaining methodbut they are not necessarily faster in experimental and theoretical anal ysesthe chaining method is either competitive or faster than the other methodsdepending on the load factor of the bucket array soif memory space is not major issuethe collision-handling method of choice seems to be separate chain ing stillif memory space is in short supplythen one of these open addressing methods might be worth implementingprovided our probing strategy minimizes the clustering that can occur from open addressing