IntroductionPro21、改进hash函数，减少由于hash函数结果相同导致的碰撞2、因为哈希表的大小发生变化，哈希函数最后一步的mod m的答案发生变化，导致原本在表中的数据位置需要作出调整，不然在查找时由于两次使用的哈希函数不一致会导致位置的不一致。3、不是，由于复杂度取决于碰撞几率，当碰撞几率小的时候可以理解为复杂度是均等的，但当碰撞几率大的时候复杂度不均等RequirementCSE 331 Spring 2017Project 3100 pointsDue April 20th, 9:00pm via CSE HandinThis is not a team work, do not copy somebody else’s work.Assignment OverviewThis assignment focuses on implementing a Hash Table using hashing with chaining and tabledoubling. You will design and implement the C++ program described below.Assignment DeliverablesThe deliverables for this assignment are the following files:HashTable.h - ​​The source code of your solution.problem2.pdf​​ - The PDF containing your answers to ​Problem 2​​.Be sure to use the specified file names and to submit your files for grading ​via the CSE handinsystem​​ before the project deadline.Assignment SpecificationsYour task will be to complete the methods list under ​Problem 1 and Problem 2​​ below.Assignment NotesPoints will be deducted if your solution has any warnings of type:comparison between signed and unsigned integer expressions [-Wsign-compare]The types specified in the functions are very important because of the size of the numbers usedin this ADT. With integers/floating-points in C++, if the destination of a value is not largeenough to hold the data in the value in the source, (​int f = uint64_t d). ​If you ignorethe warnings from the compiler because you used the incorrect types, ​consider those warningserrors and fix them without losing precision.Page 2​​ - Illustrations of the Hash Table implementation. See the last page of thisdocument for information on secondary resources and a quick overview of themake​commands provided.Page 3 ​​- Outlines ​Problem 1​​ and​ Problem 2​​.Page 4 ​​- Explains ​make​​, ​make test​​, and ​how to trace a segfault​​, and includes links tosecondary resources.Hash TablesHash Tables are one of the most important ADT in Computer Science because of theirpromise of ​constant time​​ operations and “constant” space complexity. We say “constant” spacecomplexity because in reality most efficient implementations Hash Tables may actually beslightly,​but not overly,​wasteful when it comes to space.The implementation used in this project uses ​Chaining​and ​Table Doubling/Halving​.Visti lecture notes for Chaining and please see the above links for a clear understanding of theresizing that will enable the desire performance.When we ​insert​​ a ​key​​ into the Hash Table a few things happen.1.The ​key​​ is ​pre-hashed—converted to an integer representation for mapping.2.Using the ​hash function​​, the ​pre-hash​​ is mapped to one of the slots (chains). ma. Hashing functions like division method, multiplication method, etc.3.If the Hash Table has as many items as it has chains, the table doubles in size.a. If doubled, all items in the Hash Table are put into the ​hash function​​ oncemore in order to find which chain the item should be placed in.4.Once the chain is found, the node is placed at the ​tail​​ of the chain.When we ​remove​​ a ​key ​​something from the Hash Table a few things happen.1.The ​key​​ is ​pre-hashed—converted to an integer representation for mapping.2.Using the ​hash function​​, the ​pre-hash​​ is mapped to one of the slots (chains). ma. Hashing functions like division method, multiplication method, etc.3.Once the chain is found, it is traversed (linked list traversal) until a node is foundwith the matching ​key​​ (the ​hash​​ of the key, that is).4.Once the node is found, the removal is made in-place.2Problem 1Your job is to implement a Hash Table that uses table doubling and chaining to amortize most standardoperations to ​Θ(1)​​. You have to implement the following public methods in your Hash Table:1) HashTable(size_t m)a) Builds the empty Hash Table with a total ​m​ chains. All chains will be empty. ​m​ must be positive.2C代写 CSE 331 Spring 2017代写C/C++实验) ~HashTable()a) Destructor for the Hash Table ensures all nodes in every chain is deleted properly.3) void insert(string key, string value):a) Adds the key value pair to the Hash Table.b) If the key already exists, the value is overwritten with ​value​.c) The table is required to grow using the ​Grow​ function when . where ​n​ is the number of n > melements in the Hash Table and ​m​ is the number of chains in the Hash Table. For example, a HashTable of size 4 would need to grow after the 5​th​​insert​ operation without any interweavingremove​ operations. The size will grow to where is the number of chains in the Hash Table m 2 mcurrently. Only double after an ​add​ operation. A table of size ​0​​ should double to size ​1​​.4) const string* get(string key) const:a) Returns a pointer to the value of the key in the Hash Table if found, otherwise returns ​nullptr​.5) void remove(string key):a) Removes key-value pair (represented by the ​ChainNode​ class) from the Hash Table.b) The table is required to shrink using the ​Shrink​ function when the table is at least ​¾​ ​empty. Thisis true when . The check is always done at the ​end​​ of a ​remove​ operation. Only shrink n ≤4mafter a ​remove​ operation. In your code, take the ​ceiling​of and check if it is​if so, shrink​.4mn ≥6) uint64_t HashFunction(string key):a) Returns the index of the chain ​key​ should be mapped to according to the ​division​method.7) uint64_t Grow():a) Grows the Hash Table such that 2m m =8) uint64_t Shrink():a) Shrinks the Hash Table such that m/2 m =9) void Rehash(size_t originalSize):a) Rehashes the items in the Hash Table to align with the current ​HashFunction.​he See thesecondary resources for intuition on why we must re-hash all our elements (and what rehashactually entails. ​Hint:​the pre-hash of the values will never change.Problem 2Answer the following questions in a digital document and submit your answers in ​a single​​ PDF,named ​problem2.pdf​​:1. What changes would we need to make in order to decrease the probability of a collision (in ourimplementation)?2. Why must we re-hash all of the items in the table when growing/shrinking?3. Is this data structure constant time per operation? Why or why not? (hint: amortization)3Using the makefile and testing your workRun the project on the CSE server ​black (black.cse.msu.edu)​using the commands below.Makefile commands:makeThis will compile the code in main.cpp and generate an executable name ​ProjectHashTable. ​Runthis executable with the command ​./ProjectHashTablemake testThis will run the tests for the project. These tests are only a subset of all tests and only cover a few of therequired methods. Passing all tests does not guarantee you will get all the points. These are only publictests. Your code will be tested against these tests and extra private tests.Tracing segfaults:Is the executable generated from main.cpp crashing?1.In the terminal run the following (type the command and pressreturn), notice the ​or​​ which means either command will work:a.makeb.gdb (or lldb) ./ProjectHashTablec.rd.where (if gdb)e.bt (if lldb)2.The line your code crashed on should be indicated in the terminal.Are the tests crashing?:1.All steps are == except:a.make testb.gdb (or lldb) ./tests/testsPlease make sure to have your ​​tests​subfolder in your project folder in order to runthe make test command successfully. If not, extract the folder from the project zip.More informationFor more information, see the following online video lecture or the following lecture notes:CLRS(11.2, 11.3)6.006 MIT Online Video Lecture​​ / ​​Lecture NotesReference​: ​​This project was created by the following incredible students. ​Ibrahim Ahmed​authorof the project and multiple test cases. ​Fatema Alsaleh and Scott Swarthout​authors of multipletest cases.转自：http://ass.3daixie.com/2019042536766877.html