Implementing the Hash-based or Unordered Map Implementing the Hash-based or Unordered Map Input: ● Line 1 have three values which indicate the number of lines to follow, the initial number of buckets...

Writing a class for an unordered (hash) map


Implementing the Hash-based or Unordered Map Implementing the Hash-based or Unordered Map Input: ● Line 1 have three values which indicate the number of lines to follow, the initial number of buckets in the table, and maximum load factor. ● Each line starts with a command that indicates which method is executed. The command is separated by a space followed by appropriate parameters. Output: ● Each line prints the execution of the equivalent command. Note: ● The main () function is already built for you. No need to implement main(). ● Last test is fake. Test Case # What are we testing 4 Tests insert, load, and size. Tests on edges were the table rehashes. 5 Tests insert, search, load 6 Tests insert and load 7 Tests insert, remove, load 8 Tests insert and load rapidly and at edges 9 Tests insert with collisons 10 Tests hash 11 Large insert, load and size 12 Large insert, load and size Sample Input 1: 5 5 0.80 hash 33341253 insert 20000000 A insert 10000000 B insert 30000000 C size Sample Output 1: 3 3 Sample Input 2: 5 5 0.80 insert 20000000 A insert 10000000 B insert 30000000 C search 30000000 load Sample Output 2: C 0.60 Sample Input 3: 5 5 0.80 insert 20000000 A insert 10000000 B insert 30000000 C remove 30000000 search 20000000 Sample Output 3: A Sample Input 4: 14 5 0.80 insert 20000000 A insert 10000000 B insert 30000000 C load insert 60000000 D size load insert 40000000 E insert 99999999 F insert 00000001 G load insert 00000002 H size load Sample Output 4: 0.60 4 0.40 0.70 8 0.40 Here is the template of the code. Insert the code where noted #include #include #include #include unsigned int hashFunction(char const* key, int table_size) {} class UnorderedMap { private: //define your data structure here //define other attributes e.g. bucket count, maximum load factor, size of table, etc. public: class Iterator; UnorderedMap(unsigned int bucketCount, double loadFactor); ~UnorderedMap(); Iterator begin() const; Iterator end() const; std::string& operator[] (std::string const& key); void rehash(); void remove(std::string const& key); unsigned int size(); double loadFactor(); class Iterator { public: //this constructor does not need to be a default constructor; //the parameters for this constructor are up to your discretion. //hint: you may need to pass in an UnorderedMap object. Iterator() { } Iterator& operator=(Iterator const& rhs) { } Iterator& operator++() { } bool operator!=(Iterator const& rhs) { } bool operator==(Iterator const& rhs) { } std::pair operator*() const { } friend class UnorderedMap; }; }; UnorderedMap::UnorderedMap(unsigned int bucketCount, double loadFactor) { } UnorderedMap::~UnorderedMap() { } UnorderedMap::Iterator UnorderedMap::begin() const { } UnorderedMap::Iterator UnorderedMap::end() const { } std::string& UnorderedMap::operator[] (std::string const& key) { } void UnorderedMap::rehash() { } void UnorderedMap::remove(std::string const& key) { } unsigned int UnorderedMap::size() { } double UnorderedMap::loadFactor() { } //implement other operators in Iterator class //Do not change main() int main() { int lines = 0, buckets = 0; double maxLoadFactor = 0.0; std::string command = "", ufid = "", name = "", key = ""; std::cin >> lines >> buckets >> maxLoadFactor; UnorderedMap myMap = UnorderedMap(buckets, maxLoadFactor); while(lines--) { std::cin >> command; if(command == "hash") { std::cin >> key; const char* convertedKey = key.c_str(); std::cout < hashfunction(convertedkey,="" buckets)="">< "\n";="" }="" else="" if(command="=" "insert")="" {="" std::cin="">> ufid >> name; myMap[ufid] = name; } else if(command == "size") { std::cout < mymap.size()=""><"\n"; }="" else="" if(command="=" "load")="" {="" std::cout="">< std::fixed="">< std::setprecision(2)="">< mymap.loadfactor()=""><"\n"; }="" else="" if(command="=" "search")="" {="" std::cin="">> ufid; std::cout < mymap[ufid]="">< "\n";="" }="" else="" if(command="=" "traverse")="" {="" for="" (unorderedmap::iterator="" iter="myMap.begin();" iter="" !="myMap.end();" ++iter)="" {="" std::cout="">< (*iter).first="">< "="" "="">< (*iter).second="">< "\n";="" }="" *="" this="" should="" also="" work="" for="" (auto="" tableentry:="" mymap)="" {="" std::cout="">< tableentry.first="">< "="" "="">< tableentry.second="">< "\n";="" }="" */="" }="" else="" if(command="=" "remove")="" {="" std::cin="">> ufid; myMap.remove(ufid); } } return 0; } 11/6/21, 10:17 PM Project 2a: Individual submission https://ufl.instructure.com/courses/436423/assignments/4829947 3/16 Return true if the deletion is successful and return false if the deletion is unsuccessful. Note: You do not need to create these methods from scratch. Call and modify the respective methods your peer already coded in Project 1. If your peer coded the corresponding methods incorrectly, message the Instructor on Slack. Testing your tree-based map and Skeleton Code: https://stepik.org/lesson/596462/step/1?unit=591487 (https://stepik.org/lesson/596462/step/1?unit=591487)      Part 2: Implementing the Hash-based or Unordered Map  [40 points] Unordered maps, or hash-based maps, store pairs in an unsorted fashion, as they are built upon a hash table. The map's hash function generates a hash code from the key, reduces this hash code (usually by modulo) to an index, and the key-value pair is placed in the table at this index.   Hash function (key)   ==>   hash code (key) % Data_Structure_Capacity    ==>   index Suppose our map is backed by a structure that can hold 5 items. If the hash code for a key (int) is the ASCII value of the �rst character and we wanted to add the UFID “20000000”, our hash code would be 50, so our hash function would return an index of 0 (50 % 5). The UFID “20000000” and its de�nition would be stored in bucket or position 0 in the underlying data structure.  One problem with hash-based maps is collision between keys. If we also wanted to store the UFID “70000000”, the hash function would generate the the hash code 55, so we’d be using bucket/position 0 again. To deal with collisions in this implementation, make each hash map bucket a linked list that can hold multiple pairs. When we want to store or retrieve a value, we compute the bucket of the key and then step through the bucket's list until we �nd the correct value.  https://stepik.org/lesson/596462/step/1?unit=591487 11/6/21, 10:17 PM Project 2a: Individual submission https://ufl.instructure.com/courses/436423/assignments/4829947 4/16 Figure 2: Hash-based Map with Separate chaining using linked lists and buckets. The top value is UFID which is the key, the bottom value is Student Name which is the value, Hash_code is ASCII value of key's �rst character, and the table size is 5 initially. Your implementation of the unordered map will involve three main components: the bucketing structure, the hash function, and the iterator. 2.1. Bucketing Structure: The bucketing structure will be based on a given initial bucket count and maximum load factor. Collisions should be resolved using the linked list method described above. You should implement your own list and not rely on std::list; this is crucial for later implementing your Iterator. Once the current load factor meets or exceeds the maximum load factor, the bucket count and hash table should double in size. For example, if the maximum load factor is 0.8, the current capacity is 10, and there are 7 keys in the table, the current load factor is 0.7. Therefore, the next insertion should trigger a rehash where the capacity doubles in size, and the current data is rehashed from the old hash table to the new hash table. Removals should not cause rehashing; there is only a maximum load factor, not a minimum load factor. In order to determine where in the table to insert new key/value pairs, you will need to build and utilize the hash function described next. 2.2. Hash Function: Your hash function must adhere to the following speci�cations: The input of the hash function is a character array, while the output of your hash function is an unsigned integer which represents the hash code for your key. The goal of this algorithm is to encode a character array into 32-bits binary hash code. The function will use the bit shifting operators (“<” to="" shift="" bits="" left,="" and="" “="">>” to shift bits right. For example, 1 < 2="" is="" 4="" and="" 2="">> 1 is 1.), bit-wise exclusive OR operator (^) and bit inversion operator (~).  For more information about these operators, refer to C++ operators (https://www.cplusplus.com/doc/tutorial/operators/) . https://www.cplusplus.com/doc/tutorial/operators/ 11/6/21, 10:17 PM Project 2a: Individual submission https://ufl.instructure.com/courses/436423/assignments/4829947 5/16 Pseudocode to determine hash_code The hash code for the key is initially set to 0 with unsigned integer type. Unsigned integer a represents the ASCII value of your key at index n. b is a temporary variable with unsigned integer type. Begin          Initiate hash code for a character array (your key) with 0.          Traverse the character array from left to right (from 0 index to the end of the array):                   If n is even:                         b = (Hash code < 7)="" ^="" a="" ^="" (hash="" code="">>3)                   If n is odd:                       b = (Hash code < 11)="" ^="" a="" ^="" (hash="" code="">>5)                       b = ~ b               Update hash code: hash code = hash code ^ b          Traverse end        Set the leftmost bit to 0. (i.e., set the 32nd bit to 0)          Return hash code End Taking the modulus of the resulting hash code with respect to the bucket count will yield the �nal position for insertion and this value must be returned by your hash function. Examples Consider the following examples, where the bucket count is 100 and Hash is the output of the hash function. Key (char array) Hash Code (unsigned int) Hash or Insert Position "Hello" 1684828962 62 "Gator"  1328599194 94 "33341253" 1788611538 38 Method signature for Hash Function Method Description unsigned int hashFunction(char const* key, int table_size) {} Convert the key to the hash code and change the hash code to an index associated with the table.  n n n 11/6/21, 10:17 PM Project 2a: Individual submission https://ufl.instructure.com/courses/436423/assignments/4829947 6/16 2.3. Iterator The �nal component is the iterator class. You will build an unordered_map::Iterator class which supports the de- referencing, pre-incrementing, assignment, equality, and non-equals operators. You should build this from scratch and not rely on any existing iterator implementations. Method signatures for Unordered map and associated iterator Your unordered map must support the following methods: Method Description UnorderedMap(unsigned int bucketCount, double loadFactor) Constructor for UnorderedMap. Parameters are the initial total bucket count, and the maximum load factor. Iterator begin() const Returns an iterator pointing to the beginning of the map (�rst bucket, �rst key/value pair). Iterator end() const Return an iterator pointing past the