hashing large number of deletions in separate chaining hash table can cause the table to be fairly emptywhich wastes space in this casewe can rehash to table half as large assume that we rehash to larger table when there are twice as many elements as the table size how empty should the table be before we rehash to smaller tablereimplement separate chaining hash tables using vector of singly linked lists instead of vectors the isempty routine for quadratic probing has not been written can you implement it by returning the expression currentsize== in the quadratic probing hash tablesuppose that instead of inserting new item into the location suggested by findposwe insert it into the first inactive cell on the search path (thusit is possible to reclaim cell that is marked deletedpotentially saving spacea rewrite the insertion algorithm to use this observation do this by having findpos maintainwith an additional variablethe location of the first inactive cell it encounters explain the circumstances under which the revised algorithm is faster than the original algorithm can it be slowersuppose instead of quadratic probingwe use "cubic probing"here the ith probe is at hash(xi does cubic probing improve on quadratic probingusing standard dictionaryand table size that approximates load factor of compare the number of collisions produced by the hash function in figure and the hash function in figure what are the advantages and disadvantages of the various collision resolution strategies suppose that to mitigate the effects of secondary clustering we use as the collision resolution function (ii (hash( ))where hash(xis the -bit hash value (not yet scaled to suitable array index)and ( | ymod ( )) /*fnv- hash routine for string objects *unsigned int hashconst string keyint tablesize unsigned int hashval forchar ch key hashval hashval ch ) return hashval tablesizefigure alternative hash function for exercise