Need help with this assignment : you can find the book there: http://www.uoitc.edu.iq/images/documents/informatics-institute/Competitive_exam/DataStructures.pdf If you cannot do it it's understandable, leave it for someone who actually can. :)

Outline: in this assignment, you will create two separate implementations of an unordered mag in C++: 1) Unordered_map using hash table with separate chaining 2) Unordered_map using red-black tree a. Note typically, trees are used for ordered map, not unordered map, but we will use it in this assignment for academic purposes. Description: unordered maps are associative containers that store elements formed by the combination of a key value and a mapped value, allowing for fast retrieval of individual elements based on their keys. The key value is used to identify the element, and the mapped value is an object with content associated to this key. Check section 4.8 ofthe Weiss textbook for more details. Your map must implement the following methods: find, erase, insert, operator, size, clear, count, empty You must provide a method for all the signatures described in the pages linked to above. For example, erase requires three separate implementations, you must provide all three: iterator erase C constiiterator position 3 size type erase C const key type& R N iterator erase C const_iterator first. const_iterator Last )1 Most of these functions will just involve calling the respective function on the underlying data structure (hash table or tree). For example, operator {1 will call contains on the tree and then return the element if it exists. Because erase requires an iterator, you must provide a full iterator implementation for your unordered map. This means implementing separate iterators for hash table and red-black trees. Page 176 of Weiss gives hints for tree iterator. Timing experiments: compare the performance of your two map implementations on 100000 elements. first, insert all the elements, then find and return them using operator [ ] , then erase them one-by-one using erase. Do two versions of the experiment, version 1 using int values as the key in your key-value pair, and version 2 using strings (of at least 8 chars) in your key-value pair. You can use 'float' as value in both cases. Your table should look as follows: Hash table Red-black tree Hash table Red-black tree (int keys) (int keys) (string keys) (string keys) Insert 100k elements operator 100k times Erase 100k elements The hash table is expected to perform better, but make sure to accurately report whatever you find! Hints: you may use the red-black tree and hash table code from the Weiss textbook as the base data structures. However, you will need to modify this code to store key-value pairs, and you will need to implement the rest of the map logic yourself, including all the functions outlined above. You will probably want to provide two separate map implementations, example: TreeMap and HashTableMap, instead of making the data structure a template parameter. Bonus: see if you can speed up your map by using different hash functions, collision resolution methods (quadratic or linear probing), and tree implementations. Also, try to provide a single map class, and make the data structure (tree or hash table) a template parameter (similar to what stl does for gueue with class Container). HashMap () : table(16), num_elements(0) {} HashMap(size_t num_buckets) : table(num_buckets), num_elements(0) {} ~HashMap() = default; void insert(const KeyType& key, const ValueType& value) { size_t index = hash_function(key) % table.size(); HashNode* node = table [index].get(); while (node != nullptr) { if (node->key == key) { node->value = value; return; 3 node = node->next; auto new_node = std::make_unique (key, value); new_node->next = table [index].release(); table [index]. Yes, this code appears to be generated by ChatGPT. The code provides an implementation of an unordered map using a hash table with separate chaining in C++. The implementation includes a class definition with methods for find, erase, insert, operator , size, clear, count, and empty. The code also mentions conducting timing experiments on 100,000 elements using int and string keys to compare the performance of the hash table implementation and a red-black tree implementation. The code includes suggestions for optimizing the map with different hash functions, collision resolution methods, and tree implementations, and making the data structure a template parameter