template class pair hashedobj keyobject def/appropriate constructorsetc }template class dictionary publicdictionary)void insertconst hashedobj keyconst object definition )const object lookupconst hashedobj key constbool isemptyconstvoid makeempty)privatehashtableitems}figure dictionary skeleton for exercise implement hopscotch hash table and compare its performance with linear probingseparate chainingand cuckoo hashing implement the classic cuckoo hash table in which two separate tables are maintained the simplest way to do this is to use single array and modify the hash function to access either the top half or the bottom half extend the classic cuckoo hash table to use hash functions show the result of inserting the keys into an initially empty extendible hashing data structure with write program to implement extendible hashing if the table is small enough to fit in main memoryhow does its performance compare with separate chaining and open addressing hashingreferences despite the apparent simplicity of hashingmuch of the analysis is quite difficultand there are still many unresolved questions there are also many interesting theoretical issues