open addressing the separate chaining rule has many nice propertiessuch as affording simple implementations of map operationsbut it nevertheless has one slight disadvantageit requires the use of an auxiliary data structure-- list--to hold items with colliding keys if space is at premium (for exampleif we are writing program for small handheld device)then we can use the alternative approach of always storing each item directly in table slot this approach saves space because no auxiliary structures are employedbut it requires bit more complexity to deal with collisions there are several variants of this approachcollectively referred to as open addressing schemeswhich we discuss next open addressing requires that the load factor is always at most and that items are stored directly in the cells of the bucket array itself linear probing and its variants simple method for collision handling with open addressing is linear probing with this approachif we try to insert an item (kvinto bucket ajthat is already occupiedwhere ( )then we next try [ mod nif [ mod nis also occupiedthen we try [ mod ]and so onuntil we find an empty bucket that can accept the new item once this bucket is locatedwe simply insert the item there of coursethis collision resolution strategy requires that we change the implementation when searching for an existing key--the first step of all getitem setitem or delitem operations in particularto attempt to locate an item with key equal to kwe must examine consecutive slotsstarting from [ ( )]until we either find an item with that key or we find an empty bucket (see figure the name "linear probingcomes from the fact that accessing cell of the bucket array can be viewed as "probe must probe times before finding empty slot new element with key to be inserted figure insertion into hash table with integer keys using linear probing the hash function is (kk mod values associated with keys are not shown