AST20105 – Individual Project (Hash Table) – 30% Deadline: Dec 15 You are asked to implement an individual project on Hashing. A programming framework has already done for you and you are asked to further develop it. Go to Canvas and download a starting file in zip format. Once you have decompressed it, you will get the following files: 1. CreditCard.h – A file contains details of a credit card and several related functions. 2. CardHash.h – A header file that contains 2 attributes (hashTableSize and reHashSize). The hashTableSize determines the size of a hash table (also called hash map). You may change this figure for your observation. The reHashSize is relative prime number of hashTableSize for rehashing purpose. Beside the two attributes, there are several functions. Some of the functions have been developed for your reference while the rest is for your implementation. Refer tasks detailed in later section. 3. CardHash.cpp – Actual implementation of CardHash.h. Documentation (comments) are provided for you in the file. 4. main.cpp – A file for your testing purpose Tasks: 1. Design and implement Hashing(…) in CardHash.cpp (5%) Hashing(…) is a method that takes a key (credit card number) and convert it into a hash value. With the hash value, the corresponding credit card object could be put into its corresponding slot. For example, if hash value is 5, then slot 5 (the sixth slot) should take the credit card details. Use comments within your code to clearly explain your approach of hashing. 2. Implement CreditCard* HashingQuadProbing(…) in CardHash.cpp (5%) The function takes 3 parameters: cards, numCard, and numCollision. cards is an array containing 20 credit card objects, each carrying credit card details like credit card number, name, address, etc. numCard is the total number of credit cards, in this case, 20. numCollision is a parameter using pass-by-reference to record the number of collisions happening in hashing. AST20105 – Individual Project (Hash Table) – 30% Deadline: Dec 15 The function attempts to take, for each card, credit card number as a key to produce a hash value. Once a hash value is produced, the corresponding credit card details will be recorded at its corresponding slot. Hint: refer HashingLinearProbing(…) for detailed implementation. They should be highly similar except the way of handling when collision happens. 3. Implement CreditCard* RetrieveQuad(…) in CardHash.cpp. (5%) This function takes 2 parameters (crdNum, cardQuad). crdNum is a credit card number serves as the “key” while cardQuad is a hash table created in task 2. The function takes crdNum as a key and put it into the hash function (task 1) to generate a hash value. Once a hash value is produced, the function will look for the corresponding slot in the hash table, cardQuad, to see if the credit card number in that slot matches with crdNum. If it match, return its corresponding credit card details. If they do not match, look for its i2 slot, quadratic probing. Hint: refer RetreiveLinear(…) for detailed implementation. They should be highly similar. 4. Implement int ReHashing(…) in CardHash.cpp (5%) This function is just another hash function (Hashing(…) in task 1) but using another m. In Hashing(…), the m is the size of the hash table, given in CardHash.h. In ReHashing(…), the m should be carefully chosen. Value of m should be smaller than and also be a relatively prime number to the hash table size. In this case, m = 17, is selected for you. You could use other values though. Reminder: ReHashing(…) MUST NOT return 0. Otherwise, rehashing will not happen. Explain your way of rehashing by commenting within codes. AST20105 – Individual Project (Hash Table) – 30% Deadline: Dec 15 5. Implement CreditCard* HashingRehash(…) in CardHash.cpp (5%) This function is similar to HashingLinearProbing(…) and HashingQuadProbing(…) except its way of handling collision is different. When collision happens, put the key (credit card number) into a the rehash function (in task 5) and generate another hash value. 6. Implement CreditCard* RetrieveRehash(…) in CardHash.cpp (5%) This function is similar to CreditCard* RetreiveLinear(…) and CreditCard* RetrieveQuad(…) except its way of collision handling is different. Submission Details: Submit CardHash.cpp to Canvas before deadline (Dec 15). Make sure you do not copy your colleagues’ work. If plagiarism is found, all involved parties (regardless your role in such case) will be graded 0. You could work together and exchanging ideas are fine but your coding style and ideas should be different. Working together so that your works are highly similar IS NEVER a reason. P.S. 1. I may provide some updates from time to time and I will announce it through Canvas. 2. Refer 2 sample outputs for your implementation. Your outputs most possibly will look different than mine as we are using different hashing approaches. Sample Output 1 Number of cards: 20 Hash Map Size (for closed addressing): 23 ————–Linear Probing———————— 46 happen(s) in linear probing ======Beginning of Hash Map (Slot with Data)============ Slot 0: Dominique Bordone(4065984214713801) Slot 1: Hilary Custard(4347870761788074) Slot 2: Betteann Upstell(4049264004545627) Slot 3: Nickolai Leader(4003548634274283) Slot 4: Johnna Cainey(4561526251506314) Slot 5: Jacob Novacek(4074510487240336) Slot 6: Sula Blaxland(4347874240558041) Slot 7: Isaac Pochin(4065674214741767) Slot 8: Philippine Stollhofer(4558914742768674) Slot 12: Nickolai Killshaw(4014177144343474) Slot 13: Zacharia Bickerton(4550064373516675) Slot 14: Hilary Kann(4347901087543248) Slot 15: Stillman Storre(4037467332718071) Slot 16: Raychel Thumann(4014177123578744) Slot 17: Nadia Custard(4598838333664327) Slot 18: Smitty Elph(4051071867467780) Slot 19: Cchaddie Samter(4347975277886310) Slot 20: Torrence Elph(4077011241242673) Slot 21: Isaac Dragonette(4077016428172346) Slot 22: Bridie Giercke(4550064341815084) ================End of Hash Map===================== =======Beginning of Display Credit Card Details ======== Credit Card Details of: 4077016428172346 Holder: Isaac Dragonette Expiry Date: 7/2022 Holder’s address: 0506 Lakeland Hill, United States ======End of Display Credit Card Details ============ Sample Output 1 ————–Quadradic Probing———————— 19 happen(s) in quadratic probing ======Beginning of Hash Map (Slot with Data)============= Slot 0: Dominique Bordone(4065984214713801) Slot 1: Hilary Custard(4347870761788074) Slot 2: Nickolai Leader(4003548634274283) Slot 3: Philippine Stollhofer(4558914742768674) Slot 4: Johnna Cainey(4561526251506314) Slot 5: Jacob Novacek(4074510487240336) Slot 6: Sula Blaxland(4347874240558041) Slot 8: Cchaddie Samter(4347975277886310) Slot 9: Isaac Pochin(4065674214741767) Slot 12: Nickolai Killshaw(4014177144343474) Slot 13: Zacharia Bickerton(4550064373516675) Slot 14: Hilary Kann(4347901087543248) Slot 15: Stillman Storre(4037467332718071) Slot 16: Raychel Thumann(4014177123578744) Slot 17: Betteann Upstell(4049264004545627) Slot 18: Smitty Elph(4051071867467780) Slot 19: Nadia Custard(4598838333664327) Slot 20: Torrence Elph(4077011241242673) Slot 21: Isaac Dragonette(4077016428172346) Slot 22: Bridie Giercke(4550064341815084) ================End of Hash Map===================== =======Beginning of Display Credit Card Details ========= Credit Card Details of: 4077016428172346 Holder: Isaac Dragonette Expiry Date: 7/2022 Holder’s address: 0506 Lakeland Hill, United States ======End of Display Credit Card Details =========== Sample Output 1 ————–Rehashing———————— 22 happen(s) in rehashing ======Beginning of Hash Map (Slot with Data)============ Slot 0: Cchaddie Samter(4347975277886310) Slot 1: Hilary Custard(4347870761788074) Slot 2: Isaac Poch
in(4065674214741767) Slot 4: Dominique Bordone(4065984214713801) Slot 5: Jacob Novacek(4074510487240336) Slot 6: Sula Blaxland(4347874240558041) Slot 7: Johnna Cainey(4561526251506314) Slot 8: Philippine Stollhofer(4558914742768674) Slot 10: Nickolai Leader(4003548634274283) Slot 12: Nickolai Killshaw(4014177144343474) Slot 13: Zacharia Bickerton(4550064373516675) Slot 14: Isaac Dragonette(4077016428172346) Slot 15: Stillman Storre(4037467332718071) Slot 16: Raychel Thumann(4014177123578744) Slot 17: Betteann Upstell(4049264004545627) Slot 18: Smitty Elph(4051071867467780) Slot 19: Nadia Custard(4598838333664327) Slot 20: Torrence Elph(4077011241242673) Slot 21: Hilary Kann(4347901087543248) Slot 22: Bridie Giercke(4550064341815084) ================End of Hash Map====================== =======Beginning of Display Credit Card Details ========= Credit Card Details of: 4077016428172346 Holder: Isaac Dragonette Expiry Date: 7/2022 Holder’s address: 0506 Lakeland Hill, United States ======End of Display Credit Card Details ============ Program ended with exit code: 0 Sample Output 2 Number of cards: 20 Hash Map Size (for closed addressing): 29 ————–Linear Probing———————— 13 happen(s) in linear probing ======Beginning of Hash Map (Slot with Data)============ Slot 0: Johnna Cainey(4561526251506314) Slot 1: Jacob Novacek(4074510487240336) Slot 2: Cchaddie Samter(4347975277886310) Slot 3: Dominique Bordone(4065984214713801) Slot 4: Bridie Giercke(4550064341815084) Slot 5: Raychel Thumann(4014177123578744) Slot 6: Nickolai Leader(4003548634274283) Slot 8: Smitty Elph(4051071867467780) Slot 9: Torrence Elph(4077011241242673) Slot 10: Hilary Custard(4347870761788074) Slot 12: Nadia Custard(4598838333664327) Slot 14: Isaac Dragonette(4077016428172346) Slot 15: Zacharia Bickerton(4550064373516675) Slot 20: Stillman Storre(4037467332718071) Slot 21: Sula Blaxland(4347874240558041) Slot 22: Betteann Upstell(4049264004545627) Slot 25: Philippine Stollhofer(4558914742768674) Slot 26: Isaac Pochin(4065674214741767) Slot 27: Nickolai Killshaw(4014177144343474) Slot 28: Hilary Kann(4347901087543248) ================End of Hash Map====================== =======Beginning of Display Credit Card Details ======== Credit Card Details of: 4077016428172346 Holder: Isaac Dragonette Expiry Date: 7/2022 Holder’s address: 0506 Lakeland Hill, United States ===========End of Display Credit Card Details ========== Sample Output 2 ————–Quadradic Probing———————— 6 happen(s) in quadratic probing ======Beginning of Hash Map (Slot with Data)============ Slot 0: Johnna Cainey(4561526251506314) Slot 1: Jacob Novacek(4074510487240336) Slot 2: Cchaddie Samter(4347975277886310) Slot 3: Dominique Bordone(4065984214713801) Slot 4: Nickolai Leader(4003548634274283) Slot 5: Raychel Thumann(4014177123578744) Slot 6: Bridie Giercke(4550064341815084) Slot 8: Smitty Elph(4051071867467780) Slot 9: Torrence Elph(4077011241242673) Slot 10: Hilary Custard(4347870761788074) Slot 12: Nadia Custard(4598838333664327) Slot 14: Isaac Dragonette(4077016428172346) Slot 15: Zacharia Bickerton(4550064373516675) Slot 20: Stillman Storre(4037467332718071) Slot 21: Sula Blaxland(4347874240558041) Slot 22: Betteann Upstell(4049264004545627) Slot 25: Philippine Stollhofer(4558914742768674) Slot 26: Isaac Pochin(4065674214741767) Slot 27: Nickolai Killshaw(4014177144343474) Slot 28: Hilary Kann(4347901087543248) ================End of Hash Map===================== =======Beginning of Display Credit Card Details ========= Credit Card Details of: 4077016428172346 Holder: Isaac Dragonette Expiry Date: 7/2022 Holder’s address: 0506 Lakeland Hill, United States =======End of Display Credit Card Details ============ Sample Output 2 ————–Rehashing———————— 10 happen(s) in rehashing =====Beginning of Hash Map (Slot with Data)============= Slot 0: Johnna Cainey(4561526251506314) Slot 1: Jacob Novacek(4074510487240336) Slot 2: Cchaddie Samter(4347975277886310) Slot 3: Nickolai Leader(4003548634274283) Slot 5: Raychel Thumann(4014177123578744) Slot 6: Dominique Bordone(4065984214713801) Slot 8: Smitty Elph(4051071867467780) Slot 10: Hilary Custard(4347870761788074) Slot 11: Torrence Elph(4077011241242673) Slot 12: Nadia Custard(4598838333664327) Slot 14: Bridie Giercke(4550064341815084) Slot 15: Zacharia Bickerton(4550064373516675) Slot 17: Isaac Dragonette(4077016428172346) Slot 20: Stillman Storre(4037467332718071) Slot 21: Sula Blaxland(4347874240558041) Slot 22: Betteann Upstell(4049264004545627) Slot 25: Philippine Stollhofer(4558914742768674) Slot 26: Isaac Pochin(4065674214741767) Slot 27: Nickolai Killshaw(4014177144343474) Slot 28: Hilary Kann(4347901087543248) ================End of Hash Map========================= ========Beginning of Display Credit Card Details ======== Credit Card Details of: 4077016428172346 Holder: Isaac Dragonette Expiry Date: 7/2022 Holder’s address: 0506 Lakeland Hill, United States ======End of Display Credit Card Details =========== Program ended with exit code: 0
