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 Pochin(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