to implement deletionwe cannot simply remove found item from its slot in the array for exampleafter the insertion of key portrayed in figure if the item with key were trivially deleteda subsequent search for would fail because that search would start by probing at index then index and then index at which an empty cell is found typical way to get around this difficulty is to replace deleted item with special "availablemarker object with this special marker possibly occupying spaces in our hash tablewe modify our search algorithm so that the search for key will skip over cells containing the available marker and continue probing until reaching the desired item or an empty bucket (or returning back to where we started fromadditionallyour algorithm for setitem should remember an available cell encountered during the search for ksince this is valid place to put new item (kv)if no existing item is found although use of an open addressing scheme can save spacelinear probing suffers from an additional disadvantage it tends to cluster the items of 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 cause searches to slow down considerably another open addressing strategyknown as quadratic probingiteratively tries the buckets [( (kf ( )mod ]for where (ii 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 still has non-uniform patterneven if we assume that the original hash codes are distributed uniformly when is prime and the bucket array is less than half fullthe quadratic probing strategy is guaranteed to find an empty slot howeverthis guarantee is not valid once the table becomes at least half fullor if is not chosen as prime numberwe explore the cause of this type of clustering in an exercise ( - an open addressing strategy that does not cause clustering of the kind produced 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 [ ( )that is already occupiedthen we iteratively try the buckets [( (kf ( )mod nnextfor where (ii (kin this schemethe secondary hash function is not allowed to evaluate to zeroa common choice is (kq ( mod )for some prime number alson should be prime another approach to avoid clustering with open addressing is to iteratively try buckets [( (kf ( )mod nwhere (iis based on pseudo-random number generatorproviding repeatablebut somewhat arbitrarysequence of subsequent probes that depends upon bits of the original hash code this is the approach currently used by python' dictionary class