chap searching and the next four bytes ("bbbb"will be interpreted as the integer value , , , their sum is , , , (when treated as an unsigned integerif the table size is then the modulus function will cause this key to hash to slot in the table note that for any sufficiently long stringthe sum for the integer quantities will typically cause -bit integer to overflow (thus losing some of the high-order bitsbecause the resulting values are so large but this causes no problems when the goal is to compute hash function open hashing while the goal of hash function is to minimize collisionscollisions are normally unavoidable in practice thushashing implementations must include some form of collision resolution policy collision resolution techniques can be broken into two classesopen hashing (also called separate chainingand closed hashing (also called open addressing the difference between the two has to do with whether collisions are stored outside the table (open hashing)or whether collisions result in storing one of the records at another slot in the table (closed hashingopen hashing is treated in this sectionand closed hashing in section the simplest form of open hashing defines each slot in the hash table to be the head of linked list all records that hash to particular slot are placed on that slot' linked list figure illustrates hash table where each slot stores one record and link pointer to the rest of the list records within slot' list can be ordered in several waysby insertion orderby key value orderor by frequency-of-access order ordering the list by key value provides an advantage in the case of an unsuccessful searchbecause we know to stop searching the list once we encounter key that is greater than the one being searched for if records on the list are unordered or ordered by frequencythen an unsuccessful search will need to visit every record on the list given table of size storing recordsthe hash function will (ideallyspread the records evenly among the positions in the tableyielding on average / records for each list assuming that the table has more slots than there are records to be storedwe can hope that few slots will contain more than one record in the case where list is empty or has only one recorda search requires only one access to the list thusthe average cost for hashing should be th( howeverif clustering causes many records to hash to only few of the slotsthen the cost to yesit is confusing when "open hashingmeans the opposite of "open addressing,but unfortunatelythat is the way it is