on the other handwe are trying to insert keythen we can ignore any exclamation marks and fill the position once again this now does take care of all our problemsalthough if we do lot of deleting and insertingwe will end up with table which is bit of mess large number of exclamation marks means that we have to keep looking for long time to find particular entry despite the fact that the load factor may not be all that high this happens if deletion is frequent operation in such casesit may be better to re-fill new hash table again from scratchor use another implementation search complexity the complexity of open addressing with linear probing is rather difficult to computeso we will not attempt to present full account of it here if is once again the load factor of the tablethen successful search can be shown to take ( - comparisons on averagewhile an unsuccessful search takes approximately ( ( - ) for relatively small load factorsthis is quite impressiveand even for larger onesit is not bad thusthe hash table time complexity for search is again constanti ( clustering there is particular problem with linear probingnamely what is known as primary and secondary clustering consider what happens if we try to insert two keys that have the same result when the hash function is applied to them take the above example with hash table at the stage where we just inserted glahkg phl gcm gla ory if we next try to insert jfk we note that the hash function evaluates to once again so we keep checking the same locations we only just checked in order to insert gla this seems rather inefficient way of doing this this effect is known as primary clustering because the new key jfk will be inserted close to the previous key with the same primary positiongla it means that we get continuous 'blockof filled slotsand whenever we try to insert any key which is sent into the block by the hash functionwe will have to test all locations until we hit the end of the blockand then make such block even bigger by appending another entry at its end so these blocksor clusterskeep growingnot only if we hit the same primary location repeatedlybut also if we hit anything that is part of the same cluster the last effect is called secondary clustering note that searching for keys is also adversely affected by these clustering effects double hashing the obvious way to avoid the clustering problems of linear probing is to do something slightly more sophisticated than trying every position to the left until we find an empty one this is known as double hashing we apply secondary hash function to tell us how many slots to jump to look for an empty slot if key' primary position has been filled already like the primary hash functionthere are many possible choices of the secondary hash function in the above exampleone thing we could do is take the same number associated with the three-character codeand use the result of integer division by instead of the remainderas the secondary hash function howeverthe resulting value might be bigger than so to prevent the jump looping round back toor beyondthe starting pointwe first take