linear probing reduces the index by one to and finds an empty location in that positionso we put hkg there givinghkg phl gcm ory next we wish to insert glawith hash value but the location with that index is already filled by ory again linear probing reduces the index by oneand since that slot one to the left is freewe insert gla therehkg phl gcm gla ory then we have akland although we have not had the value beforethe corresponding location is filled by gla so we try the next index downbut that contains gcmso we continue to the next one at index which emptyso we put akl therehkg phl akl gcm gla ory we now continue in the same way with the remaining keyseventually reachingdca lax fra hkg phl akl gcm gla ory this looks quite convincing all the keys have been inserted in way that seems to make good use of the space we have reserved howeverwhat happens now if we wish to find particular keyit will no longer be good enough to simply apply the hash function to it and check there insteadwe will have to follow its possible insertion locations until we hit an empty onewhich tells us that the key we were looking for is not presentafter allbecause it would have been inserted there this is why every hash table that uses open addressing should have at least one empty slot at any timeand be declared full when only one empty location is left howeveras we shall seehash tables lose much of their speed advantage if they have high load factorso as matter of policymany more locations should be kept empty soto find the key aklwe would first check at index then at and where we are successful searching for jfkon the other handwe would start with its proper positiongiven by the hash function value so we would check indices in that order until we find an empty space which tells us that jfk isin factnot present at all this looks pretty bad at first sightbut bear in mind that we said that we will aim towards keeping the load factor at around percentso there would be many more empty slots which effectively stop any further search but this idea brings another problem with it suppose we now delete gcm from the table and then search for akl again we would find the array empty at index and stop searchingand therefore wrongly conclude that akl is not present this is clearly not acceptablebut equallywe do not wish to have to search through the entire array to be sure that an entry is not there the solution is that we reserve another key to mean that position is emptybut that it did hold key at some point let us assume that we use the character '!for that then after deleting gcmthe array would bedca lax fra hkg phl akl gla ory