linear probing our implementation of probehashmap classusing open addressing with linear probingis given in code fragments and in order to support deletionswe use technique described in section in which we place special marker in table location at which an item has been deletedso that we can distinguish between it and location that has always been empty in our implementationwe declare class-level attributeavailas sentinel (we use an instance of the built-in object class because we do not care about any behaviors of the sentineljust our ability to differentiate it from other objects the most challenging aspect of open addressing is to properly trace the series of probes when collisions occur during an insertion or search for an item to this endwe define nonpublic utilityfind slotthat searches for an item with key in "bucketj (that iswhere is the index returned by the hash function for key class probehashmap(hashmapbase) """hash map implemented with linear probing for collision resolution ""avail objectsentinal marks locations of previous deletions def is available(selfj) """return true if index is available in table "" return self table[jis none or self table[jis probehashmap avail def find slot(selfjk) """search for key in bucket at index return (successindextupledescribed as follows if match was foundsuccess is true and index denotes its location if no match foundsuccess is false and index denotes first available slot "" firstavail none while true if self is available( ) if firstavail is none firstavail mark this as first avail if self table[jis none return (falsefirstavailsearch has failed elif =self table[jkey return (truejfound match keep looking (cyclically ( len(self tablecode fragment concrete probehashmap class that uses linear probing for collision resolution (continued in code fragment