collision-handling schemes the main idea of hash table is to take bucket arrayaand hash functionhand use them to implement map by storing each item (kvin the "bucketa[ ( )this simple idea is challengedhoweverwhen we have two distinct keysk and such that ( ( the existence of such collisions prevents us from simply inserting new item (kvdirectly into the bucket [ ( )it also complicates our procedure for performing insertionsearchand deletion operations separate chaining simple and efficient way for dealing with collisions is to have each bucket ajstore its own secondary containerholding items (kvsuch that (kj natural choice for the secondary container is small map instance implemented using listas described in section this collision resolution rule is known as separate chainingand is illustrated in figure figure hash table of size storing items with integer keyswith collisions resolved by separate chaining the compression function is (kk mod for simplicitywe do not show the values associated with the keys in the worst caseoperations on an individual bucket take time proportional to the size of the bucket assuming we use good hash function to index the items of our map in bucket array of capacity nthe expected size of bucket is / thereforeif given good hash functionthe core map operations run in on/ the ratio /ncalled the load factor of the hash tableshould be bounded by small constantpreferably below as long as is ( )the core operations on the hash table run in ( expected time